Обсуждение:Задача коммивояжёра
Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
 | 18-20 мая 2005 года сведения из статьи «Задача коммивояжёра» появлялись на заглавной странице в колонке «Знаете ли вы». В колонке был представлен текст: «Классическая задача коммивояжёра заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. Методы решения этой задачи, по существу, сводятся к организации полного перебора вариантов; никакого эффективного алгоритма решения не известно». С полным выпуском колонки можно ознакомиться в архиве рубрики «Знаете ли вы». |  |
NP-полнота править
Задача коммивояжёра в указанной формулировке является NP-трудной, а не NP-полной.
Algo 13:28, 26 сентября 2006 (UTC)
- Напишите об этом в статье, пожалуйста. --Amoses @ 12:35, 27 сентября 2006 (UTC)
программа править
перевод править
 | Эта статья содержит текст, переведённый из статьи Problem des Handlungsreisenden из раздела Википедии на немецком языке. Список авторов находится на странице истории правок оригинальной статьи. Информация о включении текстов из других источников и их авторах может быть размещена на странице обсуждения оригинальной статьи. |
Пример реализации на php для вычисления оптимального маршрута править
добавить внешнюю ссылку на www.route-p.ru 95.221.99.9 16:53, 20 января 2012 (UTC)
Замкнутый и незамкнутый варианты задачи править
При описании сведения задачи к незамкнутому виду ничего не сказано про путь от искусственной вершины n до первоначальной вершины 0 (Сn,0). --195.2.89.146 12:44, 29 августа 2012 (UTC)Очень злой программист
статья непригодна править
Необходимо
точно сформулировать постановку задачи ("Например, симметричную задачу можно представить в виде множества ребер V." суть не "ДАНО", а "НАЙТИ" )
и
привести легко воспроизводимый пример, как в статьях "Метод Галёркина" здесь, в Вике, или "Линейное программирование" в Корне (Справочник по математике для…, пункты 11.4-1,11.4-2)
А данная статья для изучения «Задачи коммивояжёра» и применения непригодна.
109.194.34.49 08:10, 5 декабря 2014 (UTC) Альберт.
Сложность алгоритма править
"...существует маршрутов для асимметричной и маршрутов для симметричной задачи коммивояжера. Таким образом, размер пространства поиска зависит экспоненциально от количества городов."
Вроде как факториал растёт быстрее, чем экспонента. Возможно, я чего-то не понимаю, но всё выглядит так, как будто зависимость факториальная (может, есть более удачное слово). Стоит либо пояснить, откуда берётся экспоненциальная зависимость, либо написать факториальная (или более удачное слово). 188.227.78.59 15:29, 8 декабря 2014 (UTC)Валерка