TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Поиск с возвратом: проходим лабиринт
Что ты узнаешь
- Поиск с возвратом: попробуй выбор и иди глубже; в тупике отмени последний выбор и попробуй следующий.
- В коде каждый вызов пробует свои варианты по порядку и возвращает False, когда ни один не сработал, и тогда вызвавший пробует свой следующий вариант.
- Отмечай посещённые клетки, иначе поиск ходит по кругу, пока стек не переполнится.
- Линия мелом это стек вызовов. Заливка и поиск в ИИ работают так же.
Как идёт урок
Ты в лабиринте, а в кармане мел. Есть ли правило, которое всегда выведет?
Дойди до звезды. Мел отмечает путь; шаг назад его стирает.
Робот следует одному правилу: пробуй вправо, потом вниз, потом влево, потом вверх.
Где он впервые упрётся в тупик и повернёт назад? Нажми на клетку.
Смотри на робота. Мел это его стек вызовов.
Каждая клетка это вызов solve(r, c). Тупик возвращает False, и робот отступает.
solve(r, c) по очереди вызывает solve у своих соседей. Если все возвращают False, он тоже возвращает False, его карточка снимается со стека, и вызвавший пробует своего следующего соседа. Это и есть поиск с возвратом.
Поиск с возвратом.
Поиск с возвратом это полный перебор, который рано сдаётся: иди по одному выбору; как только он безнадёжен, отмени его и попробуй следующий.
Каждый выбор это рекурсивный вызов. Тупик возвращает False, и управление возвращается к вызвавшему, который пробует свой следующий вариант.
Отметка посещено (мел) не даёт поиску ходить по кругу. Базовые случаи: цель говорит True, стена или мел говорят False.
Предскажи робота в лабиринте побольше.
На каждой развилке нажми на клетку, куда он пойдёт дальше. Вправо, вниз, влево, вверх.
Напиши робота: solve(r, c).
Сначала базовые случаи: цель говорит True, всё, кроме открытого пола, говорит False. Потом отметь клетку мелом и пробуй четырёх соседей.
or пробует каждого соседа слева направо и останавливается на первом True, поэтому порядок вправо, вниз, влево, вверх заложен в одну строку. return False в конце это шаг назад.
Этот робот забыл мел. Он падает. Исправь.
Без отметок он вечно ходит туда-сюда между двумя клетками.
Из (3, 3) робот пробует влево в (3, 2), а из (3, 2) пробует вправо обратно в (3, 3), бесконечно. Отметка мелом делает так, что второе посещение попадает в базовый случай != "." и возвращает False.
Заливка: тот же робот, только без цели.
Заливка заходит в клетку, красит её и расходится вправо, вниз, влево, вверх. Повтори цель как можно меньшим числом нажатий.
Новый лабиринт. Нарисуй линию мелом, с которой закончит робот.
Тупики стираются, поэтому мел остаётся только на пути к звезде. Потом «Проверить».
Когда solve доходит до G, каждый вызов на стеке возвращает True, не стирая свой мел. Эти клетки и есть путь от старта до цели.
Твой решатель в лабиринте, которого он никогда не видел.
Тот же код, лабиринт побольше. Нажми «Запуск». ИИ-планировщики ищут так же: вглубь, отступая в тупиках.
Предыдущий урок: Перебираем всё: подмножества и порядки · Следующий урок: Решатель судоку · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
