Задача коммивояжера и венгерский метод

[hclubmk]

Доброго времени суток. Вопрос возник по поводу предлагаемого варианта решения указанной задачи. Хочу попросить разъяснения если метод применим, или подтверждения, что это - фейк.

PS
Извиняюсь, если вопрос запостил не в ту ветку.

[Евгений Машеров]

Во-первых, это не решение. (далее вытащенное из кэша гугля, может, сейчас автором что-то изменено - но пока по ссылке недоступно)

Цитата:

3. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
...
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.

Конечно, методом проб и ошибок рано или поздно всё решается. Но обычно под решением понимают нечто более конкретное. То есть решения, собственно, нет. Как и применения венгерского метода, который не "метод проб и ошибок", отнюдь.

А, во-вторых, даже если правильно применить венгерский метод, получив оптимальное решение задачи о назначении, это решением ЗК не будет. Потому как требуемый в ЗК единственный обход в задаче о назначении не требуется и, как правило, не достигается. А получается некоторый набор циклов. Вплоть до n циклов длины 1. Попытки свести ЗК к серии задач о назначении, в которых искусственно размыкаются циклы, известны. В худшем случае всё та же экспонента, что и в "ветвях и границах", а практически вычислительные затраты растут.

[hclubmk]

Евгений Машеров
Спасибо за опровержение - были некоторые колебания, но теперь ещё больше утвердился в том, что построение ЗК не вяжется с задачами паросочетания.