Рекурсия в Delphi: Поиск кратчайшего пути

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

 

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

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

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

Листинг 12.6. Поиск кратчайшего пути

01.procedure TForml.ButtonlClicMSender: TObject) ;
02.const
03.N=10;I кол-во вершин графа}
04.var
05.map:array[1..N,1..N]of integer;// Карта.mapti,j] не О.если
06.// точки i и j соединены
07.road:array[1..NJof integer// Дорога — номера точек карты
08.incl:array[1..N]of boolean// incl Щравен TRUE, если точка
09.// с номером 1 включена в road
10.start,finish:integer// Начальная и конечная точки
11.found:boolean;
12.len:integer// длина найденного (минимального)
13.// маршрута }
14.c_len:integer// длина текущего (формируемого)
15.// маршрута
16.i,j:integer;
17.// выбор очередной точки
18.procedure step(s,f,p:integer];
19.var
20.ciinteger;{ Номер точки, в которую делаем очередной шаг }
21.i:integer;
22.begin
23.if s=f then
24.begin
25. 
26.leri: =c_len;f сохраним длину найденного маршрута }
27.{ вывод найденного маршрута J
28.for i:=l to p-1 do
29.Labell.caption:=Labell.caption+' '+IntToStr(road[ i ] ) ;
30.Labell.caption:^Labell.caption
31.+', длина:'+IntToStr(len)+#13;
32.end
33.else
34.{ выбираем очередную точку ;
35.fox c:=l to N do l проверяем все вершины /
36.if(raap[s,c]<> 0)and(NOT incite])
37.and](len=0)or(c_len+map[5,c]< len))
38.then begin
39.// точка соединена с текущей, но не включена а
40.// маршрут
41.road[p]:=с;{ добавим вершину в путь \
42.incl[с]:=TRUE;{ пометим вершину как включенную 1
43.c_len:=c_len+map(s,c];
44.step(c,f,p+l|;
45.incl [с] —FALSE;
46.road[pj:=0;
47.c_len:=c_len-map[s,c];
48.end;
49.and;{ конец процедуры step I
50.begin
51.Labell.caption:='';
52.f инициализация массивов }
53.for i:=l to do road;=0;
54.for i:=l to Ы do incl;=FALSE;
55.{ ввод описания карты из SrtingGrid.Cells}
56. 
57.for i:=l to Ы do
58.for j:=1 to do
59.if StringGridl.Cells[i,j] <> ' '
60.then map[i,j]:=StrToInt(StringGridl.Cells[i, j ] )
61.else mapli,j]:-0;
62.len:=0// длина найденного (минимального) маршрута
63.с lenr=0// длина текущего (формируемогоJ маршрута
64. 
65.start:=StrToInt(Editl.text);
66.finish:=StrToInt(Edit2.text);
67.road[l]:=start;{ внесем точку в маршрут }
68.inclfstart]:=TRUE;{ пометим ее как включенную I
69.steplstart,finish,2);/ищем вторую точку маршрута }
70.// проверим, найден ли хотя бы один путь
71.if not found
72.then Labell.caption:='Указанные точки не соединены!';
73.end;

 

 

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

dle

Помоги проекту! Расскажи друзьям об этом сайте: