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;
}

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

运行结果

最大值测试

JAVA实现双边决策的示例

最小值测试

JAVA实现双边决策的示例

完整代码

 /**
 *@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());
  } 

}

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

时间: 2016-10-22

Java算法之堆排序代码示例

堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor

Java单例模式实现静态内部类方法示例

Singleton是众多设计模式中最容易理解的一种,也是众多设计模式中较为重要的一种设计模式.接下来我们看看具体介绍. Singleton模式实现的重点在于将构造函数私有化(private),并通过提供静态公有函数(public synchronized static xxx getInstance)来获取定义在类中的静态私有成员(private static xxx instance),通过一个简单的判断静态实例是否为空来控制这个类只能够new一次,即控制了一个类只能有单个实例,一般的实现如下

java实现网页爬虫的示例讲解

这一篇目的就是在于网页爬虫的实现,对数据的获取,以便分析. 目录: 1.爬虫原理 2.本地文件数据提取及分析 3.单网页数据的读取 4.运用正则表达式完成超连接的连接匹配和提取 5.广度优先遍历,多网页的数据爬取 6.多线程的网页爬取 7.总结 爬虫实现原理 网络爬虫基本技术处理 网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般只有以下几种情况: 1) 搜索引擎 2) 竞品调研 3) 舆情监控 4) 市场分析 网络爬虫的整体执行流程: 1) 确定一个(多个)种子网页 2) 进

java tostring方法重写代码示例

当需要将一个对象输出到显示器时,通常要调用他的toString()方法,将对象的内容转换为字符串.java中的所有类默认都有一个toString()方法 默认情况下 System.out.println(对象名)或者System.out.println(对象名.toString())输出的是此对象的类名和此对象对应内存的首地址 如果想自定义输出信息必须重写toString()方法 注意事项 1.必须被声明为public 2.返回类型为String 3.方法的名称必须为toString,且无参数

Java连接postgresql数据库的示例代码

本文介绍了Java连接postgresql数据库的示例代码,分享给大家,具体如下: 1.下载驱动jar 下载地址:https://jdbc.postgresql.org/download.html 2.导入jar包 新建lib文件夹,将下载的jar驱动包拖到文件夹中. 将jar驱动包添加到Libraries 3.程序代码如下:HelloWorld.java package test; import java.sql.Connection; import java.sql.DriverManage

Java中Switch用法代码示例

一.java当中的switch与C#相比有以下区别 注:在java中switch后的表达式的类型只能为以下几种:byte.short.char.int(在Java1.6中是这样),  在java1.7后支持了对string的判断 还有一点要注意的是:在java中如果switch的case语句中少写了break;这个关键字,在编译的时候并没有报错.但是在执行的时候会一直执行所有case条件下的语句并不是去判断,所以会一直执行直到遇到break关键字跳出或者一直执行到defaut语句. 还有就是如果

Java正则表达式的语法及示例解析

1匹配验证-验证Email是否正确 Java | 复制 public static void main(String[] args) { // 要验证的字符串 String str = "service@xsoftlab.net"; // 邮箱验证规则 String regEx = "[a-zA-Z_]{1,}[0-9]{0,}@(([a-zA-z0-9]-*){1,}\\.){1,3}[a-zA-z\\-]{1,}"; // 编译正则表达式 Pattern pat

java 生成文字图片的示例代码

本文主要介绍了java 生成文字图片的示例代码,分享给大家,具体如下: import java.awt.Color; import java.awt.Font; import java.awt.FontMetrics; import java.awt.Graphics; import java.awt.Rectangle; import java.awt.image.BufferedImage; import java.io.File; import javax.imageio.ImageIO;

JAVA 文件监控 WatchService的示例方法

概述 java1.7中 提供了WatchService来监控系统中文件的变化.该监控是基于操作系统的文件系统监控器,可以监控系统是所有文件的变化,这种监控是无需遍历.无需比较的,是一种基于信号收发的监控,因此效率一定是最高的:现在Java对其进行了包装,可以直接在Java程序中使用OS的文件系统监控器了. 使用场景 场景一:比如系统中的配置文件,一般都是系统启动的时候只加载一次,如果想修改配置文件,还须重启系统.如果系统想热加载一般都会定时轮询对比配置文件是否修改过,如果修改过重新加载. 场景二