Показать сообщение отдельно
  (#13 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,961
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 30.04.2005, 11:24

tokito пишет:
Цитата:
NP-сложная, да шо вы такое говорите а венгерский алгоритм? а хотя бы симплекс метод? это задача дискретной оптимизации по факту и линейного программирования по сути, а вовсе не теории графов
tokito! Вы очень самоуверенный человек! Свою самоуверенность Вы показали ещё в задаче на переливание:
http://www.hardforum.ru/t54877
Я рад за Вас, что Вы знаете методы мат.программирования. Но к сожалению, они работают не везде и не всегда. Класс NP-полных задач довольно велик (несколько тысяч), и задача коммивояжера - это характерный пример из этого класса. Не верите мне, обратитесь к людям, которым Вы доверяете.
Эгервари я уважаю как человека, но его алгоритм - безнадёга для NP-задач. Читайте учебники по дискретной математике.

STORM пишет:
Цитата:
Вот отлично работающий алгоритм, может быть пригодиться:
ЗАДАЧА КОММИВОЯЖЕРА
STORM! Вы открыли для себя известный метод ветвей и границ в его простейшем варианте. Молодец, так держать!
Применение метода ветвей и границ оправдано только на графах до ~17 вершин, и об этом я здесь уже говорил.

МЕТОДЫ МАТ.ПРОГРАММИРОВАНИЯ НЕ СПОСОБНЫ НАХОДИТЬ ОПТИМАЛЬНОЕ РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА, ОНИ НАХОДЯТ ЛИШЬ СУБОПТИМАЛЬНОЕ РЕШЕНИЕ.
Ответить с цитированием
Ads