文档章节

JAVA实现双边决策

一贱书生
 一贱书生
发布于 2017/04/16 20:31
字数 2025
阅读 7
收藏 0

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

 

双边决策——个人理解

      为了帮助大家理解,我用一个简单的例子介绍什么是双边决策,加入现在市场上有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)在写算法的时候,我们首先需要定义一些常量、保存分配方案等:

 

[java] view plain copy

 print?

  1. public class TwoSidedDecision {  
  2.     private int num = 10;//个体数目  
  3.     private boolean maxFlag = true;//是否求最大值  
  4.     private int[][] scoreArray;//AB之间的互评得分  
  5.     private int[] decisionArray;//A选择B的方式  
  6. }  

      这里有一个maxFlag属性,他的作用是用来标识我们的双边决策是要取最大值还是要取最小值,true表示最大值,false表示最小值;num用来标识个体的个数,scoreArray数组用来表示用户对商品的满意度,decisionArray用来保存商品的分配方案,decisionArray[0]表示编号为0的顾客分配的商品是decisionArray[0];

 

2)在运行算法之前,我们需要设置个体数目

 

[java] view plain copy

 print?

  1. public void setNum(int num) {  
  2.     if (num < 1) {  
  3.         System.out.println("num must be greater than 0");  
  4.         return;  
  5.     }  
  6.     this.num = num;  
  7. }  


3)顾客对商品进行满意度打分并确定初始分配方案

 

[java] view plain copy

 print?

  1. public void setScoreArray(int[][] scoreArray) {  
  2.     if (scoreArray == null) {  
  3.         System.out.println("scoreArray is null");  
  4.     }  
  5.     if (!(scoreArray.length == num && scoreArray[0].length == num)) {  
  6.         System.out.println("scoreArray`s must be " + num);  
  7.     }  
  8.     this.scoreArray = scoreArray;  
  9.     decisionArray = new int[num];  
  10.     //初始决策,对角线  
  11.     for (int i = 0; i < num; i++) {  
  12.         decisionArray[i] = i;  
  13.     }  
  14.     decision();  
  15. }  

 

 

4)然后进行算法描述中的第4)步,确认分配方案是否对调

 

[java] view plain copy

 print?

  1. private boolean compare(int stepSize) {  
  2.     for (int i = 0; i < num - stepSize; i++) {  
  3.         int a1 = i;  
  4.         int a2 = i + stepSize;  
  5.         int b1 = decisionArray[a1];  
  6.         int b2 = decisionArray[a2];  
  7.         //原始两个得分之和  
  8.         int score1 = scoreArray[a1][b1] + scoreArray[a2][b2];  
  9.         int between1 = Math.abs(scoreArray[a1][b1] - scoreArray[a2][b2]);  
  10.         //交换后的两个得分之和  
  11.         int score2 = scoreArray[a1][b2] + scoreArray[a2][b1];  
  12.         int between2 = Math.abs(scoreArray[a1][b2] - scoreArray[a2][b1]);  
  13.         if (maxFlag) { //最后的得分最大  
  14.             if (score1 <= score2) {//交换后的分数不小于交换前的  
  15.                 //交换后的分数大于交换前的或者交换后的差值大于交换前的  
  16.                 if (score1 < score2 || between2 > between1) {  
  17.                     decisionArray[a1] = b2;  
  18.                     decisionArray[a2] = b1;  
  19.                     return true;  
  20.                 }  
  21.             }  
  22.         } else { //最后的得分最小  
  23.             if (score1 >= score2) {//交换后的分数不小于交换前的  
  24.                 //交换后的分数大于交换前的或者交换后的差值大于交换前的  
  25.                 if (score1 > score2 || between2 > between1) {  
  26.                     decisionArray[a1] = b2;  
  27.                     decisionArray[a2] = b1;  
  28.                     return true;  
  29.                 }  
  30.             }  
  31.         }  
  32.     }  
  33.     return false;  
  34. }  

 

 

      这个方法的返回值是确认该步长下是否发生对调,如果该步长没有发生对调,我们可以进行下一个步长的比较。这样就完成了双边决策算法,下面我们看一下测试结果。

 

运行结果

最大值测试

img

 

最小值测试

img

 

完整代码

 

