Внедрение венгерского метода, описанного Papadimitriou & Steiglitz

Question

Если вы реализовали венгерский метод точно , как показано на рис. 11-2 из Комбинаторная оптимизация: алгоритмы и сложность , удалось ли вам без изменения псевдокода в любом [значительный] способ? В частности, я имею в виду исправленное издание Dover за 1998 год, которое обновлено в отношении файла с ошибками от октября 2000 года, размещенного на веб-сайте Steiglitz.

Приемлемый ответ: «Я реализовал это, и оно отлично работает». Или: «Я реализовал это, но ему нужно то-то и то-то и то-то». В первом случае я хотел бы продолжить и без того обширное копание и отладку моего кода. (В любом случае, я собираюсь сделать это.) В последнем случае у меня было бы немного понимания, которое могло бы заставить мою собственную реализацию работать правильно.

Если вы реализовали венгерский метод, но не использовали CO: AaC или не использовали C без сторонних библиотек, вы все равно более чем рады предложить ответ. На самом деле, если вы супер-гений, который может просто изучить рис. 11-2 и указать на ошибку или упущение P & S, я хотел бы услышать от вас, и держу пари, что они тоже :-)

Редактировать: Вот книга в Google Книгах. Венгерский метод см. На стр. 251-252. Псевдокод для процедуры augment() см. На стр. 224. Объяснение структур данных см. На окружающих страницах. В идеале у вас есть физическая книга, так как версия Google Книг предсказуемо неполная.

Обновление:

После более тщательного тестирования моей реализации и более тщательного изучения псевдокода и текста книги, я думаю Я решил некоторые проблемы с самим псевдокодом. Была пара новых опечаток. Я связался с профессором Стейглицем, который ведет файл с ошибками на своей домашней странице в Принстоне, и он сказал, что рассмотрит мои записи, когда у него будет больше времени в конце семестра в декабре январь. (Извините всех, кто ожидал решения к концу года. Я предположил, что декабрь - это конец семестра для Принстона, но на самом деле это январь.)

Обновление:

Prof. Штейглиц разместил мой пакет с кодами и документацией в своем веб-пространстве в Принстоне. Смотрите мой ответ ниже для ссылки.

Answer 1

Прошло довольно много времени с тех пор, как я открыл этот вопрос, и я не получил ответа от профессора Штайглица (что вполне понятно, так как я уверен, что он занят практически 24/7, если не работой) затем с более счастливыми вещами, чем проверка предполагаемых исправлений некоторых незнакомцев :-)), так что я собираюсь продолжить и опубликовать мои предполагаемые ошибки, которые, при учете, позволяют реализовать псевдокод P & S, рисунок 11-2, для получения правильных выход.

[...]

И, наконец, для всех, кто заинтересовался, я только что разместил пакет с кодами и документацией своей собственной реализации здесь, на share1t.com. (Справедливое предупреждение: без загрузки он будет работать только 15 дней. После этого они удаляют отправленные файлы.) Этот пакет включает в себя гораздо более читаемую версию PDF (читаемую и правильно набранную с pdflatex) из ошибок Приложение, которое я даю выше.

И ... я думаю, это все. Я надеюсь, что это полезно.

Обновление:

Prof. Steiglitz разместил мой пакет с кодами и документацией на своей веб-странице Publications .