Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет им. Ф. Скорины»

Математический факультет

Кафедра МПУ

Алгоритмы на графах. Методы приближенного решения задачи коммивояжера

Курсовая работа

Исполнитель:

Студентка группы М-33 Голубева А.Ю.

Научный руководитель:

Канд. физ-мат. наук, доцент Звягина Т.Е.

Гомель 2007

Содержание

Введение

1. Метод локальной оптимизации

2. Алгоритм Эйлера

3. Алгоритм Кристофидеса

Заключение

Литература

Введение

Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V,E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.

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

Матрица смежности - это двумерный массив размерности N*N.

A[i,j]=

Для хранения перечня ребер необходим двумерный массив R размерности M*2. Строка массива описывает ребро.

1. Метод локальной оптимизации

Попытаемся отказаться от перебора вариантов, рассмотренного в главе 2. Найдем первое решение (первую оценку), а затем попытаемся улучшить оценку, просматривая только соседние города найденного пути.

Шаг 1. Получить приближенное решение (первую оценку). При этом не следует забывать, что после получения первой оценки предыдущим методом его работа заканчивается.

Шаг 2. Пока происходит улучшение решения, выполнять следующий шаг, иначе перейти на шаг 4.

Шаг 3. Для всех пар номеров городов i,j, удовлетворяющих неравенству (1?i<j?n), проверить:

d_i-1,i +d_i,j +d_j,j+1 >d_i-1,j +d_j,i +d_i,j+1 для смежных городов, то есть j=i+1

d_i-1,i +d_i,i+1 +d_j-1,j +d_j,j+1 >d_i-1,j +d_j,i+1 +d_j-1,i +d_i,j+1 для несмежных городов.

Примечание. На рисунке даны графические иллюстрации первого и второго неравенств. “Жирными” линиями обозначены участки старых маршрутов, “тонкими” - новых.

Если одно из неравенств выполняется, то найдено лучшее решение. Следует откорректировать ранее найденное решение и вернуться на шаг 2.

Шаг 4. Закончить работу алгоритма.

Для реализации логики (из рассмотренных в предыдущем алгоритме структур данных) достаточно матрицы расстояний (А) и массива для хранения пути коммивояжера (Way). Вид общей логики:

begin

init;{Ввод из файла матрицы расстояний, инициализация глобальных переменных}

one_way;{Поиск первого варианта пути коммивояжера}

local;{Локальная оптимизация}

out;{Вывод результата}

end.

Примечание. Владение технологиями “сверху вниз” и “снизу вверх” - необходимые составляющие структурной парадигмы мышления.

Продолжим уточнение логики. Работа процедур init, one_way, out достаточно очевидна. Естественным приемом является вынесение ее в самостоятельную часть работы школьников на занятии. Нам необходимо уточнить процедуру local. Работаем не с частностями, а на содержательном уровне. Предположим, что мы имеем функции best1 и best2, их параметры - индексы элементов массива way, определяющих номера городов в пути коммивояжера, а выход естественный - истина или ложь, в зависимости от того, выполняются неравенства или нет. Рассуждаем дальше. Если неравенство выполняется, то нам необходимо изменить путь (соответствующие элементы массива way). Пока не будем заниматься деталями. Пусть эту работу выполняет процедура swap, ее параметры - индексы элементов массива way). Эта процедура, вероятно, должна сообщать о том, что она «что-то изменила», ибо нам необходимо продолжать работу до тех пор, пока что-то меняется, происходят улучшения. Итак, логика процедуры local.

Procedure local;

var i,j:integer; change:boolean;

<здесь функции best1 и best2, а также процедура swap>;

begin

repeat

change:=false;

for i:=1 to n-1 do

for j:=i+1 to n do

if i=j+1 then begin if best1(i,j) then swap(i,j);end

else if (i=1) and (j=n) then begin if best1(i,j) then swap(i,j); end{ъ

Об этой проверке лучше первоначально умолчать, чтобы было о чем спросить, «если совсем будет плохо» - все понимают и нет вопросов}

else if best2(i,j) then swap(i,j);

until not(change);

end.

2. Алгоритм Эйлера

