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

ИИ как поиск

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

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

• Состояние это снимок головоломки, например 4 л и 3 л.
• Ход переводит из одного состояния в другое. Все состояния и ходы вместе это пространство состояний.
• Решить головоломку значит провести поиск: найти путь от старта до целевого состояния.

Начать урок

Как идёт урок

1. Кувшин на 5 л, кувшин на 3 л и кран. Можно ли набрать ровно 4 л?

   На кувшинах нет делений. Сначала ставка: какое наименьшее число ходов?

2. Переливай, пока в кувшине на 5 л не будет ровно 4 л.

   Каждое количество, до которого доберёшься, загорается на карте. Норма 6 ходов.

3. Вот все состояния, в которых вообще могут быть кувшины.

   Сейчас 5 л и 0 л. Нажми на каждое состояние, куда можно попасть за один ход.

   Из 5 л и 0 л три хода что-то меняют: наполнить маленький кувшин (5,3), вылить большой (0,0) или перелить большой в маленький, тогда останется 2 л (2,3). Наполнить полный кувшин или вылить пустой ничего не меняет, поэтому это не ходы.

4. У того, что сейчас было, есть названия.

   Состояние это один снимок: сколько в каждом кувшине. Ход это линия от одного состояния к другому. Все состояния и ходы вместе это пространство состояний. Цель это нужное состояние. Поиск значит найти путь от старта до цели.

5. Проведи самый короткий путь от 0,0 до цели.

   Нажимай на точки, которые отстоят на один ход. Кувшины следуют за тобой. Получится за 6?

   Путь 0,0, 5,0, 2,3, 2,0, 0,2, 5,2, 4,3 использует маленький кувшин, чтобы забирать по 3 л: 5 минус 3 оставляет 2, а если долить до 5 из кувшина на 3 л, в котором уже 2, останется 4.

6. Новые кувшины: 6 л и 4 л. Сколько может в итоге оказаться в кувшине на 6 л?

   Оба объёма чётные, поэтому наполнение, выливание или переливание всегда переносит чётное число литров. Начав с 0 и 0, нечётного количества не получить. На карте состояний просто нет нечётных точек, поэтому никакой поиск их не найдёт.

7. Теперь пусть машина обыщет карту для 5 л и 3 л.

   Нажми «Расширить» и смотри, как она проверяет состояния кольцами.

Следующий урок: В ширину и в глубину · Часть курса: Поиск, игры и планы

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