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

Материал из WikiGrapp
Версия от 14:12, 20 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Задача коммивояжера''' (''Travelling salesman problem'') - Коммивояжер должен посетить ка...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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

Литература

[Лекции],

[Кристофидес]