Этот алгоритм и следующий работоспособны в том случае, если выполняется неравенство треугольника. Его суть в том, что для любой тройки городов i, j, k (между которыми есть связь) выполняется неравенство di,j+dj,k>di,k. Рассмотрим идею алгоритма.

Шаг1. Строится каркас минимального веса (алгоритмы Прима или Краскала).

Примечание. Это не есть первое приближение, как в предыдущем алгоритме.

Шаг 2. Путем дублирования каждого ребра каркас преобразуется в эйлеров граф.

Шаг 3. Находим в построенном графе эйлеров цикл.

Шаг 4. Эйлеров цикл преобразуем в гамильтонов цикл (или маршрут коммивояжера). Метод преобразования: последовательность вершин эйлерова цикла сокращается так, чтобы каждая вершина графа в получившемся цикле встречалась ровно один раз.

Шаг 5. Закончить работу алгоритма. Получено приближенное решение задачи коммивояжера.

Покажем, что стоимость приближенного решение CostAp не превосходит удвоенной стоимости оптимального решения CostBet. Пусть стоимость каркаса - CostFr. Тогда CostFr<CostBet, так как при удалении из оптимального пути коммивояжера ребра получаем каркас с весом не большим, чем CostAp. Из правила построения эйлерова графа получаем, что вес построенного эйлерова цикла 2*СostFr. Неравенство треугольника обеспечивает результат: следующую оценку шага 4 - CostAp<2*CostFr, а значит, CostAp<2*CostBet.

Рассмотрим пример.

Для исходных данных, приведенных в п. 2.1.7, на рисунке жирными линиями выделен каркас минимального веса. Тонкие линии добавляются на шаге 2. Получаем эйлеров граф. Затем эйлеров цикл (маршрут) преобразуется в путь коммивояжера (шаг 4). Согласно неравенству треугольника мы получаем: d_2,9+d_9,8>d_2,8; d_2,8+d_8,1>d_2,1; d_2,1+d_1,7>d_2,7. Суммируя левые и правые части неравенств, получаем: d_2,9+d_9,8+d_8,1+d_1,7>d_2,7. Для рассмотренного примера CostAp равна 202. Это ~ 1.28*CostBet.

Структуры данных. Помимо названных ранее массивов А - матрица расстояний и массива Way - хранение искомого пути, требуется «что-то» для хранение описания каркаса. Пусть это будет массив B (B:array[1..Nmax,1..Nmax] of boolean). Элемент B[i,j], равный true, говорит о том, что ребро (i,j) графа принадлежит каркасу.

Общая логика.

Begin

init;{ввод описания - матрица расстояний; инициализация данных}

solve;{решатель}

out;{вывод результата}

end.

Процедуры init и out очевидны (должны писаться «на автомате»). Уточняем процедуру solve. Первый «набросок».

Procedure solve;

var ?

<процедуры и функции>;

begin

init_solve;{инициализация переменных процедуры solve}

find_tree;{построение каркаса}

eiler_way;{поиск эйлерова цикла}

komm_way;{поиск пути коммивояжера}

end;

