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 са единствените.

  1. Кой връх избира greedy веднага след S и по кой път стига до G?
  2. Какви са f(A) и f(B) след обработката на S?
  3. Кой път намира A* и каква е цената му?
  4. Допустима ли е евристиката във всички четири върха? Обоснови с най-евтините остатъци.

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

Отговор 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))

Изтегли example.py.

В речника Евристика за търсене · Алчно търсене по евристика · Търсене A*.