贪心算法之——黑白点的匹配（两种实现方法）
- 2019 年 10 月 3 日
- 筆記
一、题目
设平面上分布着n个白点和n个黑点，每个点用一对坐标（x, y）表示。一个黑点b=（xb,yb）支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw。
若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对）。
在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。
二、解题思路
一看完题目，一开始的思路是先将黑白点分别存入两个数组中，再对两个数组分别进行对x和对y的排序，在实际实验过程中，发现排序完后数组的下标与点不好对应，这样就不容易确定一个点是否已经匹配过。
经过了解查阅后发现了最大匹配问题的算法，和本题类似，而且递归的操作复杂度远小于多次对数组的排序。
而且过多的排序也造成了算法思路难以理清。决定先学习掌握最大匹配度算法再考虑本题…
在查阅了最大匹配度问题的思想后，发现这是一种递归形式的方法，算法需要基于对二分图的遍历算法，这就需要学习DFS或者BFS，所以又去复习了一下这两个算法，在彻底掌握了之后终于可以步入正题了…
（dfs和bfs的执行动态图）
http://5b0988e595225.cdn.sohucs.com/images/20171101/f1f45fe9ca37425ba200180be89624b2.gif
http://5b0988e595225.cdn.sohucs.com/images/20171101/a85c0716fcc847f1915dddfcfd019c01.gif
理解了最大匹配算法后，发现只要在图遍历的基础上，多借助一个matching数组，用来储存各匹配点之间的联系，通过一些剪枝和判断就可以实现。
我选择了DFS进行最大匹配算法的基础算法，DFS是对图做出处理，在空间上需要借助一张邻接矩阵，我的想法是将黑白点问题化作图，再根据题目的要求做出对应的邻接矩阵，这样再通过最大匹配就可以求解出来。
下面主要针对这两个问题讨论并通过具体例子演示最大匹配核心思想。
1、如何将黑白点化作图：
创建一个结构体
黑白点都看作顶点，只通过color进行区别
2、如何求对应邻接矩阵：
对储存所有顶点的结构体数组做两次循环，若满足题目中黑点xy坐标大于白点，即将邻接矩阵该位置置为1。
3、具体流程演示：
上图分析：
通过邻接表可以知道，2能控制4,7,8三点
一开始2就控制了4，跳过2点
接着5控制了7，跳过5点
6控制了7,但是7已经被5控制，这时回到5，
5控制了8，跳过5
这时7没人控制，6控制7，流程结束，匹配度为3。
三、代码（DFS BFS两种实现方法）
1 public class MaxMatching {// 基于DFS 2 3 static int graph[][]; // 邻接表 默认全为0 4 static int n; // 节点数 5 static int visit[]; // 是否访问 6 static int matched[]; // 是否已经匹配，对应的匹配点 7 static vertex V[];//// 结构体数组储存所有黑白 8 9 public class vertex {// 顶点结构体 10 public int color;// 白:0 黑：1 11 public double Vx; 12 public double Vy; 13 } 14 15 public void Init() { 16 System.out.println("输入的黑白点总数为："); 17 Scanner sc = new Scanner(System.in); 18 n = sc.nextInt(); 19 graph = new int[n][n]; // 邻接表 默认全为0 20 visit = new int[n]; // 是否访问 21 matched = new int[n]; // 是否已经匹配，对应的匹配点 22 V = new vertex[n]; 23 InitGraph();// 初始邻接矩阵 24 } 25 26 private void InitGraph() { 27 Scanner sc = new Scanner(System.in); 28 for (int i = 0; i < n; i++) {// 输入黑白点 29 V[i] = new vertex(); 30 System.out.println("please int color/x/y"); 31 V[i].color = sc.nextInt(); 32 V[i].Vx = sc.nextDouble(); 33 V[i].Vy = sc.nextDouble(); 34 } 35 for (int i = 0; i < n; i++) { 36 for (int j = 0; j < n; j++) { 37 if (i != j && (V[i].color == 1) && (V[j].color == 0) && (V[i].Vx > V[j].Vx) && (V[i].Vy > V[j].Vy)) { 38 graph[i][j] = 1; 39 } 40 } 41 } 42 } 43 44 // 显示匹配结果 45 public void show() { 46 Arrays.fill(visit, 0); 47 for (int i = 0; i < n; i++) { 48 if (visit[i] == 0) { 49 if (matched[i] != -1) { 50 System.out.println("(" + V[i].Vx + "," + V[i].Vy + ")与" + "(" + V[matched[i]].Vx + "," 51 + V[matched[i]].Vy + ")" + "匹配"); 52 visit[i] = 1; 53 visit[matched[i]] = 1; 54 } 55 } 56 } 57 } 58 59 /* 60 * dfs实现, params: x:起始的未匹配点 return: 1:找到增广路 0:未找到 61 */ 62 public int dfs_solve(int x) { 63 // 找到一个和节点存在边的点，并且该点在本轮中没有被访问过 64 for (int i = 0; i < n; i++) { 65 if (graph[x][i] != 0 && visit[i] == 0) { 66 visit[i] = 1; // 标记为匹配过 67 // 按照交替路的模式找增广路，增广路相对于交替路的特性是就是，第一个节点和最后一个节点都是未匹配过的节点 68 if (matched[i] == -1 || dfs_solve(matched[i]) == 1) { // 直接跳到matched[i]能够保证匹配边和未匹配边交替 69 // 说明找到了一个未匹配节点，将所有匹配边变为未匹配边，将所有未匹配边变为匹配边，这样匹配边数会加1,这个交换过程通过回溯实现 70 71 matched[x] = i; 72 matched[i] = x; 73 74 System.out 75 .println("(" + V[x].Vx + "," + V[x].Vy + ") 与 " + "(" + V[i].Vx + "," + V[i].Vy + ")" + "匹配"); 76 return 1; 77 } 78 } 79 } 80 return 0; 81 } 82 83 public void hungarian1() { 84 Arrays.fill(matched, -1); 85 int sum = 0; 86 for (int i = 0; i < n; i++) { 87 if (matched[i] == -1) { 88 System.out.println("从 " + "(" + V[i].Vx + "," + V[i].Vy + ")" + " 开始匹配"); 89 Arrays.fill(visit, 0);// 重置浏览数组，用来浏览邻接矩阵当前列 90 sum += dfs_solve(i); 91 } 92 } 93 System.out.println("n"+"最后共有 " + sum + " 匹配项"); 94 show(); 95 } 96 97 public static void main(String[] args) { 98 MaxMatching mm = new MaxMatching(); 99 mm.Init(); 100 mm.hungarian1(); 101 } 102 }