Прежде чем продолжать уточнение, необходимо определить структуры данных этой части логики и взаимодействие ее составных частей. Во-первых, при построении каркаса необходимо иметь список ребер, отсортированный в порядке возрастания их весов (алгоритмы Краскала и Прима). Следовательно, на входе процедуры find_tree матрица расстояний A, на выходе - B, рабочие структуры - массив для хранения списка ребер. Внутренние процедуры: формирование списка ребер и сортировки. Продолжим рассмотрение. Эйлеров цикл необходимо где-то хранить, пусть это будет массив St (St:array[1..n*(n-1) div 2] of byte. Количество не нулевых элементов в St - значение переменной Count. Эти величины описываются в разделе переменных процедуры solve, их инициализация - в процедуре init_solve.Процедуру поиска эйлерова цикла сделаем рекурсивной, поэтому первый вызов изменится - eiler_way(1). Выбор начальной вершины при поиске эйлерова цикла не имеет значения.

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

procedure eiler_way(v:byte);

var j:integer;

begin

for j:=1 to N do

if b[v,j] then begin b[v,j]:=false;b[j,v]:=false;eiler_way(j);end;

inc(count);St[count]:=v;{заносим номер вершины в эйлеров цикл}

end;

procedure komm_way;

var s:set of 1..Nmax;

i,j:integer;

begin

i:=0;s:=[];

for j:=1 to Count do{исключаем повторяющиеся номера вершин из эйлерова цикла}

if Not(St[j] in s) then begin

inc(i);way[i]:=St[j];s:=s+[St[j]];

end;

end;

3. Алгоритм Кристофидеса

Отличается от предыдущего логикой построения маршрута из каркаса минимального веса. Неравенство треугольника выполняется.

Шаг 1. Строится каркас минимального веса (алгоритм Прима или Краскала).

Шаг 2. На множестве вершин каркаса(обозначим их через V), имеющих нечетное число ребер каркаса, находится паросочетание минимального веса. Таких вершин в любом каркасе четное число. Метод поиска паросочетания - чередующиеся цепочки.

Шаг 3. Каркас преобразуется в эйлеров граф путем присоединения ребер, соответствующих найденному паросочетанию.

Шаг 4. В построенном графе находится эйлеров маршрут.

Шаг 5. Эйлеров маршрут преобразуется в маршрут коммивояжера:

Итак, данный метод отличается от предыдущего только шагами 2 и 3.

Все этапы реализуются за полиномиальное время. Известно[1], что для этого метода оценка приближенного метода имеет вид CostAp<1.5*CostBest и эта оценка является лучшей для приближенных полиномиальных алгоритмов решения задачи о коммивояжере с неравенством треугольника. На данных из п. 2.1.7 на рисунке показан пример каркаса (жирными линиями) и паросочетание минимального веса (тонкими линиями), построенное на вершинах каркаса с нечетными степенями. Путь коммивояжера имеет стоимость CostAp, равную 191, что составляет ~ 1.2*CostBest.



В логику solve (см. предыдущий алгоритм) добавляется процедура построения паросочетания минимального веса (P). Назовем ее pair. Ее входными данными является матрица B (описывает каркас), выходными - новая матрица С (элементы логического типа), соответствующая графу получаемому добавлением к каркасу ребер P.

Procedure pair;

var ?;

<процедуры pair>;

begin

init_pair;{инициализация переменных процедуры, формирование массива с номерами вершин, имеющих нечетную степень}

first;{поиск первого паросочетания}

find;{поиск P}

ad;{добавление ребер, образующих P к каркасу - матрица С}

end;

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

Заключение

Стоимость приближенного решение CostAp не превосходит удвоенной стоимости оптимального решения CostBet. Пусть стоимость каркаса - CostFr. Тогда CostFr<CostBet, так как при удалении из оптимального пути коммивояжера ребра получаем каркас с весом не большим, чем CostAp. Из правила построения эйлерова графа получаем, что вес построенного эйлерова цикла 2*СostFr. Неравенство треугольника обеспечивает результат: следующую оценку шага 4 - CostAp<2*CostFr, а значит, CostAp<2*CostBet.

Литература

Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы.-М.:Наука,1975.

Берж К. Теория графов и ее применение. - М.: ИЛ, 1962.

Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990.

Зыков А.А. Теория конечных графов.-Новосибирск:Наука; Сиб. отд-ние, 1969.

Йенсен П., Барнес Д. Потоковое программирование.-М.:Радио и связь,1984.

Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.

Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978.

Кофман А. Введение в прикладную комбинаторику.-М.:Наука,1975.

Липский В. Комбинаторика для программистов.-М.:Мир, 1988.

Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир,1981.

Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях.-Новосибирск: Наука; Сиб. отд-ние, 1990.

Окулов С.М.Конспекты занятий по информатике (алгоритмы на графах). Учебное пособие для студентов и учителей школ. - Киров, 1996.

Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.-М.:Мир,1985.

Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.:Мир,1984.

Филипс Д., Гарсиа-Диас А. Методы анализа сетей. - М.: Мир, 1984.

Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях.-М.:Мир,1963.

Фрэнк Г., Фриш И. Сети, связь и потоки.-М.:Связь,1978.

Харари Ф. Теория графов.-М.:Мир,1973.

Ху Т. Целочисленное программирование и потоки в сетях.- М.:Мир,1974.