Задача коммивояжера, ДП по подмножествам — различия между версиями
Материал из Викиконспекты
|
|
| (не показано 96 промежуточных версий 9 участников) |
| Строка 1: |
Строка 1: |
| − | Задача о коммивояжере - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из n точек на плоскости.
| + | #перенаправление [[Гамильтоновы графы]] |
| − | | |
| − | == Формулировка задачи: ==
| |
| − | Коммивояжер должен посетить N городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
| |
Текущая версия на 20:48, 9 января 2016
