Модификации алгоритма с возвратом. задачи на максимум и минимум

ЗАДАЧА КОММИВОЯЖЕРА

Пусть заданы конечное множество C городов, целые положительные расстояния A(c1,c2) для каждой пары городов c1,c2.

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

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

Итак, задача на минимум — среди всех допустимых объектов ищется минимальный.

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

При продолжении решения стоимость может только увеличиваться:

cost(< X(1), …, X(i-1) >)<= cost(< X(1), …, X(i-1), X(i)>).

Для задачи коммивояжера целевой функцией, удовлетворяющей такому условию, будет

cost(< X(1), …, X(i)>)=A(X(1), X(2))+…+ A(X(i-1), X(i)).

Очевидно, что ее значение будет увеличиваться при удлинении маршрута.

Идея алгоритма:

1. Находим первое решение и запоминаем его стоимость в OptCost.

2. Пусть < X(1), …, X(i)> — текущее частичное решение. Прежде, чем пытаться продолжать его дальше, проверим, имеет ли смысл это делать. Если cost(< X(1), …, X(i)>) >= OptCost,

то любое его продолжение будет заведомо больше текущего минимального решения. Производим возврат к предыдущему частичному решению <X(1), …, X(i-1)>.

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

АЛГОРИТМ. {Нахождение гамильтоновых цикла min длины}

Данные: Граф G=<V,E>, представленный списками ЗАПИСЬ[v], матрица весов A[u,v].

Результаты: Печать min гамильтонова цикла.

Переменные ЗАПИСЬ, X, cost, OptX, OptCost, DOP — глобальные.

1 procedure KOMMI(i);

2 begin

3 for y Є ЗАПИСЬ[X[i-1]] do

4 if cost + A[X[i-1], y] < OptCost then

5 if (i = n+1) AND (y = k) then

6 begin OptX:=X; OptCost:= cost + A[X[i-1],y] end

7 else if DOP[y] then

8 begin

9 X[i]:=y; DOP[y]:= ложь;

10 cost:=cost + A[X[i-1], y];

11 KOMMI(i+1);

11 DOP[y]:= истина; cost:=cost — A[X[i-1], y];

12 end;

13 end; {KOMMI }

1 begin { основная программа }

2 for v Є V do DOP[v]:=истина;

3 X[1]:=k; { k — произвольная }

4 DOP[k]:= ложь;

5 cost:=0; OptCost:= +¥;

6 KOMMI(2);

7 end.

ЗАДАЧА О РЮКЗАКЕ

Задано конечное множество A, положительные целые веса w(a), стоимости s(a) для каждого a Є A и общее ограничение на вес K. Найти из всевозможных выборок A' A такую, чтобы суммарный вес входящих в него элементов не превосходил K, а суммарная стоимость была максимальна.

Задача о рюкзаке — задача об определении оптимальной выборки из N объектов, подчиненной некоторому ограничению. Поскольку из N объектов возможно сделать 2^N различных выборок, для решения подобной задачи с помощью алгоритма с возвратом необходимо очень сильное ограничение!

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

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

Такой метод получил название

ПРИНЦИП ВКЛЮЧЕНИЯ‑НЕВКЛЮЧЕНИЯ.

Каждый i-й объект проверяется на допустимость (согласно нашему ограничению). Затем внутри одной процедуры допустимый объект вначале включается в выборку, и с этим включенным объектом рекурсивно генерируются всевозможные решения и лучшее из них запоминается как оптимальное.

После этого происходит возврат и i-й объект удаляется из выборки.

Классический алгоритм с возвратом стал бы рекурсивно генерировать всевозможные решения без i-го объекта — принцип включения–невключения действует иначе.

Прежде, чем пытаться получать решения без i-го объекта, ПРОВЕРИМ, можно ли, не включив этот объект, получить решение лучшее, чем найденное оптимальное с i-м объектом. Если нет — то не стоит и пытаться.

Как проверить возможность получения без i-го объекта более ценной выборки, чем текущая оптимальная, если мы не собираемся сразу строить эти выборки?

