Задача коммивояжера

Задача коммивояжера (Travelling salesman problem) — Коммивояжер должен посетить каждый из [math]\displaystyle{ n }[/math] городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном взвешенном графе требуется найти гамильтонов цикл (или цепь) наименьшего веса (длины).

Данная задача является [math]\displaystyle{ \mathcal{NP} }[/math]-полной; для ее решения не известно эффективного (полиномиального) алгоритма. Важность этой задачи связана с тем, что к ней сводятся многие другие задачи, в связи с чем она играет роль эталонной задачи.

Литература

• Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.