[java] view plain copy

 print?

  1.  /**   
  2.  *@Description: 双边匹配决策算法 
  3.  */   
  4. package com.lulei.twosided.matching.decisionmaking;    
  5.   
  6. import com.lulei.util.JsonUtil;  
  7.     
  8. public class TwoSidedDecision {  
  9.     private int num = 10;//个体数目  
  10.     private boolean maxFlag = true;//是否求最大值  
  11.     private int[][] scoreArray;//AB之间的互评得分  
  12.     private int[] decisionArray;//A选择B的方式  
  13.       
  14.     public boolean isMaxFlag() {  
  15.         return maxFlag;  
  16.     }  
  17.   
  18.     public void setMaxFlag(boolean maxFlag) {  
  19.         this.maxFlag = maxFlag;  
  20.     }  
  21.   
  22.     /** 
  23.      * @return 
  24.      * @Author:lulei   
  25.      * @Description: 获得最后的决策 
  26.      */  
  27.     public int[] getDecisionArray() {  
  28.         return decisionArray;  
  29.     }  
  30.       
  31.     /** 
  32.      * @return 
  33.      * @Author:lulei   
  34.      * @Description: 获取决策的评分 
  35.      */  
  36.     public int getScoreSum() {  
  37.         int sum = 0;  
  38.         for (int i = 0; i < num; i++) {  
  39.             sum += scoreArray[i][decisionArray[i]];  
  40.         }  
  41.         return sum;  
  42.     }  
  43.   
  44.     /** 
  45.      * @param num 
  46.      * @Author:lulei   
  47.      * @Description: 设置双边决策个体个数 
  48.      */  
  49.     public void setNum(int num) {  
  50.         if (num < 1) {  
  51.             System.out.println("num must be greater than 0");  
  52.             return;  
  53.         }  
  54.         this.num = num;  
  55.     }  
  56.       
  57.     /** 
  58.      * @param scoreArray 
  59.      * @Author:lulei   
  60.      * @Description: 设置A类个体与B类个体间的评价 
  61.      */  
  62.     public void setScoreArray(int[][] scoreArray) {  
  63.         if (scoreArray == null) {  
  64.             System.out.println("scoreArray is null");  
  65.         }  
  66.         if (!(scoreArray.length == num && scoreArray[0].length == num)) {  
  67.             System.out.println("scoreArray`s must be " + num);  
  68.         }  
  69.         this.scoreArray = scoreArray;  
  70.         decisionArray = new int[num];  
  71.         //初始决策,对角线  
  72.         for (int i = 0; i < num; i++) {  
  73.             decisionArray[i] = i;  
  74.         }  
  75.         decision();  
  76.     }  
  77.       
  78.     /** 
  79.      * @Author:lulei   
  80.      * @Description: 计算最优决策 
  81.      */  
  82.     private void decision() {  
  83.         if (scoreArray == null || decisionArray == null) {  
  84.             System.out.println("please init scoreArray");  
  85.         }  
  86.         for (int stepSize = 1; stepSize < num; stepSize++) {  
  87.             //特定步长下的交换  
  88.             while (compare(stepSize));  
  89.         }  
  90.     }   
  91.       
  92.     /** 
  93.      * @param stepSize 
  94.      * @return 
  95.      * @Author:lulei   
  96.      * @Description: 特定步长比较,返回值确认是否发生交换 
  97.      */  
  98.     private boolean compare(int stepSize) {  
  99.         for (int i = 0; i < num - stepSize; i++) {  
  100.             int a1 = i;  
  101.             int a2 = i + stepSize;  
  102.             int b1 = decisionArray[a1];  
  103.             int b2 = decisionArray[a2];  
  104.             //原始两个得分之和  
  105.             int score1 = scoreArray[a1][b1] + scoreArray[a2][b2];  
  106.             int between1 = Math.abs(scoreArray[a1][b1] - scoreArray[a2][b2]);  
  107.             //交换后的两个得分之和  
  108.             int score2 = scoreArray[a1][b2] + scoreArray[a2][b1];  
  109.             int between2 = Math.abs(scoreArray[a1][b2] - scoreArray[a2][b1]);  
  110.             if (maxFlag) { //最后的得分最大  
  111.                 if (score1 <= score2) {//交换后的分数不小于交换前的  
  112.                     //交换后的分数大于交换前的或者交换后的差值大于交换前的  
  113.                     if (score1 < score2 || between2 > between1) {  
  114.                         decisionArray[a1] = b2;  
  115.                         decisionArray[a2] = b1;  
  116.                         return true;  
  117.                     }  
  118.                 }  
  119.             } else { //最后的得分最小  
  120.                 if (score1 >= score2) {//交换后的分数不小于交换前的  
  121.                     //交换后的分数大于交换前的或者交换后的差值大于交换前的  
  122.                     if (score1 > score2 || between2 > between1) {  
  123.                         decisionArray[a1] = b2;  
  124.                         decisionArray[a2] = b1;  
  125.                         return true;  
  126.                     }  
  127.                 }  
  128.             }  
  129.         }  
  130.         return false;  
  131.     }  
  132.   
  133.     public static void main(String[] args) {  
  134.         int[][] scoreArray = {  
  135.                 {0,1,2,3,4,5,6,7,8,9},  
  136.                 {1,2,3,4,5,6,7,8,9,0},  
  137.                 {2,3,4,5,6,7,8,9,0,1},  
  138.                 {3,4,5,6,7,8,9,0,1,2},  
  139.                 {4,5,6,7,8,9,0,1,2,3,},  
  140.                 {5,6,7,8,9,0,1,2,3,4},  
  141.                 {6,7,8,9,0,1,2,3,4,5},  
  142.                 {7,8,9,0,1,2,3,4,5,6},  
  143.                 {8,9,0,1,2,3,4,5,6,7},  
  144.                 {9,0,1,2,3,4,5,6,7,8}};  
  145.         TwoSidedDecision test = new TwoSidedDecision();  
  146.         test.setNum(10);  
  147.         test.setMaxFlag(false);  
  148.         test.setScoreArray(scoreArray);  
  149.         System.out.println("最优决策");  
  150.         System.out.println(JsonUtil.parseJson(test.getDecisionArray()));  
  151.         System.out.println("决策得分");  
  152.         System.out.println(test.getScoreSum());  
  153.     }  
  154.   
  155. }  

