6.16. Пример практической задачи на графах

Следует осознать, что рассматривался "инструментарий" для решения всевозможных графовых задач. Например, алгоритмы нахождения максимального потока (Минимального разреза), которым посвящен целый ряд исследований, позволяют решать разнообразные задачи, и не только задачи о потоках энергии и вещества (см. [11]). Используемые в алгоритмах методы сами по себе представляют ценность и к ним прибегают, когда готовых алгоритмов недостаточно.

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

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

Итак, нужен замкнутый маршрут с минимальной стоимостью или длиной. Сложность оптимального решения задач зачастую высока, поэтому довольствуются приближенным. Например, для полных гра­фов с выполненным неравенством треугольника d_ij<=d_ik + d_kj, где i, j, k - любые узлы графа

а) находят кратчайший каркас графа, затем дублируют ребра каркаса;

б) в полученном мультиграфе находят эйлеров цикл - замкну­тый маршрут, проходящий через все узлы и - строго по одно­му разу - через все ребра;

в) выделяют отрезок эйлерова цикла, на котором лежат все узлы, и принимают за искомый маршрут; его длина всегда меньше удвоенной длины оптимального маршрута [11].

Усложняя алгоритм, добиваются лучшего результата. Мы, напротив, сделаем упрощения, обойдемся без мультиграфа и не будем искать эйлеров цикл, сохранив тем не менее качество результата. Изучите рисунок, на котором сплошными линиями изображен кратчайший каркас графа G4 с 11 узлами, а пунктиром - хорды:

Стрелки показывают маршрут, причем порядок посещения узлов соответствует поиску в глубину в каркасе. Исходя из неравенства треугольника, нетрудно показать, что длина хорды не превосходит суммы длин ребер цепи, стягиваемой хордой. Отсюда следует, что длина маршрута - не больше удвоенной суммы длин ребер кратчайшего каркаса, а последняя - меньше длины оптимального маршрута [11].

Пример 6.15 (идея заимствована из [11]).

Устройство может выполнять поочередно n различных работ, причем t_ab – время его перенастройки при переходе от работы a к работе b. Множество значений t_ab можно рассматривать как веса ребер в полном графе из n узлов, представляющих работы, а ребра – переходы от работы к работе. Каждая работа выполняется один раз. Надо найти последовательность работ с минимальным суммарным временем перенастройки. Решим приближенно эту задачу, отличающуюся от задачи коммивояжера лишь тем, что "маршрут" переходов не замкнут.

Const n=6;

Type tip=word; matr=Array[1 ..n, 1 ..n] of tip;

mas=Array[1..n] of integer; vec=Array[1..n] of word;

gla=Array[1..n+1] of word;

Const A:matr=(( 0, 20, 5, 30, 70, 30), {Перенастройки 1->2.. 1->6} i

(20, 0, 16, 20, 88, 11), {Перенастройки2-> 1.. 2->6} '

(5, 16, 0, 25, 67, 26), {Перенастройки 3->1.. 3->6]

(30, 20, 25, 0, 35, 50), {Перенастройки 4-> 1.. 4->6] .

(70,88, 67, 35, 0, 40), (Перенастройки 5-> 1.. 5->6]

(30, 11, 26, 50, 40, 0)); {Перенастройки 6-> 1.. 6->5]

Varr,sp:vec; i,og:gla; j,jj,k,L,X:word; C:longint; B:Boolean;

Procedure Ostov (var A:matr; var r,sp:vec; var og:gla; X:word);

Var k,j,L,min:word; max,p:integer; d:mas;

Begin max:= Maxint;

For j:=1 to n do d[j]:=-max; d[X]:=0;

r[X]:=n+1; L:=X;

Repeat For j:=1 to n do If A[L,j] > 0 then

If A[L,j] < -d[j] Then

Begin d[j]:=-A[l,j]; r[j]:=L End;

min:=max;

For k:=1 to n do lf(d[k] < 0) And (-d[k] < min) then

Begin min:=-d[k]; L:=k End; d[L]:= -<1[L]

Until min=max; {Ниже - действия из ответа к заданию 5.13:}

og[1]:=1; For j:= 2 to n+1 do og[j]:= 0;

For j = 1 to n do Begin k:= r[j]; og[k]:= og[k] + 1 End;

For j = 2 to n+1 do og[j]:= ogfj]+og[j-1];

For j = 1 to n do Begin k:= r[j]; og[k]:=og[k]-1; sp[og[k]]:=j End

End {блока Ostov}',

Procedure Obrab(k,j:word); {Блок, составляемыйпользователем}

Begin

Writeln(A[k,j],' ',j); C:= C+A[k,j] ;

End;

BEGIN

Writeln ('Укажите номер (1..n) начальной работы: ');

Readln(X); Ostov(a,r,sp,og,X); Writeln;

C:=0; L:=X; B:=true; i:=og; {Далее следует обход каркаса:}

Repeat j:=i[L];i[L]:=i[L]+1;

If j < og[L+1] Then

Begin jj:= sp[j]; If В Then Obrab(LJj) Else Obrab(kjj);

B:=true; L:=jj

End

Else Begin If В Then k:=L; B:= false; L:= r[L] End

Until L= n+1;

Writeln ('Общее время всех перенастроек равно', С); Readln

END.

В блок Obrab передается (в виде номеров 2 смежных умов) очередное ребро маршрута и пользователь может выбрать

• обработку маршрута по мере выявления его звеньев (ребер);

• вывод маршрута с указанием весов ребер (как в примере);

• запоминание маршрута для дальнейшего использования;

• комбинацию указанных возможностей.

В главной программе трудно усмотреть глубинный обход каркаса. Дело в том, что возвраты выполнены с помощью ссылок r[L] и стек не понадобился. Заметим, что предложенный алгоритм решения естественнее для данной задачи, чем "традиционный": в найденном нами маршруте узлы не повторяются.

Задание 6.16.

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