132. Пространство на състоянията и задача за път

Формулираме задача за търсене чрез начално състояние, допустими действия, преходи, условие за цел и цена на пътя. Състоянието пази сведенията, нужни за избор на следващо действие.

Раздел в разширената разработка.

Самостоятелна задача

Условие

В игра жетонът заема позиция 0, 1, 2, 3 или 4. Започва на 0. Допустим ход увеличава позицията с 1 или 2, ако остава най-много 4. Целта е да стигнем на 4 с най-малко ходове. Всеки ход струва 1. Записът x → y означава един ход от x към y.

  1. Кои са състоянията и кое е началното?
  2. Кои ходове са допустими от позиция 3?
  3. Дай допустим път до целта с три хода.
  4. Дай най-евтиния път и обоснови цената му.

Отговори за самопроверка

Отговор 1

0, 1, 2, 3, 4. Началното е 0.

Отговор 2

Само 3 → 4.

Отговор 3

Например 0 → 1 → 2 → 4.

Отговор 4

0 → 2 → 4 струва 2. Един ход стига най-много до 2.

Изпълним пример

Python 3. successors дава допустимите следващи позиции. Извеждаме по един ред за всяко състояние, за да се види какво се случва на границата.

def successors(position):
    return [position + step for step in (1, 2) if position + step <= 3]

for position in range(4):
    print(position, successors(position))

Изтегли example.py.

В речника Пространство на състоянията · Задача за търсене на път · Цена на път.