algorithm - 实现 Papadimitriou 和 Steiglitz 所描述的匈牙利方法

Question

如果您完全实现了组合优化:算法和复杂性的图 11-2 中给出的匈牙利方法，您是否在不更改伪代码的情况下成功了以任何[重要]方式？具体而言，我指的是经过更正的 1998 年 Dover 版本，该版本与 Steiglitz 网站上日期为 2000 年 10 月的勘误表文件相比是最新的。

一个可接受的答案应该是“我实现了它，而且效果很好。”或者，“我实现了它，但它需要某某在线某某”。在前一种情况下，我知道要继续对我的代码进行已经很广泛的研究和调试。 (尽管如此，我还是会这样做。)在后一种情况下，我会有一些洞察力，可能会使我自己的实现工作正常进行。

如果您实现了匈牙利方法，但没有使用CO:AaC 或没有使用没有第三方库的 C，仍然非常欢迎您提供答案。事实上，如果你是一个 super 天才，可以检查图 11-2 并指出 P&S 遗漏或委托(delegate)的错误，我想听听你的意见，我敢打赌他们也会:-)

编辑: Here是 Google 图书上的图书。对于匈牙利方法，请参见第 251-252 页。对于 augment() 过程的伪代码，请参见第 224 页。对于数据结构的解释，请参见周围的页面。理想情况下，您拥有实体书，因为可以预见，Google 图书版本是不完整的。

更新:

在对我的实现进行更彻底的测试以及对本书的伪代码和文本进行更彻底的检查之后，我认为我已经解决了伪代码本身的一些问题。有几个新的勘误表。我一直在与 Steiglitz 教授保持联系，他在他的普林斯顿主页上维护勘误表文件，他说他会在 12 月学期结束时有更多时间查看我的笔记 一月。 (对那些一直期待年底前解决的人感到抱歉。我以为 12 月是普林斯顿的学期末，但实际上是 1 月。)

更新:

教授Steiglitz 已将我的代码和文档包发布到他的普林斯顿网站空间。请参阅下面我的回答以获取链接。

Answer 1

自从我提出这个问题以来已经有一段时间了，我还没有收到 Steiglitz 教授的回音(这是完全可以理解的，因为我敢肯定他几乎 24/7 都很忙，如果不是工作的话然后比验证一些陌生人所谓的错误修复更快乐的事情 :-) )，所以我将继续并发布我所谓的勘误表，当考虑到时，允许 P&S 图 11-2 伪-要实现以产生正确输出的代码。

[...]

最后，对于任何感兴趣的人，我刚刚在 share1t.com 上发布了我自己实现的代码和文档包。 (公平警告:如果没有下载，它只会在那里保留 15 天。之后，他们会删除提交的文件。)这个包包括一个更具可读性的 PDF 版本(使用 pdflatex 可读且正确排版>) 我在上面给出的勘误表附录。

还有……我想就这些吧。我希望这是有用的。

更新:

教授Steiglitz 已在 his Publications webpage 发布了我的代码和文档包.