Нужно посчитать стоимость, которую мы, МОЖЕТ БЫТЬ, наберем без i-го объекта. Для этого просуммируем стоимости всех предметов, УЖЕ вошедших в выборку, и стоимости всех ЕЩЕ неисследованных предметов (разумеется, без i-го объекта).

Если эта стоимость, которую, может быть, удастся набрать (а, может, и не удастся — ведь неисследованные объекты могут не пройти ограничение по весу!), будет больше оптимальной — будут генерироваться решения без i‑го объекта.

Опишем рекурсивную процедуру TRY с включением‑невключением.

1 procedure try(i);

{i — номер объекта}

2 begin

3 IF ВКЛЮЧЕНИЕ ПРИЕМЛИМО THEN

4 begin

5 включить i-тый объект;

6 if i=N then проверить оптимальность

7 else try(i+1);

{продолжить выборку}

8 удалить i-тый объект;

{возврат}

9 end;

{оптимум с i-тым объектом запомнен, а сам объект
удален}

10 IF НЕВКЛЮЧЕНИЕ ПРИЕМЛИМО THEN

{подсчет возможной стоимости без i-того объекта и
сравнение ее с оптимальной}

11 if i=N then проверить оптимальность

12 else try(i+1);

{строим выборки без i-того объекта}

13 end; {try}

Пусть имеется 3 предмета и ограничение по весу 16.

НОМЕР
ВЕС
СТОИМОСТЬ

Первый раз из основной программы вызывается try(1).

try(i)	№ 1	№ 2	№ 3	Сумм. вес	Сумм. стоим.	Возм. стоим.	Оптим. стоим.	Примечания
try(1)	да	нет	нет					вкл. 1
try(2)	да	да	нет					вкл. 2
try(3)	да	да	нет					оптимум
try(2)	да	нет	нет					невкл. 2
try(3)	да	нет	да					оптимум
try(1)	нет	нет	нет					невкл. 1 неприем.

Последний оптимум = 25 достигается на выборке 1, 3 и далее уже не меняется.

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

CONST N=3;

VES=16;

TYPE index=1..N;

object= record

v, st: integer {вес и стоимость}

end;

VAR A: array [index] of object; {массив объектов}

s, opts: set of index; {выборка, оптимальная
выборка}

sum: integer; {стоимость всех объектов}

opt_st: integer; {оптимальная стоимость}

Алгоритм. {РЮКЗАК}

Данные: Массив A записей object, ограничение по весу VES.

Результаты: Выборка max ценности с ограничением по весу.

{Считаем, что массив записей A уже сформирован}

1 procedure try(i:index; sum_v, pos_st: integer);

{i — объект, sum_v — вес текущей выборки, pos_st —
возможная стоимость}

2 begin

{включение}

3 if sum_v + A[i].v <= VES then

4 begin {проверка допустимости}

5 s:=s + [i];

6 if (i = N) and (pos_st > opt_st) then

7 begin {новый оптимум}

8 opts:=s; opt_st:=pos_st

9 end

10 else

11 try(i+1, sum_v + A[i].v, pos_st);

{строим решения с i-тым объектом, pos_st не изменилась, т.к. i-тый объект из неисследованных перешел во включенные}

12 s:=s — [i]; {возврат}

{невключение}

13 st1:= pos_st — A[i].st; {возможная ценность
без i-того объекта}

14 if st1 > opt_st then

15 if i = N then

16 begin {новый оптимум}

17 opts:=s; opt_st:=st1

18 end

19 else

{строим решения без i-того объекта}

20 try(i+1, sum_v, st1);

21 end; {проверка допустимости}

22 end; {try}

1 begin {основная часть}

2 sum:=0;

3 for i:=1 to N do

4 sum:=sum + A[i].st;

5 s:=[]; opts:=[]; opt_st:=0;

6 try(1, 0, sum);

7 печать opts;

8 end.

Ответы.

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

Кратчайшие пути

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

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

Будем рассматривать ориентированные графы, дугам которых приписаны веса.

Рисунок 8.28

Это означает, что каждой дуге u→v поставлено в соответствие вещественное число A[u,v]. Матрицу весов дуг данного графа будем обозначать A, несуществующим дугам будем приписывать веса, равные ¥, т.е. A[u,v]=¥, если дуга u→v не существует.

