JAVA實現(xiàn)雙邊決策的示例
現(xiàn)實生活中存在很多問題，比如商品買賣如何實現(xiàn)商家利潤最大化？大學(xué)生招生錄取如何實現(xiàn)整體效果最好？病人醫(yī)生如何實現(xiàn)整體服務(wù)水平最高等？這些我們都可以把他統(tǒng)一的轉(zhuǎn)化為雙邊決策問題。下面先說說自己對雙邊決策的理解。
雙邊決策——個人理解
為了幫助大家理解，我用一個簡單的例子介紹什么是雙邊決策，加入現(xiàn)在市場上有10位顧客，分別為A0、A1、A2、A3、A4、A5、A6、A7、A8、A9，市場上有是個商品，分別為B0、B1、B2、B3、B4、B5、B6、B7、B8、B9，現(xiàn)在要求要把這10個商品分別分給這10位顧客，要求整體的滿意程度最高，當(dāng)然每位顧客對每個商品的打分是不一樣的，加入M位顧客對N件商品的滿意度為AMBN，那么如何分配這些商品才能使整體的滿意度最高？像這個為題就是一個雙邊決策問題。
算法介紹
目前關(guān)于雙邊決策的實現(xiàn)算法有很多，下面就介紹一種自己想到的（如有雷同，純屬巧合），這個算法是基于之前自己寫的一篇遺傳算法的文章想到的。自己這個算法要求顧客和商品的數(shù)目必須一致，并且是一對一的關(guān)系，如果數(shù)目不一致或者是一對N（N是一個具體值）的時候，我們可以通過構(gòu)建虛擬的商品（顧客）來使用這個算法，下面我就簡單介紹下算法思想：
1）我們首先選取一個分配方案，這里我們不防假定初始的分配方案就是M件商品分給M位顧客；
2）我們將比較步長step設(shè)置為1；
3）判斷step是否超過數(shù)組長度，如果超過結(jié)束算法，如果沒超過繼續(xù)執(zhí)行下一步；
4）比較step步長下的兩位顧客，假設(shè)將他們的分配方案對調(diào)，如果對調(diào)之后的滿意度大于對調(diào)前的滿意度就進(jìn)行對調(diào)，否則保持原樣，將比較位往后移動一位繼續(xù)進(jìn)行第4）步；
5）該步長step下已經(jīng)沒有可以對調(diào)的分配方案，將步長step加1；
6）跳到第3）步繼續(xù)執(zhí)行。
在上述算法描述中，我們重點介紹下第4）步，這里我們假設(shè)第1位顧客分配的商品是1號商品，第2位顧客分配的商品是2號商品，他們對商品的滿意度分別為A1B1、A2B2，這時這兩個顧客的總體滿意度為SCORE1=A1B1+A2B2，這里我們將他們的分配方案對調(diào)，也就是第1位顧客分配的商品是2號商品，第2位顧客分配的商品是1號商品，這時候他們對商品的滿意度分別為A1B2、A2B1，這兩個顧客的整體滿意度為SCORE2=A1B2+A2B1，如果SCORE1小于SCORE2，那么我們就改變分配策略，否則保持原來的分配策略。
Java代碼分析
對于上面的介紹也許并不是太具體，或者并不知道用JAVA如何實現(xiàn)，下面我們就對如何實現(xiàn)做拆解：
1）在寫算法的時候，我們首先需要定義一些常量、保存分配方案等：
public class TwoSidedDecision {
private int num = 10;//個體數(shù)目
private boolean maxFlag = true;//是否求最大值
private int[][] scoreArray;//AB之間的互評得分
private int[] decisionArray;//A選擇B的方式
}
這里有一個maxFlag屬性，他的作用是用來標(biāo)識我們的雙邊決策是要取最大值還是要取最小值，true表示最大值，false表示最小值；num用來標(biāo)識個體的個數(shù)，scoreArray數(shù)組用來表示用戶對商品的滿意度，decisionArray用來保存商品的分配方案，decisionArray[0]表示編號為0的顧客分配的商品是decisionArray[0]；
2）在運行算法之前，我們需要設(shè)置個體數(shù)目
public void setNum(int num) {
if (num < 1) {
System.out.println("num must be greater than 0");
return;
}
this.num = num;
}
3）顧客對商品進(jìn)行滿意度打分并確定初始分配方案
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）然后進(jìn)行算法描述中的第4）步，確認(rèn)分配方案是否對調(diào)
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) {//交換后的分?jǐn)?shù)不小于交換前的
//交換后的分?jǐn)?shù)大于交換前的或者交換后的差值大于交換前的
if (score1 < score2 || between2 > between1) {
decisionArray[a1] = b2;
decisionArray[a2] = b1;
return true;
}
}
} else { //最后的得分最小
if (score1 >= score2) {//交換后的分?jǐn)?shù)不小于交換前的
//交換后的分?jǐn)?shù)大于交換前的或者交換后的差值大于交換前的
if (score1 > score2 || between2 > between1) {
decisionArray[a1] = b2;
decisionArray[a2] = b1;
return true;
}
}
}
}
return false;
}
這個方法的返回值是確認(rèn)該步長下是否發(fā)生對調(diào)，如果該步長沒有發(fā)生對調(diào)，我們可以進(jìn)行下一個步長的比較。這樣就完成了雙邊決策算法，下面我們看一下測試結(jié)果。
運行結(jié)果
最大值測試
最小值測試
完整代碼
/**
*@Description: 雙邊匹配決策算法
*/
package com.lulei.twosided.matching.decisionmaking;
import com.lulei.util.JsonUtil;
public class TwoSidedDecision {
private int num = 10;//個體數(shù)目
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: 設(shè)置雙邊決策個體個數(shù)
*/
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: 設(shè)置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: 計算最優(yōu)決策
*/
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: 特定步長比較，返回值確認(rèn)是否發(fā)生交換
*/
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) {//交換后的分?jǐn)?shù)不小于交換前的
//交換后的分?jǐn)?shù)大于交換前的或者交換后的差值大于交換前的
if (score1 < score2 || between2 > between1) {
decisionArray[a1] = b2;
decisionArray[a2] = b1;
return true;
}
}
} else { //最后的得分最小
if (score1 >= score2) {//交換后的分?jǐn)?shù)不小于交換前的
//交換后的分?jǐn)?shù)大于交換前的或者交換后的差值大于交換前的
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("最優(yōu)決策");
System.out.println(JsonUtil.parseJson(test.getDecisionArray()));
System.out.println("決策得分");
System.out.println(test.getScoreSum());
}
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java使用Optional實現(xiàn)優(yōu)雅避免空指針異常
空指針異常（NullPointerException）可以說是Java程序員最容易遇到的問題了。為了解決這個問題，Java?8?版本中推出了?Optional?類，本文就來講講如何使用Optional實現(xiàn)優(yōu)雅避免空指針異常吧2023-03-03
這篇文章主要介紹了java讀取properties文件的方法,實例分析了java操作properties配置文件的相關(guān)技巧,需要的朋友可以參考下2015-05-05
Mybatis的sql語句執(zhí)行異常后打印到日志問題
文章介紹了一種Mybatis異常日志打印方案,主要通過Mybatis攔截器獲取執(zhí)行的sql語句,并利用ThreadLocal存儲,以避免多線程下的sql語句覆蓋問題,當(dāng)異常發(fā)生時,從ThreadLocal中取出sql語句并打印到單獨的日志文件中,方便數(shù)據(jù)恢復(fù),該方案經(jīng)過壓力測試2024-10-10
Maven 私服是一種特殊的Maven遠(yuǎn)程倉庫,它是架設(shè)在局域網(wǎng)內(nèi)的倉庫服務(wù),本文就來介紹一下Maven私服倉庫Nexus配置小結(jié),具有一定的參考價值,感興趣的可以了解一下2024-08-08
這篇文章主要介紹了Java中的Semaphore源碼分析,Semaphore是一個訪問公共資源的線程數(shù)量如限流、停車等,它是一個基于AQS實現(xiàn)的共享鎖,主要是通過控制state變量來實現(xiàn),需要的朋友可以參考下2023-11-11
這篇文章主要介紹了java web激活郵箱并找回密碼，在項目中要實現(xiàn)用戶注冊的郵箱激活以及忘記密碼重置密碼功能，感興趣的小伙伴們2015-11-11
本文通過使用Arthas工具對一個bug進(jìn)行分析,發(fā)現(xiàn)該bug的原因是不同類型的動態(tài)代理（JDK和CGlib）實現(xiàn)機(jī)制的不同導(dǎo)致的2025-01-01
這篇文章主要給大家介紹了關(guān)于如何在Java中為日期增加一天的多種方法,在JAVA業(yè)務(wù)代碼中,經(jīng)常會遇到通過指定時間,增加指定天數(shù)的業(yè)務(wù)需求,需要的朋友可以參考下2023-07-07
Selenium?是目前用的最廣泛的Web?UI?自動化測試框架，本文給大家介紹下Java?Selenide使用，感興趣的朋友一起看看吧2022-01-01
今天小編就為大家分享一篇Java關(guān)于含有繼承類的成員初始化過程講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-04-04