Транспортная задача

Приближенный алгоритм решения транспортной задачи. Решить задачу ком­мивояжера с N городами, последовательно двигаясь из города n в город n+1, соблюдая условие: стоимость проезда между городом n и новым городом n+1 минимальна. Индекс n изменяет значение от 1 до N.

Шаг 0. [Инициализация, т. е. установка в начальное состояние]

TOUR=0; МIN=¥.

Шаг 1. [Посещение всех городов]

For I=1 to (N—1)

Шаг 2. [Выбор следующего пути]

Определение минимальной стоимости проезда из города n во все

оставшееся города и определение города n+1.

Шаг 3. [Вычисление стоимости проезда]

Вычисляем стои­мость COST (Т (Р)) как сумму всех стоимостей от начальной точки до точки V+1.

Шаг 4. [Окончание цикла]

Ш аг 5 [Вывод результатов и окончание программы]

На рис. 5.4а изображена сеть городов с соответствующими стоимостями проезда, а рис.5.4б - 5.4е иллюстрируют построение тура коммивояжера для эвристического алгоритма, начинающегося с вершины 1; пройдённые вершины обозначены черным квадратиком, а непройденные — кружком.

Алгоритм эвристики дает общий проезд со стоимостью 14, а в гл.3 решение исчерпывающего алгоритма дает общий проезд со стоимостью 13. Ясно, что эвристический алгоритм не всегда находит общий проезд с минимальной стоимостью.

Обычно грубые алгоритмы очень быстры и интуитивно привлека­тельны, но, как мы заметили, они не всегда дают оптимальное решение задачи. Нам повезло, и мы смогли легко найти контрпример для алгоритма эвристического метода транспортной задачи. Однако не всегда можно легко показать, что грубый алгоритм не работает. Разумеется, если мы считаем, что наш грубый алгоритм работает всегда, то мы должны доказать, что это так.

Эвристический алгоритм транспортной задачи основан на идее подъема. Цель — найти общий проезд с минимальной стоимостью. Задача сведена к набору частных целей — найти на каждом шаге «самый дешевый» город, чтобы посетить его следующим. Алгоритм не строит плана вперед; текущий выбор де­лается безотносительно к последующим выборам.

Оптимальное решение задачи коммивояжера имеет два основных свойства:

1. Оно состоит из множества ребер, вместе представляющих общий проезд.

2. Стоимость никакого другого общего проезда не будет меньше данного.

Эвристический алгоритм рассматривает свойство 1 как «обязательное», или «легкое», требование, а свойство 2 — как «трудное», относительно которого можно пойти на компромисс.

Пример с пятью городами на рис. 5.4 сразу показывает, что ал­горитм приведенный выше не гарантирует свойство 2. Однако на шаге 2 делается некоторая попытка снизить стоимость общего проезда.

Конечно, для алгоритма с помощью метода эвристики легко написать программу, но яв­ляется ли он быстрым? Для произвольной задачи коммивояжера с п городами требуется операций пропорционально N², чтобы прочесть или построить матрицу стоимостей С. Поэтому нижняя граница сложности любого алгоритма, способного дать нетривиальное возможное решение этой задачи по существующему методу равна N². Поэтому представленный алгоритм настолько быстрый, насколько возможно.

По-видимому, представленный алгоритм — это хороший эвристический алго­ритм. Конечно, понятие «хороший» относительно. Поскольку алго­ритм «исчерпывающий коммивояжер» слишком неэффективен, эпитет «хороший» может просто указывать на тот факт, что представленный алгоритм — наилучший из имеющихся для больших (в разумных пределах) значений N.

5.3 Программирование с отходом назад

Часто в программировании встречаются задачи в которых необходимо перебрать все возможные комбинации некоторой величины, или ситуация поиска некоторого значения из списка параметров. Встает задача как правильно организовать перебор комбинаций или осуществить поиск, не пропустив при этом ни одного значения. Причем, очень часто складывается ситуацию в которой, при таком переборе необходимо учесть те комбинации на которые условиями задачи поставлен запрет.

Один из методов такой организации вышеназванных процессов является программирование с отходом назад.

Метод разработки алгоритма, известный как программирование с отходом назад, можно описать как организованный исчерпывающий поиск, который часто позволяет избежать исследования всех возмож­ностей.

Этот метод особенно удобен для решения задач, требующих проверки потенциально большого, но конечного числа решений.

Для более полного представления этой задачи ее целесообразно посмотреть на примере задачи о замке с шифр.