Матрица весов A для рисунка 8.28:

¥		¥	¥
¥	¥
¥	¥	¥		-5
¥	¥		¥	¥
¥	¥	¥		¥

В программе граф будет задаваться матрицей весов и (если потребуется) списками инцидентности PRED и SLED. В списках PRED для каждой вершины v хранится список ее предшественниц u, т.е. вершин, из которых дуга идет в эту вершину.

В списках SLED для каждой вершины v хранится список ее потомков, т.е. вершин, в которые из v идет дуга.

Длина пути будет подсчитываться как сумма весов входящих в него дуг.

Зафиксируем в графе пару вершин s (источник) и t.

Длину кратчайшего пути от s до t будем обозначать D[s, t], где D — матрица расстояний между всеми парами вершин. Если такого пути не существует, то будем считать, что D[s, t]=¥.

Если источник s зафиксирован, то расстояния от s до остальных вершин графа будут храниться в векторе (одномерном массиве) D, где D[v] — расстояние от s до v.

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

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

Окончательная постановка:

БУДЕМ ИСКАТЬ КРАТЧАЙШИЕ ПУТИ НА ГРАФАХ БЕЗ КОНТУРОВ ОТРИЦАТЕЛЬНОЙ ДЛИНЫ.

В этом разделе мы рассмотрим четыре алгоритма, которые будут вычислять матрицу D расстояний между источником и всеми остальными вершинами:

— первый подходит графам самого общего вида, т.е. без контуров отрицательной длины;

— второй применяется для графов с неотрицательными весами;

— третий для бесконтурных графов

— и четвертый на графе общего вида находит расстояния между всеми парами вершин.

Сразу возникает вопрос: зачем нужны четыре различных алгоритма, когда для решения всех этих задач было бы достаточно одного, самого первого?

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

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

зная расстояния от источника s до всех остальных вершин, найти путь от источника до какой-то выбранной вершины t.

Если нам удастся по последней вершине t восстановить предпоследнюю (назовем ее v), то задача решена. Восстановим предпоследнюю, по ней предпредпоследнюю и так до тех пор, пока не дойдем до источника.

Предпоследняя вершина v кратчайшего пути обладает следующим свойством:

D[s,t]=D[s,v] + A[v,t].

Алгоритм. {Нахождение кратчайшего пути}

Данные: Расстояния D[v] от источника s до всех остальных vÎV, фиксированная вершина t, матрица весов A[u,v], u,vÎV.

Результаты: СТЕК, содержащий путь от s до t.

1 begin

2 СТЕК:=0; СТЕКÜt; v:=t;

3 while v<>s do

4 begin

5 u:= первая из списка PRED[v];

6 while D[v]<>D[u] + A[u,v] do

7 u:=следующая из списка PRED[v];

8 СТЕКÜu; v:=u;

9 end

10 end.

Так как для поиска всех вершин u происходит просмотр не более m дуг (в списках PRED), то вычислительная сложность этого алгоритма О(m).

?Вопрос 1. Как переделать процедуру восстановления пути так, чтобы в случае существования нескольких путей одной длины на печать выдавались все?

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

Алгоритм Форда-Беллмана

Мы должны вычислить матрицу расстояний D[v]. За начальные (приближенные) значения D[v] возьмем веса дуг A[s,v]. Они будут соответствовать путям из s в v длиной в одну дугу. Если дуги s→v не существует, то начальное D[v] принимается равным ¥. Расстояние от источника до самого себя всегда считается равным 0.

Каким образом можно уточнить значения D[v]? Взять все пути из s в v длиной в две дуги и сравнить их с начальными D[v]. За окончательное значение D[v] принимается минимальное. Затем берутся пути длиной в три дуги и т.д. Процесс пересчета будет продолжаться до тех пор, пока не будут рассмотрены пути длиной в n-1 дугу. Нет смысла рассматривать пути длиной в n и более дуг, т.к. они будут содержать контур, который только увеличит суммарную длину пути.

