TwiddleLab / Искусственный интеллект / Поиск, игры и планы

Поиск в ширину и в глубину

Урок 2 из 11 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Поиск хранит список ожидания из клеток, которые он нашёл, но ещё не проверил.
• Поиск в ширину берёт самую старую карточку (это очередь). Он расходится кольцами и находит самый короткий путь.
• Поиск в глубину берёт самую новую карточку (это стек). Он ныряет вглубь и находит путь, но не всегда самый короткий.
• В коде разница в одной строке: todo.pop(0) или todo.pop().

Начать урок

Как идёт урок

1. Робот видит только соседние клетки. Какой план точно найдёт самый короткий путь до звезды?

2. План первый: круги на воде.

   Пройди его по шагам. Каждая проверенная клетка показывает, сколько до неё шагов от старта.

3. Теперь ты круги на воде. Нажми на клетку, которую он проверит следующей.

   Жёлтые клетки в списке ожидания. Круги на воде всегда берут самую старую карточку.

4. План второй: нырок.

   Тот же лабиринт, тот же список. Меняется только одно: он берёт самую новую карточку.

5. У двух планов есть названия.

   Поиск в ширину берёт самую старую карточку. Такой список это очередь: первым пришёл, первым вышел. Поиск в глубину берёт самую новую карточку. Такой список это стек: последним пришёл, первым вышел.

6. Теперь ты нырок. Нажми на клетку, которую он проверит следующей.

   Поиск в глубину берёт самую новую карточку из списка.

7. Этот робот должен искать в ширину, а он ныряет. Исправь его код.

   В Python список ожидания это список todo. Запусти, поменяй одну строку, запусти снова.

   Новые клетки добавляются в конец todo. todo.pop() берёт конец, самую новую: это поиск в глубину. todo.pop(0) берёт начало, самую старую: это поиск в ширину. Одна строка решает весь поиск.

8. Отправь нырок в обход.

   Добавляй стены в этот открытый лабиринт, пока путь нырка не станет хотя бы 32 шага.

9. Спасательный дрон должен добраться до звезды самым коротким путём через твой лабиринт. Какой список ему взять?

   Запусти оба, потом нажми на поле, которому доверяешь.

   Поиск в ширину проверяет клетки по порядку расстояния, поэтому, впервые дойдя до звезды, он уже нашёл самый короткий путь. Поиск в глубину может добраться раньше или позже, но его путь бывает намного длиннее.

10. Скоростной раунд: четыре маленьких лабиринта. Нажми на следующую клетку.

    На каждом поле написано, какой план там работает. Три жизни.

Предыдущий урок: ИИ как поиск · Следующий урок: Эвристики: A* находит путь · Часть курса: Поиск, игры и планы

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.