JAVA实现双边决策的示例

现实生活中存在很多问题，比如商品买卖如何实现商家利润最大化？大学生招生录取如何实现整体效果最好？病人医生如何实现整体服务水平最高等？这些我们都可以把他统一的转化为双边决策问题。下面先说说自己对双边决策的理解。

双边决策——个人理解

为了帮助大家理解，我用一个简单的例子介绍什么是双边决策，加入现在市场上有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()); 
  } 
 
} 

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。