Остается выяснить, каким образом из пути в k дуг можно получить все пути длиной в k+1 дугу. Из рисунка 8.29 видно, что, добавив между s и v промежуточную (предпоследнюю) вершину u, мы автоматически удлиняем путь ровно на одну дугу. Длина старого пути равна D[v], длина нового пути равна D[u] + A[u,v].

Рисунок 8.29

Алгоритм. {Форд-Беллман}

Данные: Орграф <V,E> с n вершинами и выделенным источником s, заданный списками инцидентности PRED, матрица весов A[u,v], u,vÎV; граф не содержит контуров отрицательной длины.

Результаты: Расстояния D[v] от источника s до всех остальных vÎV.

1 begin

2 for vÎV do D[v]:=A[s,v]; D[s]:=0;

3 for k:=1 to n-2 do

4 for vÎV-[s] do

5 for u Î PRED[v] do

6 D[v]:= min(D[v], D[u] + A[u,v]);

7 end.

Возможно, для вычисления D[v] нам не потребуются все n-2 итерации. Момент, когда D[v] будут вычислены окончательно, легко определить. Это произойдет, когда выполнение цикла 4 не вызовет изменения ни одного значения D[v].

Вычислительная сложность алгоритма О(n*m). Если граф не является «разреженным» и число дуг m» n², то можно считать вычислительную сложность равной О(n³).

Трассировка работы алгоритма Форда–Беллмана для графа с рисунка 8.28:

k	D[1]	D[2]	D[3]	D[4]	D[5]
			¥	¥
					-1
					-1
					-1

?Вопрос 2. Можно ли воспользоваться алгоритмом Форда-Беллмана для неориентированного графа, заменив каждое неориентированное ребро парой противоположно направленных дуг одного веса?

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

Рассмотрим отдельно случай, когда веса всех дуг неотрицательны.

Разделим все вершины V графа на два множества: T и V\T. T — рабочее множество, в нем содержатся вершины uÎT, для которых еще не известны окончательные D[u]. V\T — множество вершин, для которых уже известны настоящие расстояния.

В начальный момент в V\T содержится единственная вершина — источник s, все остальные вершины содержатся в V\T.

На каждой итерации основного цикла одна вершина из T будет переводиться в V\T. Этой вершиной r будет та, у которой D[r] минимально среди всех вершин множества T. Как только такая минимальная r будет найдена и переведена из T в V\T, для оставшихся вершин uÎT нужно будет пересчитать расстояния D[u].

Пересчет производится следующим образом: проведем путь от s к u через вершину r. Длина этого пути сложится из D[r] и веса дуги A[r,u]. Новое значение D[u] выберется как минимальное из старого D[u] и длины D[r]+A[r,u].

Алгоритм закончит работу, когда все вершины из множества T будут переведены в множество V\T. Доказательство корректности этого алгоритма будет приведено чуть позже, опишем сам алгоритм.

Алгоритм. {Дейкстра}

Данные: Орграф <V,E> с выделенным источником s, матрица неотрицательных весов A[u,v], u,vÎV.

Результаты: Расстояния D[v] от источника s до всех остальных vÎV.

1 begin

2 for vÎV do D[v]:=A[s,v]; D[s]:=0;

3 T:=V—[s];

4 while T<>0 do

5 begin

6 r — вершина из T, для которой
D[r]:=min(D[u], uÎT);

7 T:=T—[r];

8 for uÎT do D[u]:= min(D[u], D[r] + A[r,u]);

9 end;

10 end.

Подсчитаем вычислительную сложность этого алгоритма.

Цикл 4 выполняется n-1 раз, так как именно столько вершин переводится из T в V\T. Внутри цикла при поиске минимальной просматривается не более n вершин; при пересчете расстояния пересчитываются не более, чем для n вершин. Окончательно получаем О(n²).

Докажем корректность первого шага алгоритма, когда из множества T, содержащего все вершины за вычетом источника, удаляется минимальная вершина r. Рассмотрим для иллюстрации модельный граф на рисунке 8.30.

Рисунок 8.30

