Задача коммивояжера: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
'''Задача коммивояжера''' (''[[Travelling salesman problem]]'') - Коммивояжер должен посетить каждый из <math>n</math> городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти ''[[кратчайший маршрут]]'', зная расстояния между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном [[взвешенный граф|взвешенном графе]] требуется найти [[гамильтонов цикл]] (или [[гамильтонова цепь|цепь]]) наименьшего [[вес цикл|веса]] ([[длина цепи|длины]]).
'''Задача коммивояжера''' (''[[Travelling salesman problem]]'') Коммивояжер должен посетить каждый из <math>n</math> городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти ''[[кратчайший путь|кратчайший маршрут]]'', зная [[расстояние между вершинами|расстояния]] между каждой парой городов. Математическая постановка этой задачи состоит в следующем: в полном [[взвешенный граф|взвешенном графе]] требуется найти [[гамильтонов цикл]] (или [[гамильтонова цепь|цепь]]) наименьшего [[вес цикла|веса]] ([[длина цепи|длины]]).


Данная задача является ''<math>\mathcal{NP}</math>-полной''; для ее решения не
Данная задача является [[NP-Полная задача|''<math>\mathcal{NP}</math>-полной]]''; для ее решения не
известно эффективного (''полиномиального'') алгоритма.
известно эффективного (''полиномиального'') алгоритма.
Важность этой задачи
Важность этой задачи
Строка 7: Строка 7:
связи с чем она играет роль эталонной задачи.
связи с чем она играет роль эталонной задачи.
==Литература==
==Литература==
[Лекции],  
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.


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

Текущая версия от 13:31, 11 февраля 2011

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

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

Литература

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