Заключительные замечания. Следует отметить, что задача коммивояжера является комбинаторной задачей, поскольку число возможных маршрутов экспоненциально зависит от числа городов

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

Ряд задач, представляющих собой разновидность задачи коммивояжера, был поставлен и решен с целью исследовать маршруты движения людей или перевозки товаров. Однако рассмотрение этих прикладных задач отодвигает на второй план одну важную особенность задачи коммивояжера. Основное различие между задачей коммивояжера и другими задачами о кратчайшем пути заключается в том, что в первой из них требуется существование ориентированного цикла, в который ровно один раз входят все узлы сети. Другими важными приложениями задачи коммивояжера являются задачи составления расписаний.

Дополнительная литература

1. Ю. М. Ермолаев и др. Математические методы исследования операций. Киев: “Вища школа”, 1979 г.

2. Д. Филлипс, А. Гарсиа-Диас. Методы анализа сетей. М.:Мир, 1984 г.

3. Н. М. Губин и др. Экономико-математические методы и модели в планировании и управлении в отрасли связи. М.: Радио и связь, 1993 г.