本文转载自:http://blog.csdn.net/xiaojimanman/article/details/50373369

一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
CSDN日报180524——《一个合格的程序员,需要哪些必备技能?》

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/blogdevteam/article/details/80445364 程序人生 | 一个合格的程序员,需要哪些必备技能? 作者:hollischuan...

CSDN官方博客
2018/05/24
0
0
工具|FinalShell,必备终端利器

FinalShell,全平台支持,必备终端利器,国人开发,值得推荐。 FinalShell主页 主要特性 1.多平台支持Windows,Mac OS X,Linux 2.多标签,批量服务器管理. 3.支持登录Ssh和Windows远程桌面. 4...

王诗翔
2018/09/19
0
0
IBM 和 Oracle 改变了游戏:结成 OpenJDK 同盟

编者:Oracle-IBM® OpenJDK 同盟对整个 Java™ 行业产生涟漪效应,这对于 Java 生态系统的健康发展影响如何,评论人士对此褒贬不一。纵观各种观点评述,前 JavaWorld 编辑 Athen O'Shea 的评...

红薯
2011/02/18
3.2K
8
[Java学习探讨]为什么学Java虚拟机的Java程序员更值钱?

[Java学习探讨]为什么学Java虚拟机的Java程序员更值钱? 曾经的我经常害怕处理与JVM相关的异常,对JVM的配置参数也一无所知,那时候我天真地认为,JVM的出现本身就是想让程序员屏蔽实现细节,...

原创小博客
2018/07/19
0
0
阿里巴巴连任 Java 全球管理组织席位

11 月 23 日,阿里巴巴宣布连任 Java 全球管理组织 JCP 最高执行委员会委员,任期从 2018 年 12 月 4 号开始,为期两年。 阿里表示,这意味将有更多中国开发者的声音被引入 Java 规范的制定中...

h4cd
2018/11/26
3K
14

没有更多内容

加载失败,请刷新页面

加载更多

八、RabbitMQ的集群原理

集群架构 写在前面 RabbitMQ集群是按照低延迟环境设计的,千万不要跨越WAN或者互联网来搭建RabbitMQ集群。如果一定要在高延迟环境下使用RabbitMQ集群,可以参考使用Shovel和Federation工具。...

XuePeng77
今天
1
0
mac系统下,brew 安装mysql,用终端可以连接,navicat却连接不上?

问题: 1.报错? 2059 - Authentication plugin 'caching_sha2_password' cannot be loaded: dlopen(../Frameworks/caching_sha2_password.so, 2): image not found 2.自己通过设置,已经把密......

写bug的攻城狮
昨天
2
0
老生常谈,HashMap的死循环

问题 最近的几次面试中,我都问了是否了解HashMap在并发使用时可能发生死循环,导致cpu100%,结果让我很意外,都表示不知道有这样的问题,让我意外的是面试者的工作年限都不短。 由于HashMap...

群星纪元
昨天
5
0
拉普拉斯算子

拉普拉斯算子是二阶微分算子。 我们知道,一维离散信号一阶微分公式如下: 相应的,一维离散信号二阶微分公式如下: 由于图像有x和y两个方向,因此图像信号属于二维离散信号。其在x,y两个...

yepanl
昨天
3
0
记录"正则表达式"

详细请查看我的博客:https://blog.enjoytoshare.club/article/RegularExpression.html 1 写在前面 正则表达式(Regular Expression)在代码中常常简写为regex。正则表达式通常被用来检索、替...

wugenqiang
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部