Поиск с возвратом (Перебор с возвратом) Введение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов. - презентация

1 Поиск с возвратом (Перебор с возвратом) Введение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов

2 Введение Поиск с возвратом (Backtracking) общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.

3 Решение задачи методом поиска с возвратом сводится к последовательному расширению частичного решения. Если на очередном шаге такое расширение провести не удается, то возвращаются к более короткому частичному решению и продолжают поиск дальше. Данный алгоритм позволяет найти все решения поставленной задачи, если они существуют. Для ускорения метода стараются вычисления организовать таким образом, чтобы как можно раньше выявлять заведомо неподходящие варианты. Зачастую это позволяет значительно уменьшить время нахождения решения.

4 Задача о лабиринте (поиск единственного решения) Имеется прямоугольная матрица n x m, который задается лабиринт. Нули в матрице обозначают проход, минус единицы - стены. Нужно найти путь из заданной клетки (вход) в другую заданную клетку (выход). Ходы разрешается делать только по горизонтали и вертикали, и только по проходам. Гарантируется, что путь существует.

5 Входные данные. Количество столбцов и количество строк n и m (1 <= N,M <= 6). Координаты старта и координаты финиша. Матрица лабиринта. Пример входных данных

6 Выходные данные. Матрица лабиринта, в которой помечен путь до выхода Пример выходных данных

7 const maxn = 20; { макс размер лабиринта } dx: array [1..4] of integer = (-1, 0, 1, 0); dy: array [1..4] of integer = ( 0, -1, 0, 1); var a: array [0..maxn+1, 0..maxn+1] of integer; n, m, { размеры лабиринта } sx, sy, { начальное положение } fx, fy: integer; { положение выхода }

8 procedure init; var i, j: integer; begin for i := 0 to maxn+1 do { барьеры } for j := 0 to maxn+1 do a[i, j] := -1; assign(input, 'labirint.in'); reset(input); read(n, m, sx, sy, fx, fy); for i := 1 to m do for j := 1 to n do read(a[i, j]); end;

9 procedure print_labirint; var i, j: integer; begin writeln; for i := 1 to n do begin for j := 1 to m do write(a[i, j]:4); writeln; end;

10 procedure search(x, y, k: integer); var i: integer; begin a[y, x] := k; {запись варианта} if (x = fx) and (y = fy) then {решение найдено} begin print_labirint; {вывод решения} halt; end else for i := 1 to 4 do {перебор всех вариантов} if a[y+dy[i], x+dx[i]] = 0 then {вариант подходит} search(x+dx[i], y+dy[i], k+1); {рекурсивный вызов} a[y, x] := 0; {стирание варианта} end;

11 begin init; search(sx, sy, 1); end.

12 Числа Вася Пупкин из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 пытается составить число a 1 a 2 …a n такое, в котором Первая цифра не ноль; Нет повторяющихся цифр; Число a 1 a 2 делится на 2, a 1 a 2 a 3 делится на 3, …, a 1 a 2 …a n делится на n. Помогите ему. Составьте программу, которая находит наибольшее число, начинающееся на введенную пользователем по запросу первую цифру a 1 и удовлетворяющую поставленным Васей условиям. Например: Первая цифра 5 Искомое число

13 program Chislo; uses crt; type massiv=array[1..10] of integer; var lr:massiv; dl,i:integer; function proverka1(a:massiv;n:integer):boolean; var i:integer; begin proverka1:=true; for i:=1 to n-1 do if (a[i]=a[n]) then proverka1:=false; end;

14 function proverka2(a:massiv;n:integer):boolean; var i,m:integer; begin proverka2:=false; m:=0; for i:=1 to n do m:=(m*10+a[i]) mod n; if ((m=0) or (n=1)) then proverka2:=true; end;

15 procedure sled(a:massiv;n:integer); var i:integer; begin if (dl=n) then for i:=1 to n do lr[i]:=a[i] else if (n>dl) then begin for i:=1 to n do lr[i]:=a[i]; dl:=n; end; if (n<10) then for i:=0 to 9 do begin a[n+1]:=i; if (proverka1(a,n+1) and proverka2(a,n+1)) then sled(a,n+1); end;

16 begin clrscr; dl:=0; for i:=1 to 10 do lr[i]:=0; writeln(Первая цифра ');read(lr[1]); sled(lr,1); write('Ответ '); for i:=1 to dl do write(lr[i]); writeln; readkey; end.

17 И это еще не все, но... КОНЕЦКОНЕЦ