所以我遇到了一个问题，其中有'n'飞行员和'm'飞机。每个飞行员都有一张他可以飞行的飞机名单。一名飞行员一次只能飞一架飞机。你必须确定可以同时飞行的最大飞机数量。标准二分配匹配问题（我后来发现）。双方匹配的贪婪算法
的较量中，我想出了一个贪心算法如下：
虽然在图面：
1）选择可以通过最小数量飞行飞机飞行员
2）贪婪地分配一个试点到面（从那些谁可以飞的话）
3）卸下两个平面和一个从图中
通常，对于二分匹配问题，我提出以下算法llocated导频：
虽然有在右组中的二部图的节点：
1）选择从与最小传入度设定权的节点
2）贪婪与任何节点F匹配它从左边的集合（它有一个边缘）
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个边），然后用t连接D，用t连接A。结果你有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
谢谢！出于好奇，如果我包含一个条件，例如“对于右边的最小进入度的节点Y，选择左边的一个节点x，并且Y的边缘是这样的，那么在所有这样的x中，它具有最不传出的程度“？ – Anirudh
不，它不会。但是需要更多时间才能找到反例 –