135. Информирано търсене — евристика, greedy и A*
Евристиката h оценява оставащата цена. Greedy избира най-малкото h. A* избира най-малкото f = g + h, където g е цената до текущото състояние. Допустимата евристика не надценява най-евтиния остатък. При търсене по пътища с положителни цени допустимата оценка позволява на A* да намери най-евтин път. При реализация със затворено множество и без повторно отваряне на състояния се използва и условието за съгласуваност h(u) ≤ цена(u,v) + h(v) за всяко ребро.
Раздел в разширената разработка.
Самостоятелна задача
Условие
Има насочени преходи S→A (5), S→B (1), A→G (1), B→G (3). Началото е S, целта е G. Евристиката е h(S)=4, h(A)=1, h(B)=3, h(G)=0. В скобите е цената на прехода. Greedy избира най-малкото h. A* избира най-малкото f = g + h, където g е сборът от цените на преходите от S до текущия връх. Търсенето спира, когато целта бъде избрана за обработка. Допустима евристика е тази, която никъде не надценява най-евтината оставаща цена. Пътищата през A и B са единствените.
- Кой връх избира greedy веднага след S и по кой път стига до G?
- Какви са f(A) и f(B) след обработката на S?
- Кой път намира A* и каква е цената му?
- Допустима ли е евристиката във всички четири върха? Обоснови с най-евтините остатъци.
Отговори за самопроверка
Отговор 1
A, защото 1 е по-малко от 3. Пътят е S→A→G с цена 6.
Отговор 2
f(A)=5+1=6, f(B)=1+3=4.
Отговор 3
S→B→G с цена 4.
Отговор 4
Да. Най-евтините остатъци от S, A, B и G са съответно 4, 1, 3 и 0.
Изпълним пример
Python 3. Двата режима използват едни и същи пътища. Стойността за избор е h при алчно търсене и g + h при A*. Извеждат се избраните пътища и реалните им цени.
roads = {
"S": [("A", 4), ("B", 1)],
"A": [("G", 1)],
"B": [("G", 2)]
}
estimate = {"S": 3, "A": 1, "B": 2, "G": 0}
def search(use_cost):
waiting = [(0, "S")]
while waiting:
cost, path = min(waiting, key=lambda item:
estimate[item[1][-1]] + (item[0] if use_cost else 0))
waiting.remove((cost, path))
if path[-1] == "G":
return path, cost
for next_stop, price in roads[path[-1]]:
waiting.append((cost + price, path + next_stop))
print(*search(False))
print(*search(True))
В речника Евристика за търсене · Алчно търсене по евристика · Търсене A*.