Задача коммивояжера, ДП по подмножествам — различия между версиями
(→Формулировка задачи:) |
|||
| Строка 1: | Строка 1: | ||
| + | Задача о коммивояжере - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из n точек на плоскости. | ||
| + | |||
== Формулировка задачи: == | == Формулировка задачи: == | ||
Коммивояжер должен посетить N городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей? | Коммивояжер должен посетить N городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей? | ||
Версия 01:54, 13 декабря 2010
Задача о коммивояжере - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из n точек на плоскости.
Формулировка задачи:
Коммивояжер должен посетить N городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
