132. Пространство на състоянията и задача за път
Формулираме задача за търсене чрез начално състояние, допустими действия, преходи, условие за цел и цена на пътя. Състоянието пази сведенията, нужни за избор на следващо действие.
Раздел в разширената разработка.
Самостоятелна задача
Условие
В игра жетонът заема позиция 0, 1, 2, 3 или 4. Започва на 0. Допустим ход увеличава позицията с 1 или 2, ако остава най-много 4. Целта е да стигнем на 4 с най-малко ходове. Всеки ход струва 1. Записът x → y означава един ход от x към y.
- Кои са състоянията и кое е началното?
- Кои ходове са допустими от позиция 3?
- Дай допустим път до целта с три хода.
- Дай най-евтиния път и обоснови цената му.
Отговори за самопроверка
Отговор 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))
В речника Пространство на състоянията · Задача за търсене на път · Цена на път.