Алгоритмы с возвратом
Алгоритмы с возвратом (backtrack) / алгоритмы последовательных испытаний используются в задачах, в которых поиск решения не подчиняется твердым правилам, а выполняется путем последовательных испытаний; если испытание не приводит к результату, то «возвращаются назад» для других попыток. Данный подход часто применяют в области искусственного интеллекта.
Поиск всех возможных решений (схема)
Схема:
procedure Try (i: integer); {i – глубина рекурсии} var k: integer;
begin
for k:=1 to m do {кол-во путей}
begin выбор k-го кандидата;
if кандидат подходит then его запись;
if i<n {решение не полное} then Try(i+1)
else печать решения стереть запись end end |
|
Поиск первого «хорошего» решения (две схемы + пример)
Схема 1:
procedure Try;
begin
инициация выбора кандидата;
repeat
выбор очередного кандидата;
if кандидат подходит then
begin
его запись;
if решение не полное then
begin
Try;
if неудача then стирание записи;
end;
end;
until удача or кандидатов больше нет; end; |
|
Схема 2:
procedure Try (i: integer);
begin
k:=0;
repeat
k:=k+1; выбор k-го кандидата
if кандидат подходит then
begin
его запись;
if i < n then
begin
Try(i+1);
if неудача then стирание записи;
end;
end;
until удача or (k=m); end; |
|
Пример:
Дана система двухсторонних дорог. Найти путь от города А в город В.
const maxN=10;
type
TIndex=1..MaxN;
TMatr=array[TIndex,TIndex]of boolean;
TSet=set of TIndex;
TPath=array[TIndex] of TIndex;
var
Roads:TMatr;
A,B: TIndex;
p:TPath;
len:integer; //длина пути
function FindPath(t:TIndex; var visited:TSet):boolean;
var i:integer;
begin
if t=B then result:=true
else
begin
i:=1;
result:=false;
while (i<=MaxN) and not result do
if Roads[t,i] and not (i in visited) then
begin
len:=len+1;
P[len]:=i;
Include(visited,i);
result:=FindPath(i,visited);
if not result then
begin
Exclude(i,visited);
len:=len-1;
i:=i+1;
end;
end
else i:=i+1;
end;
end;
//Вызов рекурсии
function MainFind:boolean;
var v:TSet;
begin
len:=1;
P[len]:=A;
v:=[A];
result:=FindPath(A,v)
end; |
Поиск оптимального решения (схема + пример см. Н.Вирт стр. 197)
