实施 Papadimitriou 和 Papadimitriou 所描述的匈牙利方法。施泰格利茨

发布于 2024-09-29 06:12:01 字数 1171 浏览 0 评论 0原文

如果您完全实现了匈牙利方法，如组合优化：算法和复杂性的图 11-2 所示，那么您是否在不更改任何 [ 中的伪代码的情况下成功了？重要]方式？具体来说，我指的是修正后的 1998 年 Dover 版本，该版本相对于 Steiglitz 网站上给出的 2000 年 10 月勘误文件来说是最新的。

一个可接受的答案是这样的：“我实现了它，并且它运行得很好。”或者，“我实现了它，但它需要某某在线某某。”在前一种情况下，我知道要继续对我的代码进行广泛的研究和调试。（不过，无论如何我都会这样做。）在后一种情况下，我会有一些洞察力，这可能会使我自己的实现正常工作。

如果您已经实现了匈牙利方法，但没有使用CO:AaC或者没有在没有第三方库的情况下使用C，我们仍然非常欢迎您提供答案。事实上，如果你是一个超级天才，只需检查图 11-2 并指出 P&S 的遗漏或委托错误，我很想听听你的意见，我打赌他们也会的： -)

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

更新：

在对我的实现进行更彻底的测试以及对本书的伪代码和文本进行更彻底的检查之后，我认为我已经解决了伪代码本身的一些问题。有一些新的勘误表。我一直与施泰格利茨教授保持联系，他在普林斯顿大学的主页上维护着勘误表文件，他说他会在~~12月学期末有更多时间时查看我的笔记~~ 一月。（对所有期待年底解决问题的人表示抱歉。我原以为 12 月是普林斯顿大学的学期末，但实际上是一月。）

更新：

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

原文

If you've implemented the Hungarian Method exactly as given in Figure 11-2 of Combinatorial Optimization: Algorithms and Complexity, did you succeed without altering the pseudo-code in any [significant] way? To be specific, I'm referring to the corrected 1998 Dover edition, which is up-to-date with respect to the errata file dated October 2000 given on Steiglitz's website.

An acceptable answer would be along the lines of, "I implemented it, and it works perfectly." Or, "I implemented it, but it needed such-and-such on line so-and-so." In the former case, I'd know to continue the already-extensive delving and debugging of my code. (I'm going to do that anyway, though.) In the latter case, I'd have a bit of insight that might make my own implementation work correctly.

If you've implemented the Hungarian Method, but did not use CO:AaC or did not use C without third-party libraries, you are still more than welcome to offer an answer. In fact, if you're a super-genius who can just examine Figure 11-2 and point out an error of omission or commission by P&S, I'd like to hear from you, and I bet they would, too :-)

Edit: Here's the book on Google Books. For the Hungarian Method, see pages 251-252. For the pseudo-code for the augment() procedure, see page 224. For the explanation of the data structures, see the surrounding pages. Ideally you have the physical book, as the Google Books version is predictably partial.

Update:

After more thorough testing of my implementation and more thorough examination of the book's pseudo-code and text, I think I've resolved some issues with the pseudo-code itself. There were a couple of new errata. I've been in touch with Prof. Steiglitz, who maintains the errata file at his Princeton homepage, and he has said that he will review my notes when he has more time at the end of the semester in ~~December~~ January. (Sorry to anyone who'd been expecting resolution by year's end. I had assumed December was end-of-semester for Princeton, but it's actually January.)

Update:

Prof. Steiglitz has posted my code-&-documentation package to his Princeton webspace. See my answer below for a link.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

完美的未来在梦里 2024-10-06 06:12:01

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

~~[...]~~

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

而且......我想这就是全部。我希望这有用。

更新：

Steiglitz 教授已将我的代码和文档包发布在他的出版物网页。