Рекурсивный алгоритм Алгоритм Каркас-Рек

Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во-первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во-вторых, чтобы в каркасе было ровно N-1 ребро (N - количество вершин графа).

Реализация.

procedure step(v,k: byte; r: longint);var j: byte;begin if r < min then if k = N-1 then min:= r else for j:= 1 to N do if (sm[v,j]<>0)and(mark[j]=0) then begin mark[j]:= 1; step(j,k+1,r+sm[v,j]); mark[j]:= 0 end;end;begin ... for i:= 1 to N do mark[i]:= 0; min:= MaxLongInt; for i:= 1 to N do begin mark[i]:=1; step(i,1,0); mark[i]:=0; end; writeln(min); ...end.

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

Рекурсивный алгоритм Алгоритм Расст-Рек

Совершить обход графа в глубину, при каждом "шаге вперед" прибавляя длину ребра к длине текущего пути, при каждом возврате - отнимая длину этого ребра от длины текущего пути. При движении "вперед" пометки посещенности вершин ставятся, при "откате" - снимаются. По достижении выделенной вершины t производится сравнение длины текущего пути с ранее найденным минимумом.

Реализация

Пусть граф задан матрицей смежности sm, а массив mark хранит информацию о посещениях вершин. Напомним, что уменьшение длины пути "на возврате" совершается рекурсией автоматически, поскольку в ее заголовке использован параметр-значение, а вот аналогичное обнуление соответствующих позиций массива mark приходится делать вручную, поскольку задавать массив параметром-значением чересчур накладно:

procedure rasst(v: byte; r: longint);var i: byte;begin if v = t then if r< min then min:= r else else for i:= 1 to N do if (mark[i]=0)and(sm[v,i]<>0) then begin mark[i]:=1; rasst(i,r+sm[v,i]); mark[i]:=0 endend;begin ... for i:= 1 to N do mark[i]:= 0; min:= MaxLongInt; mark[s]:= 1; rasst(s,0); mark[s]:= 0; ...end.

Итеративный алгоритм

Алгоритм, предложенный Дейкстрой, настолько мощнее рекурсивного алгоритма Расст-Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t, но и до всех остальных вершин графа.

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

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

Переменная last будет хранить номер последней помеченной вершины.

Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.

Алгоритм Дейкстры

Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше - ведь веса всех ребер графа у нас положительны. Таким образом:

dist[s]:= 0; done[s]:= true; last:= s;

Повторить N-1 раз следующие действия:

для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:

dist[x]:= min(dist[x], dist[last]+ sm[last,x]);

среди всех непомеченных вершин найти минимум в массиве dist: это будет новая вершина last;

пометить эту новую вершину в массиве done.

Реализация

dist[s]:= 0; done[s]:= true; last:= s;for i:= 1 to N-1 do begin for x:= 1 to N do if (sm[last,x]<>0)and(not done[x]) then dist[x]:= min(dist[x],dist[last]+ sm[last,x]); min_dist:= MaxLongInt; for x:= 1 to N do if (not done[x])and(min_dist>dist[x]) then begin min_dist:= dist[x]; last:= x; end; done[last]:= true; end.

СОДЕРЖАНИЕ РАБОТЫ:Разработать программу с использованием алгоритмов с возвращением:

― нахождение минимального каркаса в зданном взвешенном связанном графе:

― рекурсивный алгоритм Каркас-Рек;

― интерактивный алгоритм Краскала.

― нахождения кратчайших путей в зданном взвешенном связанном графе:

― рекурсивный алгоритм Расст-Рек;

― интерактивный алгоритм Дейкстры.

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Перечислите алгоритмы с возвращением.

2. Опишите принцип работы алгоритмов с возвращением.

ДОМАШНЕЕ ЗАДАНИЕ

Выучить алгоритмы Каркас-Рек, Краскала, Расст-Рек и Дейкстры.