Задача коммивояжёра
2010-11-15 01:02Задача коммивояжёра формулируется так: Для данного списка точек и расстояний между ними, упорядочить точки таким образом, чтобы суммарная длина маршрута, проходящего через них в этом порядке была минимальной (возврат в исходную точку учитывается).
Словарь
| Основная форма: | Задача коммивояжёра |
| Синонимы: | |
| Travelling salesman problem, TSP | |
| Задача коммивояжёра на вики | |
Задача коммивояжёра является одной из самых известных задач, для которых не существует лучшего алгоритма решения, чем полный перебор вариантов. Однако, существуют алгоритмы для некоторых частных случаев, и существуют эвристические алгоритмы, в том числе:
- Основанные на нейросетях (FLEXMAP - A Neural Network For The Traveling Salesman Problem);
- Основанные на Messy GA.
Поскольку эта задача имеет важное практическое значение, и благодаря кажущейся простота ее решения человеком ("а шофер Вася подошел к карте и быстро нарисовал не самый плохой маршрут"), то решение задачи коммивояжёра считается неплохой демонстрацией возможностей искусственного интеллекта (хотя и не связана с ним непосредственно).
Для целей тестирования ПО, решающего задачу коммивояжера, существуют тестовые примеры большой размерности, длина наилучшего пути для которых была подсчитана полным перебором и известна.