В первый момент расстояния D[v] равны весам дуг A[s,v]. Минимальной вершиной r (вершина 2) является вершина с минимальным весом дуги s→r (дуга 1→2 с весом 1). Ни в одну другую вершину нельзя прийти более коротким путем, т.к. либо первая дуга s→u (дуга 1→4 с весом 2) (u¹r) будет уже длиннее, либо к дуге s→r нужно будет добавить хотя бы одну дугу, а веса всех дуг неотрицательны.

Полное математическое доказательство корректности читатель может найти в [1].

Трассировка работы алгоритма Дейкстры для модельного графа (рисунок 8.31) представлена в таблице 1.

Рисунок 8.31

Таблица 1

узел пересчета	D[1]	D[2]	D[3]	D[4]	D[5]	D[6]
			¥	¥	¥	¥
					¥

?Вопрос 3. Всегда ли можно воспользоваться алгоритмом Дейкстры для неориентированного графа с неотрицательными весами ребер?

Пути в бесконтурном графе

Для бесконтурного графа с произвольными весами дуг задача нахождения кратчайшего пути может быть решена за О(m) шагов. Рассмотрим модельный бесконтурный граф (рисунок 8.32).

Рисунок 8.32

Любой бесконтурный граф обладает следующим свойством:

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

Такую нумерацию будем называть правильной. Для нашего модельного графа пример возможной правильной нумерации приведен на рисунке 8.33.

Рисунок 8.33

Доказательством этого свойства будет служить алгоритм 4.

Алгоритм основывается на следующем простом факте:

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

Все такие вершины соберем в СТЕК. Затем

1) вытолкнем из СТЕКА произвольную вершину,

2) присвоим ей номер 1,

3) удалим ее из графа вместе со всеми выходящими из нее дугами.

После операции удаления дуг могут появиться новые вершины, в которые не заходит ни одна дуга. Эти вершины помещаются в СТЕК, затем из СТЕКА выталкивается произвольная вершина, ей присваивается следующий номер и т.д.

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

Не так очевидно, почему все вершины получат номера:

если из СТЕКА удалили последнюю вершину, а в графе, получившемся после удаления этой вершины и выходящих из нее дуг, все вершины имеют заходящие в них дуги, то они уже никогда не попадут в СТЕК и никогда не получат номера.

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

Поскольку из СТЕКА выталкивается произвольная вершина, то принцип стека не является обязательным и выбран только для удобства.

Алгоритм. {Правильная нумерация}

Данные: Бесконтурный орграф G=<V,E>, заданный списками инцидентности SLED[v], vÎV.

Результаты: Для каждой вершины v новый номер NN[v] такой, что номера NN[v] являются правильной нумерацией графа G.

1 begin

{INP[v] — число дуг, заходящих в вершину v}

2 for vÎV do INP[v]:=0;

3 for uÎV do

4 for vÎ SLED[u] do

{находим все вершины v, дл я которых u→v}

5 INP[v]:=INP[v] + 1;

6 СТЕК:=0;

7 for vÎV do

8 if INP[v]=0 then СТЕК Ü v;

9 num:=0; {текущий номер}

10 while СТЕК <> 0 do

11 begin

12 u Ü СТЕК;

13 num:=num+1;

14 NN[u]:=num;

15 for vÎ SLED[u] do

16 begin

17 INP[v]:=INP[v] — 1;

18 if INP[v]=0 then СТЕК Ü v;

19 end;

20 end;

21 end.

Все дуги графа анализируются два раза: в цикле 3–5 для подсчета числа заходящих дуг INP[v], в цикле 10–20, где удаление дуг из графа заменено уменьшением чисел INP[v].

Таким образом, вычислительная сложность алгоритма пропорциональна числу дуг, т.е. равна О(m) шагов.

Теперь можно считать, что у нас имеется бесконтурный граф с правильной нумерацией вершин, и вершина источник имеет номер 1.

Так как все дуги идут из вершины с меньшим номером в вершину с большим номером, то промежуточные вершины на пути от 1 до j будут иметь номера меньшие j. Поэтому для нахождения кратчайшего расстояния D[j] нужно знать только D[2],…,D[j-1]. Идея алгоритма следующая: зная D[1] (оно равно 0), вычислить D[2]; зная D[1] и D[2] вычислить D[3] и т.д.

