Первая помощь
<<  Логопедическая помощь для детей средней комбинированной группы «Мы всегда рядом» - организация домашнего визитирования по оказанию квалифицированной помощи в домашних условиях семьям с детьми-инвалидами  >>
Решение задачи обхода лабиринта с помощью перебора с возвратом
Решение задачи обхода лабиринта с помощью перебора с возвратом
Цель урока: изучить метод перебора с возвратом на примере задачи
Цель урока: изучить метод перебора с возвратом на примере задачи
Задача обхода лабиринта
Задача обхода лабиринта
Перебор с возвратом (backtrack) - это общий метод упорядоченного
Перебор с возвратом (backtrack) - это общий метод упорядоченного
Перебор с возвратом применяется для решения комбинаторных задач, в
Перебор с возвратом применяется для решения комбинаторных задач, в
Поиск решения для примера
Поиск решения для примера
Общая схема рекурсивного перебора
Общая схема рекурсивного перебора
Задача обхода лабиринта
Задача обхода лабиринта
Матрица лабиринта
Матрица лабиринта
Пример входных данных 9 9 размеры лабиринта 1 1 координаты старта и 7
Пример входных данных 9 9 размеры лабиринта 1 1 координаты старта и 7
Program obhodlab; uses crt,fileutil,sysutils; const maxn=20; dx: array
Program obhodlab; uses crt,fileutil,sysutils; const maxn=20; dx: array
Procedure init; var i, j: integer; var labirint : text; begin for i :=
Procedure init; var i, j: integer; var labirint : text; begin for i :=
procedure print_labirint; var i, j: integer; begin writeln; for i := 1
procedure print_labirint; var i, j: integer; begin writeln; for i := 1
Procedure search(x, y, k: integer); var i: integer; begin a[y, x] := k
Procedure search(x, y, k: integer); var i: integer; begin a[y, x] := k
{ Основная программа} begin init; search(sx, sy, 1); end
{ Основная программа} begin init; search(sx, sy, 1); end
Давайте обсудим
Давайте обсудим
Задания для самостоятельной работы
Задания для самостоятельной работы
Источники:
Источники:

Презентация на тему: «Решение задачи обхода лабиринта с помощью перебора с возвратом». Автор: Гергель В.П.. Файл: «Решение задачи обхода лабиринта с помощью перебора с возвратом.ppt». Размер zip-архива: 456 КБ.

Решение задачи обхода лабиринта с помощью перебора с возвратом

содержание презентации «Решение задачи обхода лабиринта с помощью перебора с возвратом.ppt»
СлайдТекст
1 Решение задачи обхода лабиринта с помощью перебора с возвратом

Решение задачи обхода лабиринта с помощью перебора с возвратом

Учитель информатики и ИТ Е.А. Перова

Муниципальное образовательное учреждение Лицей № 36

Н.Новгород 2011

2 Цель урока: изучить метод перебора с возвратом на примере задачи

Цель урока: изучить метод перебора с возвратом на примере задачи

обхода лабиринта

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

3 Задача обхода лабиринта

Задача обхода лабиринта

Цель – попасть из некоторой заданной клетки в другую заданную клетку. За один шаг можно переместиться в одну из соседних клеток по горизонтали или вертикали, если нет перегородки.

Два правила: 1) В каждой клетке выбирать еще не исследованный путь. 2) Если из исследуемой клетки не ведут неисследованные пути, вернуться на одну клетку назад по последнему пройденному пути.

Пример лабиринта

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

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

перебора.

5 Перебор с возвратом применяется для решения комбинаторных задач, в

Перебор с возвратом применяется для решения комбинаторных задач, в

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

6 Поиск решения для примера

Поиск решения для примера

M={N,S,W,E} - множество направлений: N - север, S - юг, W - запад, E - восток.

Нач. вектор: B=(), клетка (1,1)

Шаг 1: S1={E}, B=(E), клетка (2,1)

Шаг 2: S2={N,E}, B=(EN), кл. (2,2)

Шаг 3: S3={N}, B=(ENN), кл. (2,3)

Шаг 4: S4={W,E}, B=(ENNW), кл. (1,3)

Шаг 5: S5={N}, B=(ENNWN), кл. (1,4)

Шаг 6: S6={N,E}, B=(ENNWNN) кл. (1,5)

Шаг 7: S7=?, возврат в клетку (1,4)

Шаг 8: S6={E}, B=(ENNWNE), кл. (2,4),

и т.д. Решение: A=(ENNWNEEEENW)

7 Общая схема рекурсивного перебора

Общая схема рекурсивного перебора

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

8 Задача обхода лабиринта

Задача обхода лабиринта

Исходные данные

n, m

Размеры лабиринта

Координаты старта

SX, SY

Координаты финиша

fX, fY

Матрица лабиринта

a[i,j]

dx, dy

Смещение

Результат

a[i,j]

Матрица лабиринта с маршрутом

9 Матрица лабиринта

Матрица лабиринта

Стены кодируем -1, проходы – 0.

10 Пример входных данных 9 9 размеры лабиринта 1 1 координаты старта и 7

Пример входных данных 9 9 размеры лабиринта 1 1 координаты старта и 7

1 координаты финиша – задаем с клавиатуры матрица лабиринта – читаем из файла. Пример выходных данных 7 8 9 0 0 матрица лабиринта с маршрутом – выводим на экран 6 -1 -1 0 -1 5 4 -1 0 0 -1 3 -1 -1 -1 1 2 0 0 0

11 Program obhodlab; uses crt,fileutil,sysutils; const maxn=20; dx: array

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; { конечное положение}

12 Procedure init; var i, j: integer; var labirint : text; begin for i :=

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;

13 procedure print_labirint; var i, j: integer; begin writeln; for i := 1

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; end;

14 Procedure search(x, y, k: integer); var i: integer; begin a[y, x] := k

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;

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

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

16 Давайте обсудим

Давайте обсудим

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

17 Задания для самостоятельной работы

Задания для самостоятельной работы

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

Сгенерировать обход конем шахматной доски, так чтобы покрыть всю область.

18 Источники:

Источники:

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

«Решение задачи обхода лабиринта с помощью перебора с возвратом»
http://900igr.net/prezentacija/obg/reshenie-zadachi-obkhoda-labirinta-s-pomoschju-perebora-s-vozvratom-223837.html
cсылка на страницу

Первая помощь

29 презентаций о первой помощи
Урок

ОБЖ

59 тем
Слайды
900igr.net > Презентации по ОБЖ > Первая помощь > Решение задачи обхода лабиринта с помощью перебора с возвратом