https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit#
1.自行车和人匹配问题 (高频 22+次)
Update time ：【 2018-10-19】
2D平面上，有m个人（P），n辆自行车(B)，还有空白（O）满足以下条件
1.m < n
2.不存在两个人，到同一辆自行车距离相等, 距离用abs(x1-x2) + abs(y1-y2)定义
3.每个人尽量找离自己最近的自行车，一旦某辆自行车被占，其他人只能找别的自行车。
例：
OPOBOOP
OOOOOOO
OOOOOOO
OOOOOOO
BOOBOOB
红色的人找到第一行的自行车，距离最近。
蓝色的人离第一行自行车最近，但自行车已经被红色人占有，所以他只能找离他第二近的，右下角的自行车。
问：把人和自行车配对，输出vector<pair<int, int>>每个人对应的自行车. {i, j} 是人i对应自行车j
大米已加， 求问自行车分配问题的思路？
可以搞几个priority_queue<距离，人，车>
然后遍历m个人，n辆车，把m*n个 距离，人，车放入其中。
每次取出距离最小的，看看这个人是否已经分配了自行车
如果没有分配，则可以把这个人和这辆车输出
谢谢楼主的解答！我有一个问题，面试官要求说所有人完成配对时候所走的总路线最小么？lz的解法可以完成配 ...
我印象中面试官没有问 只是问如何给每个人分配一个自行车
|
也可能没理解题目或者楼主的做法 比如下面这个
BOOPBOOOOOOOOOOOOOP
如果先给了左边第一个P最近的B 总 ...33
看来确实是有反例的
我面试时候，面试官的要求是每个人都同时开始找，尽量找自己近的。假设每个人向四周的搜索速度是一样的，算是局部最优。
如果要求变成总距离最短，我的方法就不对啦。
|
思路：attempting 算出所有距离后放进heap里，依次pop出来记录人和车的状态
这道题具体是什么呀？有几个人？人和车配对？
查了半天相关的帖子，我的理解是：貌似就是2D grid，用0代表road，用1代表obstacles，然后B代表bike，用P代表people。然后是有m个人，n个车，m < n
Editor: 是的 车比人多 enum出所有人车匹配并排序 后从小往大排序输出 用双set去重就好 不是难题
所以这道题跟bfs/dfs没关系，就直接heap不停poll,然后用set来记录bike和people被visited 即可
考虑例子：
PO BOOP
OOOOOO
OOOOOO
OOOOOO
BOOOOO
BOOOOO
似乎heap不行？
如果有距离相同的情况的话怎么解呢？只能用匈牙利吗
Editor: 相同情况感觉可以跟面试官讨论
我觉得应该是类似如下情况：
0 P 0
B 0 P
0 0 B v
P代表people，B代表bike，0就是过道，那么这种情况下就只需要enumerate出每一个B和每一P 的abs distance，放进priorityqueue即可。然后用一个char[][]来记录visited。这是我的看法。但如果出现了“1”作为obstacles，就不能直接abs了，因为有障碍物，这个时候我能想到的就是以P为中心用bfs来计算到每一个B的距离，然后再放进heap。不晓得我的想法是否正确。
Editor: 对的
有障碍物就不需要heap了吧？从车开始BFS就行了吧，当然前提是没有tie
请问楼主，第四题匹配的时候，最后的目标是尽量多匹配还是让总的cost最小。
我面试的时候是尽量多匹配，优先安排距离最近的，并不考虑全局最优
恭喜楼主，我记得第四题地里的讨论比较开放，楼主是怎么做的？
当时没有很好的思路，就直接暴力得写了pq + map的解法，看所有匹配的可能。
写完了再跟面试官讨论如何优化，也没有特别好的思路。
最后面试官跟我提了Hungarian algorithm。
Summary:
- 需要跟面试官讨论清楚他需要的最佳匹配是什么
- 如果是要求全局人车距离最短
- 二分图的最佳匹配问题，使用匈牙利算法，参考题目https://blog.csdn.net/u011721440/article/details/38169201
- 发现这里不能使用max flow， 因为这个bipartite is a weighted graph. 参考 https://www.topcoder.com/community/competitive-programming/tutorials/assignment-problem-and-hungarian-algorithm/
- 如果是要求最佳匹配只是给每个人匹配到车，可以用PQ+Map
原题：一组坐标表示人，另一组表示车，车比人多，给每个人匹配最近的车。其中人和车的距离没有tie。
原题还比较简单，最笨的bfs也可以做，坐标数值很大的时候，时间复杂度可能会很高，稍微好一点的是用pq存所有的人车距离，每次poll最小的距离，如果这个人已经匹配到车了继续poll，直到所有人都匹配到车为止。
follow up版本1: 一组坐标表示人，另一组表示车，车比人多，其中人和车的距离有tie（距离两个人最近的车可能是同一辆），给每个人匹配一辆车，要求所有匹配的人车曼哈顿距离加起来最小（全局最优）。
这一问原题的两种方法基本全部gg，因为要求全局最优并且有tie，于是每个人不一定是匹配到距离自己最近的车子。pq方法完全失效，bfs方法无法保证全局最优（距离一个人最近的车可能有多辆，然而单凭bfs无法确定给此人匹配哪辆可以全剧最优）。暴力搜索全部匹配方式，找最小总距离的匹配方式可以确保正确性，但是车和人很多的时候，时间复杂度会很高。目前个人认为这一题面试官的期待做法，应该就是二分图最小带权匹配，KM算法，但是鉴于面试的时候可能很难写出，所以在此希望大家讨论一下有没有其他稍微简单点的办法，因为和正常的二分图匹配不一样，这个已经告诉你那些节点属于哪一边了。
follow up版本2: 一组坐标表示人，另一组表示车，车比人多，其中人和车的距离有tie（距离两个人最近的车可能是同一辆），给每个人匹配一辆车，要求匹配后最大的人车距离最小。
这一问和前面的关系似乎不是很大，不过万能的暴力dfs还是能做，全部匹配方法写出来，找最长距离最小的那个，就是答案，不过和前面一样，没有非常有效的剪枝方法，复杂度很高，所以面试官也不会满意（我同学面试答了这种方法挂掉了）。感觉可以用dp来做，但是没有想出很好的状态表示和转移方程，希望大家讨论！！！！
KM算法参考代码
Provider: null
public class KMAlgorithm {
@Test
public void test() {
// chear[][] graph = new char[][] {
// {'O', 'P', 'O', 'B', 'P', 'O', 'P'},
// {'O', 'O', 'O', 'O', 'O', 'O', 'O'},
// {'B', 'O', 'O', 'B', 'O', 'O', 'B'}
// };
char[][] graph = new char[][] {
{'P', 'O', 'O', 'B', 'P', 'O', 'B'}
};
System.out.println(match(graph));
}
char[][] graph;
List<int[]> bikes;
List<int[]> persons;
int[][] G;
int[] personExpect;
int[] bikeExpect;
boolean[] visitedPerson;
boolean[] visitedBike;
int[] match;
int[] slack;
//return : person[i, j] + bike[i, j]
public List<List<Integer>> match(char[][] graph) {
this.graph = graph;
init();
KM();
List<List<Integer>> res = new ArrayList<>();
for(int i = 0 ; i < match.length ; i++) {
if(match[i] == -1) continue;
int[] person = persons.get(match[i]);
int[] bike = bikes.get(i);
res.add(Arrays.asList(person[0], person[1], bike[0], bike[1]));
}
return res;
}
private void init() {
int rows = graph.length;
int cols = graph[0].length;
persons = new ArrayList<>();
bikes = new ArrayList<>();
for(int i = 0 ; i < rows ; i++) {
for(int j = 0 ; j < cols ; j++) {
if(graph[i][j] == 'P') {
persons.add(new int[] {i, j});
}
if(graph[i][j] == 'B') {
bikes.add(new int[] {i, j});
}
}
}
// build cost graph
G = new int[persons.size()][bikes.size()];
for(int i = 0 ; i < G.length ; i++) {
for(int j = 0 ; j < G[0].length ; j++) {
int[] person = persons.get(i);
int[] bike = bikes.get(j);
int dis = Math.abs(person[0] - bike[0]) + Math.abs(person[1] - bike[1]);
G[i][j] = -dis; // 求最小距离，所以这里权值用负数表示
}
}
personExpect = new int[persons.size()];
bikeExpect = new int[bikes.size()];
visitedPerson = new boolean[persons.size()];
visitedBike = new boolean[bikes.size()];
match = new int[bikes.size()];
Arrays.fill(match, -1);
slack = new int[bikes.size()];
Arrays.fill(slack, Integer.MAX_VALUE);
// init person expectation array
for(int i = 0 ; i < persons.size() ; i++) {
personExpect[i] = G[i][0];
for(int j = 0 ; j < bikes.size() ; j++) {
personExpect[i] = Math.max(personExpect[i], G[i][j]);
}
}
}
boolean find(int person) {
visitedPerson[person] = true;
for(int bike = 0 ; bike < bikes.size() ; bike++) {
if(visitedBike[bike]) continue;
int gap = personExpect[person] + bikeExpect[bike] - G[person][bike];
if(gap == 0) {
visitedBike[bike] = true;
if(match[bike] == -1 || find(match[bike])) {
match[bike] = person;
return true;
}
} else {
slack[bike] = Math.min(slack[bike], gap);
}
}
return false;
}
void KM() {
for(int i = 0 ; i < persons.size() ; i++) {
Arrays.fill(slack, Integer.MAX_VALUE);
// assign bike for each person
while(true) {
Arrays.fill(visitedPerson, false);
Arrays.fill(visitedBike, false);
if(find(i)) break;
// if can not assign one bike to the person, decrease the expectation
int tmp = Integer.MAX_VALUE;
for(int bike = 0; bike < bikes.size() ; bike++) {
if(!visitedBike[bike]) tmp = Math.min(tmp, slack[bike]);
}
for(int person = 0 ; person < persons.size() ; person++) {
if(visitedPerson[person]) {
personExpect[person] -= tmp;
}
}
for(int bike = 0 ; bike < bikes.size() ; bike++) {
if(visitedBike[bike]) {
bikeExpect[bike] += tmp;
} else {
slack[bike] -= tmp;
}
}
}
}
}
}
人车匹配 （见首页，频率 20+）
- 人车匹配，说了bfs和pq，写的pq。follow up有tie怎么办，小哥说第一次出这个题让我自己想怎么处理，就随便说了
