Механизм рекурсии весьма эффективен при программировании задач поиска. В качестве еще одного примера рассмотрим задачу поиска пути между двумя городами. Если несколько городов соединены дорогами, то очевидно, что попасть из одного города в другой можно различными маршрутами. Задача состоит в нахождении всех возможных маршрутов.

Карта дорог между городами может быть изображена в виде графа - набора вершин, означающих города, и ребер, обозначающих дороги (рис. 12.9).

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

Пусть, например, надо найти все возможные пути из точки 1 в точку 5. Согласно принятому правилу, сначала выбираем точку 2. На следующем шаге выясняем, что точка 2 тупиковая, поэтому возвращаемся в точку 1 и делаем шаг в точку 3. Из точки 3 - в точку 4, из 4 - в 6 и из точки 6 - в точку 5. Один маршрут найден. После этого возвращаемся в точку 6 и проверяем, возможен ли шаг в точку, отличную от 5. Так как это возможно, то делаем шаг в точку 7 и затем в 5. Найден еще один путь. Таким образом, процесс поиска состоит из шагов вперед и возвратов назад. Поиск завершается, если из узла начала движения уже некуда идти.

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

Рис. 12.9. Представление карты дорог в виде графа

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

Граф можно представить двумерным массивом, который назовем тар (карта). Значение элемента массива map [i, j ] - это расстояние между городами inj, если города соединены дорогой, или ноль, если города не соединены прямой дорогой. Для приведенного графа массив тар можно изобразить в виде таблицы следующим образом:

Содержимое ячейки таблицы на пересечении строки і и столбца j соответствует значению тар [i, j ].

Помимо массива тар нам потребуются массив road (дорога) и массив inci (от include - включать). В массив road мы будем записывать номера пройденных городов. В момент достижения конечной точки он будет содержать номера всех пройденных точек, т. е. описание маршрута.

В inci[i] будем записывать true, если точка с номером і включена в маршрут. Делается это для того, чтобы не включать в маршрут уже пройденную точку (не ходить по кругу).

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

На рис. 12.10 приведена блок-схема алгоритма процедуры выбора очередной точки формируемого маршрута, а нарис. 12.11 - диалоговое окно программы.

Рис. 12.10. Блок-схема процедуры выбора точки маршрута

Для ввода массива, представляющего описание карты, используется компонент 31;г:тдСг1а1 (значения его свойств приведены в табл. 12.1), для вывода результата (найденного маршрута) - поле метки Label 1. Начальная и конечная точки маршрута задаются вводом значений в поля редактирования Editi и Edit2. Процедура поиска запускается нажатием кнопки Поиск (Buttonl). Поля меток Label2, Label3 и Label4 используются для вывода поясняющего текста.

Рис. 12.11. Окно программы Поиск маршрута

Таблица 12.1. Значения свойств компонента stringeridi

Свойство

Значение

Свойство

Значение

Name

StringGridl

FixedRows

ColCount

Options.goEditing

TRUE

RowCount

DefaultColWidth

FixedCols

Default RowHe і ght

Текст программы приведен в листинге 12.5.

Листинг 12.5. Поиск маршрута

unit road_; interface
uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids;
type TForml = class(TForm)
StringGridl: TStringGrid;
Editl: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Buttonl: TButton;
Label4: TLabel;

procedure FormActivate(Sender: TObject); procedure ButtonlClick(Sender: TObject); private { Private declarations } public

{ Public declarations } end;

var Forml: TForml; implementation

{$R *.DFM}
procedure TForml.FormActivate(Sender: TObject); var
i: integers-begin
// нумерация строк for i:=l to 10 do
StringGridl.Cells[0,i]:=IntToStr(i); // нумерация колонок for i:=l to 10 do
StringGridl.Cells[i,0]:=IntToStr(i); // описание предопределенной карты StringGridl. Cells [1,2] : = Ч'; StringGridl.Cells [2,1] : = 4'; StringGridl.Cells[1,3]:='l'; StringGridl.Cells[3,1]:='l'; StringGridl.Cells [1, 4] : = 4'; StringGridl.Cells [4,1] : = 4'; StringGridl.Cells[3,7]:='l'; StringGridl.Cells[7,3]:='l'; StringGridl.Cells[4,6]:='l'; StringGridl.Cells[6,4]:='!';
StringGridl.Cells [5, 6] : = Ч'; StringGridl.Cells[6,5]:='l'; StringGridl.Cells[5,7]: = 4\-StringGridl.Cells[7,5]:='l'; StringGridl.Cells [6,7] : = 4\-StringGridl.Cells[7,6]:='l';
end;
procedure TForml.ButtonlClick(Sender: TObject);
const

N=10;// кол-во вершин графа var map:array[l..N,1..N]of integer; // Карта.map[i,j]не 0, // если точки i и j соединены road:array[1..N]of integer; // Дорога - номера точек карты

incl:array[l..N]of boolean; // incl[i] равен TRUE, если точка

// с номером i включена в road start,finish:integer; // Начальная и конечная точки

found:boolean;
i, j : integers-procedure step(s,f,p:integer); var с:integer; // Номер точки, в которую делаем очередной шаг i: integers-begin
if s=f then begin
// Точки s и f совпали ! found:=TRUE;
Label1.caption:=Labell.caption+#13+'Путь:'; for i:=l to p-1 do
Label1.caption:=Labell.caption+' Ч-IntToStr(road[i]);

end else begin // выбирем очередную точку for c:=l to N do begin // проверяем все вершины if (map [s, с] о 0) and (NOT incl [c] ) // точка соединена с текущей и не включена в маршрут then begin road[p]:=с; // добавим вершину в путь

incl[с]:=TRUE; // пометим вершину как включенную

step (с, f ,р+1) ;
incl[с]:=FALSE;
road[p]:=0;
end;
end;
end;

end; // конец процедуры step

begin
Labell.caption:='';

// инициализация массивов

for i:=l to N do road[i]:=0;
for i:=l to N do incl[i]:=FALSE;

// ввод описания карты из SrtingGrid.Cells for i:=l to N do for j:=1 to N do if StringGridl.Cells[i, j] <> "

then map[i,j]:=StrToInt(StringGridl.Cells[i,j]) else map[i,j]:=0;
start :=StrToInt(Editl.text);
finish:=StrToInt(Edit2.text);

road[1]:=start; // внесем точку в маршрут

incl[start]:=TRUE; // пометим ее как включенную

step(start,finish,2); // ищем вторую точку маршрута

// проверим, найден ли хотя бы один путь if not found

then Labell.caption:='Указанные точки не соединены!';
end;
end.

При запуске программы в момент активизации формы приложения происходит событие onActivate, процедура обработки которого заполняет массив StringGridl.ceils значениями, представляющими описание карты. Эта же процедура нумерует строки и столбцы таблицы, заполняя зафиксированные

ЯЧеЙКИ ПерВОГО СТОЛбца И ПерВОЙ СТРОКИ StringGridl.

Поиск маршрута инициирует процедура TFormi.Buttoniciick, которая запускается нажатием кнопки Поиск. Для поиска точки, соединенной с исходной, процедура TFormi .Buttoniciick вызывает процедуру step, которая, после выбора первой точки, соединенной с начальной, и включения ее в маршрут, вызывает сама себя. При этом в качестве начальной точки задается уже не исходная, а текущая, только что включенная в маршрут точка.

Кривая Гильберта || Оглавление || Поиск кратчайшего пути


Delphi 6. Программирование на Object Pascal



Новости за месяц

  • Ноябрь
    2018
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс