Решение задачи обхода лабиринта с помощью перебора с возвратом Учитель информатики и ИТ Е.А. Перова Н.Новгород 2011 Муниципальное образовательное учреждение Лицей 36

Цель урока: изучить метод перебора с возвратом на примере задачи обхода лабиринта Задачи урока формировать умение составлять рекурсивный алгоритм для решения задачи методом перебора с возвратом развивать у учащихся познавательный интерес и критическое мышление развивать творческие способности прививать учащимся навыки самостоятельной и исследовательской работы

Цель – попасть из некоторой заданной клетки в другую заданную клетку. За один шаг можно переместиться в одну из соседних клеток по горизонтали или вертикали, если нет перегородки X Y 345 Пример лабиринта Задача обхода лабиринта Два правила: 1) В каждой клетке выбирать еще не исследованный путь. 2) Если из исследуемой клетки не ведут неисследованные пути, вернуться на одну клетку назад по последнему пройденному пути.

Перебор с возвратом (backtrack) - это общий метод упорядоченного перебора.

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

и т.д. Решение: A=(ENNWNEEEENW) X Y 345 Поиск решения для примера M={N,S,W,E} - множество направлений: N - север, S - юг, W - запад, E - восток. Нач. вектор: B=(), клетка (1,1) Шаг 1: S 1 ={E}, B=(E), клетка (2,1) Шаг 2: S 2 ={N,E}, B=(EN), кл. (2,2) Шаг 3: S 3 ={N}, B=(ENN), кл. (2,3) Шаг 4: S 4 ={W,E}, B=(ENNW), кл. (1,3) Шаг 5: S 5 ={N}, B=(ENNWN), кл. (1,4) Шаг 6: S 6 ={N,E}, B=(ENNWNN) кл. (1,5) Шаг 7: S 7 =Ø, возврат в клетку (1,4) Шаг 8: S 6 ={E}, B=(ENNWNE), кл. (2,4),

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

X Y 345 Задача обхода лабиринта размеры лабиринта координаты старта координаты финиша матрица лабиринта матрица лабиринта с маршрутом n, m SX, SY fX, fY смещение dx, dy Исходные данные Результат a[i,j]

X Y 345 Матрица лабиринта Стены кодируем -1, проходы – 0.

Пример входных данных 9 9 размеры лабиринта 1 1 координаты старта и 7 1 координаты финиша – задаем с клавиатуры матрица лабиринта – читаем из файла. Пример выходных данных матрица лабиринта с маршрутом – выводим на экран

program obhodlab; uses crt,fileutil,sysutils; 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; { конечное положение}

procedure init; var i, j: integer; var labirint : text; begin for i := 0 to maxn+1 do { барьеры } for j := 0 to maxn+1 do a[i, j] := -1; read(n, m, sx, sy, fx, fy); { исходные данные } аssignfile(labirint,'lab.txt'); reset(labirint); for i:=1 to n do for j := 1 to m do begin read(labirint,a[i, j]); end; closefile(labirint); end;

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;

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;

{ основная программа} begin init; search(sx, sy, 1); end.

Давайте обсудим Назовите достоинства и недостатки метода перебора с возвратом Назовите недостатки рассмотренного решения Как можно их исправить? Как можно переформулировать задачу?

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

Источники: Перебор с возвратом». Материалы Проекта «Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в Приволжском федеральном округе» по направлению «Дополнительная подготовка школьников по дисциплине «Информатика и информационные технологии»». Раздел «Перебор с возвратом». Л.П. Жильцова. (Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Нижегородский государственный университет им. Н.И. Лобачевского) Мозговой М.В. Занимательное программирование: Самоучитель. – СПб.: Питер,