Алгоритм. {Расстояния в бесконтурном графе}

Данные: Орграф G=<V,E> с правильной нумерацией, заданный списками PRED[v], матрица весов A[u,v], u,vÎV.

Результаты: Расстояния D[v] от источника 1 до всех остальных vÎV.

1 begin

2 D[1]:=0;

3 for j:=2 to n do D[j]:= ¥;

4 for j:=2 to n do

5 for i ÎPRED[j] do

6 D[j]:= min(D[j], D[i] + A[i,j]);

7 end.

В цикле 4–6 каждая дуга анализируется ровно один раз, поэтому вычислительная сложность алгоритма равна О(m) шагов.

Бесконтурный граф может служить математической моделью для задач управления выполнением проектов. Дуги графа соответствуют элементарным задачам, составляющим проект, веса дуг — времени, необходимому для выполнения элементарной задачи. Вершина s соответствует началу выполнения проекта, вершина t — его завершению. Для любых двух дуг u→v и v→p предполагается, что задача u→v должна быть закончена до начала выполнения задачи v→p. Самый длинный путь от s до t соответствует времени, минимально необходимому для выполнения всего проекта.

?Вопрос 4. Каким образом можно воспользоваться процедурой поиска кратчайшего пути для нахождения самого длинного пути?

Алгоритм Флойда

Для решения задачи о кратчайших расстояниях между всеми парами вершин можно воспользоваться алгоритмом Форда-Беллмана, применив его n раз к каждой из вершин. Однако существует более эффективный алгоритм, который решает ту же задачу за О(n³) шагов.

Идея алгоритма следующая: будем искать кратчайшие расстояния D[i,j], постепенно увеличивая количество промежуточных вершин в пути от i до j. За начальные приближения возьмем пути от i до j без промежуточных вершин, т.е. веса ребер A[i,j].

Пусть уже известны длины D[i,j] самых коротких путей между всеми парами вершин, имеющих промежуточные вершины из множества 1..k-1. Добавим теперь к множеству промежуточных вершин вершину k. Путь от i до j будет складываться из пути от i до k и пути от k до j (см. рисунок 8.34).

Рисунок 8.34

Так как наши пути не могут содержать повторяющихся вершин (иначе бы они не были кратчайшими), то пути от i до k и от k до j среди промежуточных вершин могут иметь только вершины из множества 1..k-1. Длины таких путей нам известны по предположению, поэтому длина пути от i до j, проходящего через k, сложится как сумма D[i,k]+D[k,j]. Остается сравнить старое значение D[i,j] с этой суммой и в качестве окончательного значения выбрать минимальное. Алгоритм заканчивает работу, когда промежуточными вершинами могут быть все вершины графа.

Алгоритм 6. {Флойд}

Данные: Орграф G=<V,E>, матрица весов A[u,v], u,vÎV.

Результаты: Расстояния D[i,j] между всеми парами вершин i,j ÎV.

1 begin

2 for i:=1 to n do

3 for j:=1 to n do D[i,j]:=A[i,j];

4 for i:=1 to n do D[i,i]:=0;

5 for k:=1 to n do

6 for i:=1 to n do

7 for j:=1 to n do

8 D[i,j]:= min(D[i,j], D[i,k] + D[k,j]);

9 end.

Очевидно, что тройной цикл дает вычислительную сложность О(n³).

?Вопрос 5. Измените алгоритм печати пути исходя из того, что имеется двумерный массив расстояний D[i,j].

Ответы

Ответ 1. Цикл (6–7) находит ровно одну предыдущую вершину, но для печати всех путей нужно находить все такие вершины.

Ответ 2. Можно только в том случае, если при этом не образуется контур отрицательного веса.

Ответ 3. Да, всегда.

Ответ 4. Изменить веса дуг на противоположные. Граф бесконтурный, поэтому контуры отрицательного веса в нем не появятся.

Ответ 5. Чтобы найти путь от s до t в процедуру печати пути вместо одномерного массива D расстояний нужно передавать s–ю строку двумерного массива D.