現實生活中存在很多問題，比如商品買賣如何實現商家利潤最大化？大學生招生錄取如何實現整體效果最好？病人醫生如何實現整體服務水平最高等？這些我們都可以把他統一的轉化為雙邊決策問題。下面先說說自己對雙邊決策的理解。
雙邊決策——個人理解
為了幫助大家理解，我用一個簡單的例子介紹什么是雙邊決策，加入現在市場上有10位顧客，分別為A0、A1、A2、A3、A4、A5、A6、A7、A8、A9，市場上有是個商品，分別為B0、B1、B2、B3、B4、B5、B6、B7、B8、B9，現在要求要把這10個商品分別分給這10位顧客，要求整體的滿意程度最高，當然每位顧客對每個商品的打分是不一樣的，加入M位顧客對N件商品的滿意度為AMBN，那么如何分配這些商品才能使整體的滿意度最高？像這個為題就是一個雙邊決策問題。
算法介紹
目前關于雙邊決策的實現算法有很多，下面就介紹一種自己想到的（如有雷同，純屬巧合），這個算法是基于之前自己寫的一篇遺傳算法的文章想到的。自己這個算法要求顧客和商品的數目必須一致，并且是一對一的關系，如果數目不一致或者是一對N（N是一個具體值）的時候，我們可以通過構建虛擬的商品（顧客）來使用這個算法，下面我就簡單介紹下算法思想：
1）我們首先選取一個分配方案，這里我們不防假定初始的分配方案就是M件商品分給M位顧客；
2）我們將比較步長step設置為1；
3）判斷step是否超過數組長度，如果超過結束算法，如果沒超過繼續執行下一步；
4）比較step步長下的兩位顧客，假設將他們的分配方案對調，如果對調之后的滿意度大于對調前的滿意度就進行對調，否則保持原樣，將比較位往后移動一位繼續進行第4）步；
5）該步長step下已經沒有可以對調的分配方案，將步長step加1；
6）跳到第3）步繼續執行。
在上述算法描述中，我們重點介紹下第4）步，這里我們假設第1位顧客分配的商品是1號商品，第2位顧客分配的商品是2號商品，他們對商品的滿意度分別為A1B1、A2B2，這時這兩個顧客的總體滿意度為SCORE1=A1B1+A2B2，這里我們將他們的分配方案對調，也就是第1位顧客分配的商品是2號商品，第2位顧客分配的商品是1號商品，這時候他們對商品的滿意度分別為A1B2、A2B1，這兩個顧客的整體滿意度為SCORE2=A1B2+A2B1，如果SCORE1小于SCORE2，那么我們就改變分配策略，否則保持原來的分配策略。
Java代碼分析
對于上面的介紹也許并不是太具體，或者并不知道用JAVA如何實現，下面我們就對如何實現做拆解：
1）在寫算法的時候，我們首先需要定義一些常量、保存分配方案等：
|
1
2
3
4
5
6
|
public class TwoSidedDecision { private int num = 10;//個體數目 private boolean maxFlag = true;//是否求最大值 private int[][] scoreArray;//AB之間的互評得分 private int[] decisionArray;//A選擇B的方式 } |
這里有一個maxFlag屬性，他的作用是用來標識我們的雙邊決策是要取最大值還是要取最小值，true表示最大值，false表示最小值；num用來標識個體的個數，scoreArray數組用來表示用戶對商品的滿意度，decisionArray用來保存商品的分配方案，decisionArray[0]表示編號為0的顧客分配的商品是decisionArray[0]；
2）在運行算法之前，我們需要設置個體數目
|
1
2
3
4
5
6
7
|
public void setNum(int num) { if (num < 1) { System.out.println("num must be greater than 0"); return; } this.num = num; } |
3）顧客對商品進行滿意度打分并確定初始分配方案
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public void setScoreArray(int[][] scoreArray) { if (scoreArray == null) { System.out.println("scoreArray is null"); } if (!(scoreArray.length == num && scoreArray[0].length == num)) { System.out.println("scoreArray`s must be " + num); } this.scoreArray = scoreArray; decisionArray = new int[num]; //初始決策，對角線 for (int i = 0; i < num; i++) { decisionArray[i] = i; } decision(); } |
4）然后進行算法描述中的第4）步，確認分配方案是否對調
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
private boolean compare(int stepSize) { for (int i = 0; i < num - stepSize; i++) { int a1 = i; int a2 = i + stepSize; int b1 = decisionArray[a1]; int b2 = decisionArray[a2]; //原始兩個得分之和 int score1 = scoreArray[a1][b1] + scoreArray[a2][b2]; int between1 = Math.abs(scoreArray[a1][b1] - scoreArray[a2][b2]); //交換后的兩個得分之和 int score2 = scoreArray[a1][b2] + scoreArray[a2][b1]; int between2 = Math.abs(scoreArray[a1][b2] - scoreArray[a2][b1]); if (maxFlag) { //最后的得分最大 if (score1 <= score2) {//交換后的分數不小于交換前的 //交換后的分數大于交換前的或者交換后的差值大于交換前的 if (score1 < score2 || between2 > between1) { decisionArray[a1] = b2; decisionArray[a2] = b1; return true; } } } else { //最后的得分最小 if (score1 >= score2) {//交換后的分數不小于交換前的 //交換后的分數大于交換前的或者交換后的差值大于交換前的 if (score1 > score2 || between2 > between1) { decisionArray[a1] = b2; decisionArray[a2] = b1; return true; } } } } return false; } |
這個方法的返回值是確認該步長下是否發生對調，如果該步長沒有發生對調，我們可以進行下一個步長的比較。這樣就完成了雙邊決策算法，下面我們看一下測試結果。
運行結果
最大值測試
最小值測試
完整代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
/** *@Description: 雙邊匹配決策算法 */package com.lulei.twosided.matching.decisionmaking; import com.lulei.util.JsonUtil; public class TwoSidedDecision { private int num = 10;//個體數目 private boolean maxFlag = true;//是否求最大值 private int[][] scoreArray;//AB之間的互評得分 private int[] decisionArray;//A選擇B的方式 public boolean isMaxFlag() { return maxFlag; } public void setMaxFlag(boolean maxFlag) { this.maxFlag = maxFlag; } /** * @return * @Author:lulei * @Description: 獲得最后的決策 */ public int[] getDecisionArray() { return decisionArray; } /** * @return * @Author:lulei * @Description: 獲取決策的評分 */ public int getScoreSum() { int sum = 0; for (int i = 0; i < num; i++) { sum += scoreArray[i][decisionArray[i]]; } return sum; } /** * @param num * @Author:lulei * @Description: 設置雙邊決策個體個數 */ public void setNum(int num) { if (num < 1) { System.out.println("num must be greater than 0"); return; } this.num = num; } /** * @param scoreArray * @Author:lulei * @Description: 設置A類個體與B類個體間的評價 */ public void setScoreArray(int[][] scoreArray) { if (scoreArray == null) { System.out.println("scoreArray is null"); } if (!(scoreArray.length == num && scoreArray[0].length == num)) { System.out.println("scoreArray`s must be " + num); } this.scoreArray = scoreArray; decisionArray = new int[num]; //初始決策，對角線 for (int i = 0; i < num; i++) { decisionArray[i] = i; } decision(); } /** * @Author:lulei * @Description: 計算最優決策 */ private void decision() { if (scoreArray == null || decisionArray == null) { System.out.println("please init scoreArray"); } for (int stepSize = 1; stepSize < num; stepSize++) { //特定步長下的交換 while (compare(stepSize)); } } /** * @param stepSize * @return * @Author:lulei * @Description: 特定步長比較，返回值確認是否發生交換 */ private boolean compare(int stepSize) { for (int i = 0; i < num - stepSize; i++) { int a1 = i; int a2 = i + stepSize; int b1 = decisionArray[a1]; int b2 = decisionArray[a2]; //原始兩個得分之和 int score1 = scoreArray[a1][b1] + scoreArray[a2][b2]; int between1 = Math.abs(scoreArray[a1][b1] - scoreArray[a2][b2]); //交換后的兩個得分之和 int score2 = scoreArray[a1][b2] + scoreArray[a2][b1]; int between2 = Math.abs(scoreArray[a1][b2] - scoreArray[a2][b1]); if (maxFlag) { //最后的得分最大 if (score1 <= score2) {//交換后的分數不小于交換前的 //交換后的分數大于交換前的或者交換后的差值大于交換前的 if (score1 < score2 || between2 > between1) { decisionArray[a1] = b2; decisionArray[a2] = b1; return true; } } } else { //最后的得分最小 if (score1 >= score2) {//交換后的分數不小于交換前的 //交換后的分數大于交換前的或者交換后的差值大于交換前的 if (score1 > score2 || between2 > between1) { decisionArray[a1] = b2; decisionArray[a2] = b1; return true; } } } } return false; } public static void main(String[] args) { int[][] scoreArray = { {0,1,2,3,4,5,6,7,8,9}, {1,2,3,4,5,6,7,8,9,0}, {2,3,4,5,6,7,8,9,0,1}, {3,4,5,6,7,8,9,0,1,2}, {4,5,6,7,8,9,0,1,2,3,}, {5,6,7,8,9,0,1,2,3,4}, {6,7,8,9,0,1,2,3,4,5}, {7,8,9,0,1,2,3,4,5,6}, {8,9,0,1,2,3,4,5,6,7}, {9,0,1,2,3,4,5,6,7,8}}; TwoSidedDecision test = new TwoSidedDecision(); test.setNum(10); test.setMaxFlag(false); test.setScoreArray(scoreArray); System.out.println("最優決策"); System.out.println(JsonUtil.parseJson(test.getDecisionArray())); System.out.println("決策得分"); System.out.println(test.getScoreSum()); } } |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
