There are many problems in real life, such as how to maximize merchant profits by buying and selling goods? How to achieve the best overall results in college student enrollment? How can a patient doctor achieve the highest overall service level, etc. We can all transform these into bilateral decision-making issues in a unified manner. Let’s first talk about your understanding of bilateral decision-making.
Bilateral decision-making – personal understanding
To help everyone understand, I will use a simple example to introduce what bilateral decisions are. There are 10 customers on the market, namely A0, A1, A2, A3, A4, A5, A6, A7, A8, A9. There are products on the market, namely B0, B1, B2, B3, B4, B5, B6, B7, B8, and B9. Now, these 10 products are required to be distributed to these 10 customers, and the overall satisfaction is required. Of course, each customer scores each product differently. Customers with N products are satisfied with AMBN. So how to allocate these products to make the overall satisfaction the highest? This topic is a bilateral decision-making issue.
Algorithm introduction
There are many algorithms for implementing bilateral decision-making. Here is a way to think of oneself (if there is similarity, it is purely coincidence). This algorithm was thought of based on an article about genetic algorithms I wrote before. This algorithm requires that the number of customers and products must be consistent, and it is a one-to-one relationship. If the number is inconsistent or a pair of N (N is a specific value), we can use this algorithm by building a virtual product (customer). Let me briefly introduce the algorithm idea:
1) We first choose an allocation plan. Here we do not assume that the initial allocation plan is to allocate M products to M customers;
2) We set the comparison step step to 1;
3) Determine whether the step exceeds the length of the array. If it exceeds the end algorithm, if it does not exceed the next step, continue to execute the next step;
4) Compare the two customers under the step step size, assuming that their allocation plan is switched. If the satisfaction after the adjustment is greater than the satisfaction before the adjustment, switch it, otherwise keep it as it is, move the comparison position one backward to continue to step 4);
5) There is no allocation plan that can be adjusted under this step, add 1 to the step;
6) Jump to step 3) and continue to execute.
In the above algorithm description, we focus on step 4). Here we assume that the product allocated by the first customer is product No. 1, and the product allocated by the second customer is product No. 2, and their satisfaction with the product is A1B1 and A2B2, respectively. At this time, the overall satisfaction of the two customers is SCORE1=A1B1+A2B2. Here we compare their allocation plan, that is, the product allocated by the first customer is product No. 2, and the product allocated by the second customer is product No. 1, and at this time their satisfaction with the product is A1B2 and A2B1, respectively. The overall satisfaction of these two customers is SCORE2=A1B2+A2B1. If SCORE1 is less than SCORE2, then we change the allocation strategy, otherwise we maintain the original allocation strategy.
Java code analysis
The above introduction may not be too specific, or we don’t know how to implement it with JAVA. Let’s break down the implementation:
1) When writing an algorithm, we first need to define some constants, save allocation schemes, etc.:
public class TwoSidedDecision { private int num = 10;//number of individuals private boolean maxFlag = true;//whether to find the maximum value private int[][] scoreArray;//Mutual evaluation score between AB private int[] decisionArray;//How to choose B}There is a maxFlag attribute here. Its function is to identify whether our bilateral decisions should be taken as the maximum or minimum. True represents the maximum value, false represents the minimum value; num is used to identify the number of individuals, scoreArray array is used to represent user satisfaction with the product, decisionArray is used to save the allocation plan of the product, decisionArray[0] means that the product allocated by the customer with the number 0 is decisionArray[0];
2) Before running the algorithm, we need to set the number of individuals
public void setNum(int num) { if (num < 1) { System.out.println("num must be greater than 0"); return; } this.num = num; } 3) Customers score the product satisfaction and determine the initial allocation plan
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]; //Initial decision, diagonal for (int i = 0; i < num; i++) { decisionArray[i] = i; } decision(); } 4) Then perform step 4) in the algorithm description to confirm whether the allocation plan is adjusted
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]; //The sum of the original two scores int score1 = scoreArray[a1][b1] + scoreArray[a2][b2]; int between1 = Math.abs(scoreArray[a1][b1] - scoreArray[a2][b2]); //The sum of the two scores after exchange int score2 = scoreArray[a1][b2] + scoreArray[a2][b1]; int between2 = Math.abs(scoreArray[a1][b2] - scoreArray[a2][b1]); if (maxFlag) { //The maximum final score is if (score1 <= score2) {//The score after exchange is not less than the previous exchange //The score after exchange is greater than the previous exchange or the difference after exchange is greater than the previous exchange if (score1 < score2 || between2 > between1) { decisionArray[a1] = b2; decisionArray[a2] = b1; return true; } } } else { //The final score is the smallest if (score1 >= score2) {//The score after exchange is not less than the before exchange //The score after exchange is greater than the before exchange or the difference after exchange is greater than the before exchange if (score1 > score2 || between2 > between1) { decisionArray[a1] = b2; decisionArray[a2] = b1; return true; } } } return false; } The return value of this method is to confirm whether the switching occurs at this step size. If the switching occurs at this step size, we can compare the next step size. This completes the bilateral decision-making algorithm. Let’s take a look at the test results below.
Running results
Maximum test
Minimum value test
Complete code
/** *@Description: Bilateral matching decision algorithm*/ package com.lulei.twosided.matching.decisionmaking; import com.lulei.util.JsonUtil; public class TwoSidedDecision { private int num = 10;//number of individuals private boolean maxFlag = true;//whether to find the maximum value private int[][] scoreArray;//Mutual evaluation score between AB private int[] decisionArray;//How to choose B public boolean isMaxFlag() { return maxFlag; } public void setMaxFlag(boolean maxFlag) { this.maxFlag = maxFlag; } /** * @return * @Author:lulei * @Description: Get the final decision*/ public int[] getDecisionArray() { return decisionArray; } /** * @return * @Author:lulei * @Description: Get the rating for the decision*/ 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: Set the number of bilateral decision-making individuals */ 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: Set the evaluation between individuals in Class A and individuals in Class 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]; //Initial decision, diagonal for (int i = 0; i < num; i++) { decisionArray[i] = i; } decision(); } /** * @Author:lulei * @Description: Calculate the optimal decision*/ private void decision() { if (scoreArray == null || decisionArray == null) { System.out.println("please init scoreArray"); } for (int stepSize = 1; stepSize < num; stepSize++) { //Exchange while (compare(stepSize)); } } /** * @param stepSize * @return * @Author:lulei * @Description: Comparison of specific step size, return value to confirm whether exchange occurs*/ 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]; //The sum of the original two scores int score1 = scoreArray[a1][b1] + scoreArray[a2][b2]; int between1 = Math.abs(scoreArray[a1][b1] - scoreArray[a2][b2]); //The sum of the two scores after exchange int score2 = scoreArray[a1][b2] + scoreArray[a2][b1]; int between2 = Math.abs(scoreArray[a1][b2] - scoreArray[a2][b1]); if (maxFlag) { //The maximum final score is if (score1 <= score2) {//The score after exchange is not less than the previous exchange //The score after exchange is greater than the previous exchange or the difference after exchange is greater than the previous exchange if (score1 < score2 || between2 > between1) { decisionArray[a1] = b2; decisionArray[a2] = b1; return true; } } } else { //The minimum final score if (score1 >= score2) {//The score after exchange is not less than the before exchange //The score after exchange is greater than the before exchange or the difference after exchange is greater than the before exchange 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,5}, {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}, {9,0,1,2,3,4,5,6,7}, {9,0,1,2,3,4,5,6,7}}; TwoSidedDecision test = new TwoSidedDecision(); test.setNum(10); test.setMaxFlag(false); test.setScoreArray(scoreArray); System.out.println("Optimal Decision"); System.out.println(JsonUtil.parseJson(test.getDecisionArray())); System.out.println("Decision Score"); System.out.println(test.getScoreSum()); } }The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.