Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Лекции - Структуры и алгоритмы компьютерной обработки данных / 13.Перебор с возвратом. Общая схема перебора

.doc
Скачиваний:
81
Добавлен:
06.02.2015
Размер:
36.35 Кб
Скачать

Перебор с возвратами

Решение задачи – некоторая последовательность (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;

Соседние файлы в папке Лекции - Структуры и алгоритмы компьютерной обработки данных