現實生活中存在很多問題，比如商品買賣如何實現商家利潤最大化？大學生招生錄取如何實現整體效果最好？病人醫生如何實現整體服務水平最高等？這些我們都可以把他統一的轉化為雙邊決策問題。下面先說說自己對雙邊決策的理解。
雙邊決策――個人理解
為了幫助大家理解，我用一個簡單的例子介紹什么是雙邊決策，加入現在市場上有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）在寫算法的時候，我們首先需要定義一些常量、保存分配方案等：
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）在運行算法之前，我們需要設置個體數目
public void setNum(int num) { if (num < 1) { System.out.println("num must be greater than 0"); return; } this.num = num; } 3）顧客對商品進行滿意度打分并確定初始分配方案
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）步，確認分配方案是否對調
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; } 這個方法的返回值是確認該步長下是否發生對調，如果該步長沒有發生對調，我們可以進行下一個步長的比較。這樣就完成了雙邊決策算法，下面我們看一下測試結果。
運行結果
最大值測試
最小值測試
完整代碼
/** *@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()); } } 以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
