二分匹配的贪心算法
Greedy algorithm for bipartite matching
所以我遇到了一个问题，其中有 'n' 名飞行员和 'm' 架飞机。每个飞行员都有一份他可以驾驶的飞机的清单。一名飞行员一次只能驾驶一架飞机。您必须确定可以同时飞行的最大飞机数量。标准的二分匹配问题（我后来才知道）。
在比赛中，我想出了一个贪心算法如下：
While there are planes in the graph :
1)Select a plane which can be flown by minimum number of pilots
2)Greedily allocate a pilot to that plane (from the ones who can fly it)
3)Remove both the plane and the allocated pilot from the graph
一般来说，对于二分匹配问题，我提出如下算法：
While there are nodes in the right set of the bipartite graph :
1)Select a node from the right set with minimum incoming degree
2)Greedily match it with ANY node from the left set (which has an edge to it)
3)Remove both these nodes from the graph( this would also involve decreasing the incoming degree of all nodes on the right to which this node has an edge to)
我在数学上并不精通，无法证明这个算法的正确性，想了很多也没有想出一个反例。
所以我的具体问题是，这是标准算法还是已知算法，还是我犯了一些我看不到的明显错误？
如果您愿意，请随时编辑我的问题以使其更清楚。谢谢。
贪心法不适用于二分匹配。您可能已经猜到的问题是 "selecting any node on the left"。
这是一个示例 - 左侧的节点是 A、B、C 和 D，右侧的节点是 x、y、z、t。将 A、B、C 中的每一个与 x、y、z 中的每一个连接起来（这里有 9 个边），然后将 D 与 t 连接起来，将 A 与 t 连接起来。结果，右侧有 3 个节点，入度为 3(x, y, z)，一个节点入度为 2(t)。所以你选择 t 然后你随机选择左边的一个节点 - 这可能是 A 或 D。问题是如果你 select A，你的最大匹配大小将是 3，而真正的答案是 4(通过 selecting D).
没有理由使用贪心算法！如果你不能证明它的正确性，那么它就是假的。例如，这里的贪心算法失败了，因为它的输出取决于顶点的顺序。
你应该阅读这篇文章：https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Algorithms_and_computational_complexity
例如，有一个有效的二分图算法：Hopcroft-Karp
反例：
a1 a2 a3 a4 a5
p1 x x
p2 x x x x
p3 x x x x
p4 x
p5 x x x
a5 首先被 select 编辑。随机 select 飞行员，可能是 p5。如果是，p4没有平面
我还对通过 Google Code Jam 2018 round 2 测试的二分匹配做了一个贪婪的解决方案，总体来说非常好，但并非完全完美。它会通过 Jur 的测试用例。与 post 作者的不同之处在于我在所有节点中进行选择——在本例中是飞行员和飞机。所以在 Jur 的情况下，p4 将是我的第一选择。如果我有几个相似重要性的顶点，我
其中我 select 链接到最少连接节点的任何节点。我连接到连接最少的对方。
我做了一个程序来测试它与二分匹配与流的对比，发现它有时会出错。有趣的是，它在随机生成的数据上出错的频率在很大程度上取决于维度。对于 n=m=20，它得到了 220 的 200k 个随机生成的案例，但更准确的版本是错误的。对于 n=m=400，在 500k 个这样的案例中，1 个是错误的。
但它并不比经典的基于流的解决方案更快。
这是一个错误的案例
3 - 1 - -
1 3 - - -
- 1 3 1 1
- - 1 3 1
1 1 - - -
3 代表由我的贪心算法 select 编辑的边，1 代表不是的边。 Here's my code in C++.
所以我遇到了一个问题，其中有 'n' 名飞行员和 'm' 架飞机。每个飞行员都有一份他可以驾驶的飞机的清单。一名飞行员一次只能驾驶一架飞机。您必须确定可以同时飞行的最大飞机数量。标准的二分匹配问题（我后来才知道）。
在比赛中，我想出了一个贪心算法如下：
While there are planes in the graph :
1)Select a plane which can be flown by minimum number of pilots
2)Greedily allocate a pilot to that plane (from the ones who can fly it)
3)Remove both the plane and the allocated pilot from the graph
一般来说，对于二分匹配问题，我提出如下算法：
While there are nodes in the right set of the bipartite graph :
1)Select a node from the right set with minimum incoming degree
2)Greedily match it with ANY node from the left set (which has an edge to it)
3)Remove both these nodes from the graph( this would also involve decreasing the incoming degree of all nodes on the right to which this node has an edge to)
我在数学上并不精通，无法证明这个算法的正确性，想了很多也没有想出一个反例。 所以我的具体问题是，这是标准算法还是已知算法，还是我犯了一些我看不到的明显错误？
如果您愿意，请随时编辑我的问题以使其更清楚。谢谢。
贪心法不适用于二分匹配。您可能已经猜到的问题是 "selecting any node on the left"。
这是一个示例 - 左侧的节点是 A、B、C 和 D，右侧的节点是 x、y、z、t。将 A、B、C 中的每一个与 x、y、z 中的每一个连接起来（这里有 9 个边），然后将 D 与 t 连接起来，将 A 与 t 连接起来。结果，右侧有 3 个节点，入度为 3(x, y, z)，一个节点入度为 2(t)。所以你选择 t 然后你随机选择左边的一个节点 - 这可能是 A 或 D。问题是如果你 select A，你的最大匹配大小将是 3，而真正的答案是 4(通过 selecting D).
没有理由使用贪心算法！如果你不能证明它的正确性，那么它就是假的。例如，这里的贪心算法失败了，因为它的输出取决于顶点的顺序。
你应该阅读这篇文章：https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Algorithms_and_computational_complexity
例如，有一个有效的二分图算法：Hopcroft-Karp
反例：
a1 a2 a3 a4 a5
p1 x x
p2 x x x x
p3 x x x x
p4 x
p5 x x x
a5 首先被 select 编辑。随机 select 飞行员，可能是 p5。如果是，p4没有平面
我还对通过 Google Code Jam 2018 round 2 测试的二分匹配做了一个贪婪的解决方案，总体来说非常好，但并非完全完美。它会通过 Jur 的测试用例。与 post 作者的不同之处在于我在所有节点中进行选择——在本例中是飞行员和飞机。所以在 Jur 的情况下，p4 将是我的第一选择。如果我有几个相似重要性的顶点，我 其中我 select 链接到最少连接节点的任何节点。我连接到连接最少的对方。
我做了一个程序来测试它与二分匹配与流的对比，发现它有时会出错。有趣的是，它在随机生成的数据上出错的频率在很大程度上取决于维度。对于 n=m=20，它得到了 220 的 200k 个随机生成的案例，但更准确的版本是错误的。对于 n=m=400，在 500k 个这样的案例中，1 个是错误的。
但它并不比经典的基于流的解决方案更快。
这是一个错误的案例
3 - 1 - -
1 3 - - -
- 1 3 1 1
- - 1 3 1
1 1 - - -
3 代表由我的贪心算法 select 编辑的边，1 代表不是的边。 Here's my code in C++.