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

Проект: робот-навигатор

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

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

• Поиск в ширину находит путь с наименьшим числом клеток, но по дороге проверяет много клеток.
• A* использует догадку об оставшемся расстоянии и проверяет намного меньше клеток; если слишком доверять догадке, путь может стать длиннее.
• Когда клетки стоят по-разному (стоимость пути), наименьшее число клеток не всегда самое быстрое. A*, который складывает стоимости, находит самый дешёвый путь.
• Приложения с картами делают то же с пробками: каждая дорога получает стоимость в минутах.

Начать урок

Как идёт урок

1. Робот-доставщик должен пересечь парк, пока мороженое не растаяло. Выбери ему мозг. Но сначала выбери парк.

   Нажми на парк.

2. Сделай парк своим: поставь на пути несколько скамеек.

   Нажимай на клетки или проводи по ним. Оставь путь до звезды длиной 28 шагов или меньше.

3. Мозг первый: поиск в ширину. Запусти его на своём парке.

   Он находит самый короткий путь. Смотри, сколько клеток он проверяет по дороге.

4. Батарея у робота маленькая. Какой мозг ему дать?

   Запусти оба на своём парке, потом нажми на свой выбор.

   Оба находят самый короткий путь, потому что догадка по клеткам никогда не говорит «дальше», чем на самом деле. A* тратит проверки возле линии к звезде, поэтому экономит батарею.

5. Новая задача: не все клетки проходятся за одинаковое время.

   Грязь медленная: 3 минуты на клетку вместо 1. Сумма это стоимость пути. Поиск в ширину считает клетки; A* может вместо этого складывать стоимости (g становится минутами на пути) и найти самый дешёвый путь.

6. Нарисуй в парке грязь так, чтобы самый быстрый маршрут обходил её.

   Синий пунктир: маршрут с наименьшим числом клеток. Зелёный: маршрут с наименьшим числом минут.

7. Настрой, насколько робот доверяет догадке на твоём парке.

   f = g + w x h. Найди w, при котором проверяется меньше всего клеток, а путь всё ещё самый короткий.

   В открытых парках догадка близка к правде, поэтому доверие чуть больше 1 может сэкономить проверки, не удлиняя путь. Если перестараться, робот кидается в тупики возле звезды.

8. Большой парк: поиск в ширину проверяет 188 клеток, чтобы его пересечь. Сколько проверит A*?

   Поставь булавку.

9. Классика: доставка через большой парк.

   Путь не больше 30 клеток, проверено не больше 120. Выбери мозг и запускай.

10. Приложение с картами выбирает маршрут через город. Какой оно выберет?

    Пробки (коричневые) занимают 3 минуты на квартал. Свободные дороги 1.

    Маршрут A короче по кварталам, но его 3 квартала в пробке стоят по 3 минуты: 6 + 9 = 15 минут. Маршрут B это 13 свободных кварталов: 13 минут. Навигаторы запускают поиск вроде A* со стоимостями: каждая дорога получает время по живым данным о пробках.

11. Последняя доставка. Мороженое тает через 18 минут. Какого робота отправишь?

    Запусти оба, потом нажми на робота, которого берёшь.

    The squares robot goes straight through 3 mud squares: 13 squares but 19 minutes. The minutes robot walks 17 squares on dry paths: 17 minutes, before the ice cream melts at 18.

Предыдущий урок: Головоломки с ограничениями · Часть курса: Поиск, игры и планы

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