| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > Задача коммивояжёра динамическим программированием |
| Автор: Salatovec 17.12.2011, 19:08 |
| Народ хелп по сабжу. Есть у кого исходники программы по сей задаче? Уже с месяц с ней дерусь. На бумажке устно решить могу, а вот как запрограммировать... С рекурсиями с детства не дружу ей богу =( Или давайте объясню в чём сложность - может подсобить в написании... |
| Автор: Salatovec 20.12.2011, 20:32 |
| Всё ещё актуально |
| Автор: maxdiver 22.12.2011, 22:31 |
| Скорее всего, на бумажке вы решаете не динамическим программированием, потому что если понять, что это такое - то и запрограммировать это будет несложно. Попробуйте прочитать моё объяснение ниже - надеюсь, у вас получится понять. Кстати, рекурсия здесь не обязательна. Решения динамическим программированием удобно описывать, как заполнение некой таблицы: таблица, в которой есть N строк (от 1 до N) и 2^N столбцов (от 0 до 2^N-1). Каждая клетка таблицы - обозначает некий ответ, если мы посетили некоторый набор вершин, и сейчас стоим в некоторой вершине. А именно, клетка таблицы с координатами (i,j) содержит кратчайший путь, который заканчивается в вершине i. Число j обозначает, какие вершины этот путь посетил. Обычно это делается таким образом: число j рассматривается в двоичной системе счисления, и k-ый его бит обозначает, проходил путь через вершину k или нет. Например, клетка таблицы в строке 3 и столбце 13 обозначает путь, проходивший через вершины 1,3,4 (потому что у числа 13 включены первый, третий и четвёртый биты) и заканчивающийся в вершине 3. Изначально вся таблица заполнена плюс бесконечностью (бесконечность обозначает "нет пути, или мы пока его не нашли"). Только в ячейку (1,0) таблицы мы записываем 0 - это обозначает, что путь, состоящий только из стартовой вершины 1, имеет длину 0. Теперь начинается сам алгоритм. Мы идём по таблице слева направо, сверху вниз. Пусть текущая ячейка таблицы - это ячейка (i,j). Это обозначает, что в этой ячейке записан кратчайший путь до вершины i, при условии, что он проходит через заданные вершины. Тогда мы можем попробовать добавить к этому пути ещё одну вершину. Здесь проще описать алгоритмически: стоя на ячейке (i,j), мы перебираем число k=1..N (обязательно такое, что в числе j бит под номером k нулевой), и пытаемся улучшить значение в ячейке (k, j + 2^k): для этого мы к ячейке (i,j) прибавляем длину ребра (i,k) и, если получившееся число оказалось меньше ячейки (k, j + 2^k), - записываем туда это число. В конце концов, после того, как мы сделаем так все возможные улучшения, у нас получится заполненная таблица. Ответом на задачу будет минимум среди таких чисел: ячейка (i,2^N-1) плюс длина ребра из вершины i в вершину 1. |