TwiddleLab / Искусственный интеллект / Поиск, игры и планы
Эвристики: A* находит путь
Что ты узнаешь
- Эвристика это быстрая догадка об оставшемся расстоянии, например шагов до звезды, если бы не было стен.
- A* даёт каждой ждущей клетке счёт f = g + h: пройденные шаги плюс догадка, и берёт самый маленький.
- Если догадка никогда не говорит «дальше», чем на самом деле, A* всё равно находит самый короткий путь и проверяет намного меньше клеток.
- Если слишком доверять догадке, поиск ускоряется, но путь удлиняется.
Как идёт урок
Поиск в ширину проверил 63 клетки, чтобы пройти этот лабиринт. Робот знает, где звезда. Сколько проверит поиск поумнее?
Дай роботу чувство направления. Заполни недостающие догадки.
Догадка это число шагов до звезды, если бы не было стен: клетки по горизонтали плюс клетки вверх или вниз.
Догадка не учитывает стены, поэтому это просто расстояние по сетке: |dx| + |dy|. Её быстро считать, и она никогда не говорит «дальше», чем настоящий путь.
Теперь каждая ждущая клетка получает счёт: пройденные шаги плюс догадка.
f = g + h. Поиск всегда берёт карточку с самым маленьким f. «Шаг» или «Пуск».
У этого поиска знаменитое название.
Догадка это эвристика. Поиск, который берёт самый маленький f = g + h, это A* (читается «A-звезда»). Так находят путь персонажи игр и приложения с картами.
A* на паузе. Нажми на клетку, которую он проверит следующей.
На каждой жёлтой карточке g + h. Побеждает самая маленькая сумма. Ничья? Подойдёт любая.
А если робот будет больше доверять догадке? Найди лучшее w.
f = g + w x h. Найди w, при котором проверяется меньше всего клеток, а путь всё ещё самый короткий.
При w = 0 догадка не учитывается, и A* ведёт себя как поиск в ширину. При w = 1 это обычный A*, он сохраняет самый короткий путь. Большое w доверяет догадке больше, чем пройденным шагам: робот спешит к звезде, проверяет меньше клеток и может пропустить самый короткий путь.
Два способа угадать расстояние. Запусти оба и выбери лучшую догадку.
Клетки по горизонтали плюс вверх или вниз, или прямая линия (Пифагор: квадратный корень из dx² + dy²). Робот может двигаться только по сетке.
Обе догадки никогда не говорят «дальше», чем настоящий путь, поэтому обе сохраняют самый короткий путь. Но робот на сетке не ходит по диагонали, поэтому прямая линия всегда занижает. Подсчёт клеток ближе к правде, а более точная догадка значит меньше лишних проверок.
Одна догадка неверна, и A* пропустил самый короткий путь. Найди её.
Нажми на серую догадку, чтобы сверить её с настоящим подсчётом.
Клетка в проходе всего в 7 клетках от звезды по сетке, но её догадка сказала 12. A* поверил, дал проходу высокий счёт и пошёл в обход снизу. A* сохраняет самый короткий путь, только если ни одна догадка не говорит «дальше», чем на самом деле.
Гонка с машиной: A* это ты.
Каждый ход нажимай на жёлтую клетку с самым маленьким g + h. Две жизни. Сможешь не отстать от машины?
Предыдущий урок: В ширину и в глубину · Следующий урок: Деревья игр · Часть курса: Поиск, игры и планы
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
