Лекции - Структуры и алгоритмы компьютерной обработки данных / 13.Перебор с возвратом. Общая схема перебора
.docПеребор с возвратами
Решение задачи – некоторая последовательность (an), имеющая определенные свойства. На каждом шаге добавляется новый элемент ak. Если новый элемент добавить нельзя, возвращаемся на предыдущий шаг и пытаемся выбрать другой элемент.
Вводятся понятия номер хода и номер варианта.
Задача о выходе из лабиринта
Матрица L[1..m,1..n].
L[i,j] = 0 – клетка свободна
L[i,j] < 0 – клетка занята препятствием
L[i,j] = k >0 – клетка посещена на k-ом ходу.
Варианты:
procedure search(k,x,y: integer);
var i,x1,y1: integer;
begin
i:=0; {инициализация выбора варианта}
repeat
inc(i); x1:=x; y1:=y;
case i of
1: dec(y); 2: inc(x); 3: inc(y); 4: dec(x);
end; {выбор варианта}
if l[x,y]=0 {подходит} then begin
l[x,y]:=k; {запись варианта}
if (x<>1) and (x<>n) and (y<>1) and (y<>m) {решение неполное}
then search(k+1,x,y) {ищем дальше} else
begin
print(l); halt(0); {решение получено}
end;
l[x,y]:=0; {стирание варианта}
end; x:=x1; y:=y1;
until i=4; {все перебрали}
end;
Поиск кратчайшего пути
Необходимо перебрать все пути до выхода и выбрать путь с наименьшей длиной.
Общая схема перебора с возвратами
procedure search(k: integer);
begin
{инициализация выбора варианта}
repeat
{выбор варианта}
if {подходит} then
begin
{запись варианта}
if {решение неполное}
then search(k+1) {ищем дальше}
else found:=true;
if not(found) then
{стирание варианта}
end;
until found or {все перебрали};
end;
Задача о расстановке ферзей
Расставить на шахматной доске 8 ферзей, чтобы они не били друг друга.
Номер хода – номер ферзя.
Номер варианта – номер вертикали, куда ставим ферзя.
Схема поиска расстановки ферзей
procedure search(k: integer);
begin
i:=0;{инициализация выбора варианта}
repeat
{выбор варианта} inc(i);
if check (k,i) {подходит} then
begin
v[k]:=i;{запись варианта}
if k<8 {решение неполное}
then search(k+1) {ищем дальше}
else print(v);
v[k]:=0;{стирание варианта}
end;
until (i=8); {все перебрали};
end;