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

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

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

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

2. Cтoмocть никакого другого тура не будет меньше данного.

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

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

Конечно, для алгоритма GTS легко написать программу, но является ли он быстрым? Для произвольной задачи коммивояжера с п городами требуется 0(п=) операций, чтобы прочесть или построить матрицу стоимостей С. Поэтому нижняя граница сложности любого алгоритма, способного дать нетривиальное возможное решение этой задачи, равна 0{п). Нетрудно проверить, что для любой разумной реализации шагов 1-3 требуется не больше, чем 0(п), операций. Поэтому алгоритм GTS настолько быстрый, насколько возможно.

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

Качество алгоритма GTS может быть значительно улучшено простой модификацией. Самым плохим свойством алгоритма является то, что выбор ребер очень низкой стоимости при вьшолнении шага 1 на ранних или средних стадиях работы алгоритма может привести к выбору очень дорогих ребер в заключительной стадии. Один из способов предостеречься от этого - применять алгоритм для каждого из рп разных, случайно выбранных, начальных городов. Другая модификация может состоять в повторении алгоритма для того же самого начального города, но надо начинать со второго по дешевизне ребра и затем, быть может, вернуться к прохождению самых дешевых ребер для последующих вершин. Возможны и другие вариации. Затем можно выбрать наименьший из рассмотренных туров. Или лучше: сохранять только самый дешевый тур из до сих пор найденных и

отбрасывать частично построенные туры, стоимости которых уже превышают стоимость текущего самого дешевого тура. Конечно, сложность модифицированного алгоритма, который мы назовем GTS2, может достигать порядка О(рп).

Algorithm GTS2 (грубый коммивояжер, версия 2). Образовать туры из 1<Р<Л разных начальных городов для задач коммивояжера с N городами. Последовательно строятся Р туров и запоминается лучший из до сих пор найденных туров. В качестве ввода для алгоритма требуются значения Л, Р, матрица стоимостей С и Р начальных городов {Vl, 1/2, - ., Vp}.

Шаг 0. [Инициализация] Set COST 00; and BEST-ч-0.

(Переменная К отсчитывает число до сих пор использованных начальных городов; BEST служит для запоминания лучшего из до сих пор найденных туров, стоимость которого равна COST.)

Шаг 1. [Начало нового тура] Do through шаг 3 while /С<Р od; and STOP.

Шаг 2. [Образование нового тура] Set /С-<- /С+1; and CALL GTS (1 ). (Оператор CALL СТ5(1/д.) заставляет алгоритм GTS построить тур с городом V в качестве начального. Тур Т(К) со стоимостью С (К) построен.)

Шаг 3. [Обновление лучшего тура] If C(/C)<COST then set BEST Г (/С); and COSTC(/<) fi.

T 2 3 "4

Рис. 3.2.2. Иллюстрация алгоритма GTS2.

Реализация алгоритма GTS2 с подалгоритмом GTS не представляет труда. Алгоритм GTS2 должен передавать текущее значение COST алгоритму GTS. Если в процессе выполнения подпрограммы стоимость частично построенного тура больше или равна COST, то возвращается значение C{K) = oo.

Что получится, если применить алгоритм GTS2 к задаче с пятью городами, пог.азанной на рис. 3.2.2? Возьмем р=3, а в качестве начальных городов - три вершины с нечетными номерами.

Начиная с вершины 1, находим следующие ребра:

(1, 2) со стоимостью 25,

(2, 3) со стоимостью 17 [замечаем, что (2,1) дает нежелательный подтур],

(3,5) со стоимостью 1,

(5.4) со стоимостью 10 (это ребро мы вынуждены выбрать как единственно возможное на данном этапе),

(4.1) со стоимостью 9.

Общая стоимость полученного тура равна 62. Начиная с вершины 3, находим следующие ребра:

(3.5) со стоимостью 1,

(5.2) со стоимостью 8 [замечаем, что (5,3) дает нежелательный подтур],

- (2,1) со стоимостью 5, (1,4) со стоимостью 31,

(4.3) со стоимостью 24.

Общая стоимость этого тура равна 69. Наконец, начиная с вершины 5, находим:

(5.3) со стоимостью 7,

(3.4) со стоимостью 6,

(4.1) со стоимостью 9,

(1.2) со стоимостью 25,

(2.5) со стоимостью 25.

Здесь общая стоимость равна 72.

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

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

Предположим, что у нас есть множество п одинаковых процессоров, обозначенных Pi, . . ., Рп, и т независимых заданий Ji, . . ., Jm> которые нужно выполнить. Процессоры могут работать одновременно, и любое задание можно выполнять на любом процессоре. Если задание загружено в процессор, оно остается там до конца обработки. Время обработки задания известью, оно раврю ti, t=l, . . ., т. Наша цель - организовать обработку заданий таким образом, чтобы