所以我遇到了一个问题，那就是“ n”名飞行员和“ m”架飞机。每个飞行员都有他可以飞行的飞机清单。一名飞行员一次只能飞行一架飞机。您必须确定可以同时飞行的最大飞机数量。标准的两方匹配问题（稍后我会发现）。
在竞赛中，我提出了如下贪心算法：
虽然图中有平面：
1）选择可以由最少飞行员驾驶的飞机
2）从该能飞行的飞机上向该飞机贪婪地分配一名飞行员]
3）从图中移除飞机和分配的飞行员
通常，对于二分匹配问题，我提出以下算法：
虽然二分图的正确集合中有节点：
1）从右侧集合中选择具有最小传入程度的节点
2）使它与左集合中的任何节点（具有边）进行匹配。
3）从图中移除这两个节点（这也将涉及降低该节点具有边缘的右侧上所有节点的进入程度）
我在数学上不足以证明该算法的正确性，经过大量思考之后，我未能提出一个反例。因此，我的具体问题是，这是一种标准算法还是已知算法，还是我犯了一些看不见的公然错误？
如果您愿意，请随时编辑我的问题以使其更清楚。谢谢。
反例：
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首先被选择。随机选择可能为p5的飞行员。如果是，则p4没有平面。
贪婪的方法不适用于二分法匹配。您可能已经猜到的问题是“选择左侧的任何节点”。
这里是一个示例-左边的节点是A，B，C和D，右边的节点是x，y，z，t。将A，B，C的每个与x，y，z的每个连接（这里有9条边），然后将D与t的连接和A与t的连接。结果，您在右侧有3个节点，它们的度数分别为3（x，y，z）和1个节点，其度数分别为2（t）。因此，您选择t并在左侧随机选择一个节点-可能是A或D。问题是，如果选择A，则最大匹配将为3，而实际答案为4（通过选择D） 。
没有理由使用贪婪算法！如果您不能证明其正确性，那就是错误的。例如，在这里，您的贪婪算法失败了，因为它的输出取决于顶点的顺序。
您应阅读本文：https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Algorithms_and_computational_complexity
例如，有一个有效的二部图算法：Hopcroft-Karp
[我也对通过Google Code Jam 2018第二轮测试的二分匹配做出了贪婪的解决方案，并且总体上非常好，但并非完全无瑕。它将通过Jur的测试用例。与作者不同的是，我在所有节点之间进行选择-在这种情况下，飞行员和飞机都可以选择。因此，在Jur的情况下，p4将是我的首选。如果我有几个具有相似重要性的顶点，在这些节点中，我选择链接到最少连接节点的任何节点。我连接到连接最少的对方。
我制作了一个程序来测试它与流的二分匹配性，发现有时确实出错了。有趣的是，它在随机生成的数据上出错的频率在很大程度上取决于维度。对于n=m=20，它得到的220随机产生的案例的200k与更准确的版本是错误的。对于n=m=400，在这种情况下，在1的500k中是错误的。
但是它没有比传统的基于流程的解决方案快。
这里是一个错误的情况
3 - 1 - -
1 3 - - -
- 1 3 1 1
- - 1 3 1
1 1 - - -
3代表由我的贪婪算法选择的边缘，1代表未被选择的边缘。 Here's my code in C++。