Gwiazda wieczoru – algorytm A* (A star)

Algorytm UCS był przez nas stosowany ostatnio z dużym powodzeniem. Dlaczego więc mamy z niego rezygnować i szukać czegoś innego? Ponieważ nie jest on zbyt inteligentny. Spójrzmy na trywialną instancję problemu labiryntu.

00000Człowiek od razu zauważy, że wystarczy iść w prawo. A co zobaczy UCS?

00000

Czerwone kropki oznaczają rozwinięte wierzchołki, czyli te które były brane pod uwagę jako potencjalnie prowadzące do celu.

Czy nie można było po prostu iść prosto do celu zamiast marnować czas na szukanie dookoła a nawet wstecz? Poradziliśmy sobie lepiej niż komputer ponieważ intuicyjnie czujemy, że idąc w lewo oddalamy się od celu. Jak teraz przełożyć naszą intuicję na kod?

Heurystyka

Aby komputer wiedział w który kierunek poszukiwań jest dobry, a który zły potrzebujemy pewnej funkcji która będzie szacować odległość stanu od rozwiązania. Taką funkcję nazywamy heurystyką. Idealna heurystyka zwraca wartość będącą dokładnym kosztem przejścia z bieżącego stanu do rozwiązania. Pozwala to na bezbłędną pracę algorytmu, bez rozwijania zbędnych wierzchołków. Oczywiście uzyskanie dokładnej wartości może być skomplikowane i czasochłonne, przez co w praktyce niemożliwe do zastosowania.
Okazuje się że do znalezienia optymalnego rozwiązania wystarczy aby była ona dopuszczalna oraz spójna. Co oznaczają te pojęcia? Intuicyjnie, spójność oznacza, że funkcja nigdy nie zwraca wartości większej niż faktyczny koszt przejścia z danego wierzchołka do wyjścia. Formalnie
\forall_{v \in V} h(v) \le C(v)
gdzie V to zbiór wszystkich wierzchołków (stanów), h to heurystyka, a C to rzeczywisty koszt. Spójność natomiast można kojarzyć z nierównością trójkąta. Spójrzmy na schemat:

consistencyJeżeli zachodzi:
h(v) \le C(v,u) + h(u)
wtedy heurystyka jest spójna. Jak można to interpretować? Poprzedni warunek gwarantował, że „globalnie” nie przeszacujemy kosztu do celu. Spójność gwarantuje że to samo dzieje się lokalnie (dla każdego wierzchołka). Skoro h(v) podał nam pewną wartość oznacza to, że nie istnieje żadna droga o mniejszym koszcie – nie tylko bezpośrednio v->t ale również przez inne wierzchołki np. v->u->t. Dodatkowo spójność implikuje dopuszczalność

Wróćmy do problemu labiryntu (bez monet) i zastanówmy się nad heurystyką. Niezależnie od układu ścian nie da się przejść drogą krótszą niż tą wyznaczoną linią prostą (po prostej też może się nie dać ale jest to OK – warunek spójności jest spełniony). Taka heurystyka prezentuje się następująco (v to wierzchołek dla którego szacujemy koszt, g to wierzchołek docelowy).
h(v, g) = \sqrt{(v_x - g_x)^2 + (g_x - v_x)^2}
Jeśli poruszamy się jedynie w kierunkach NSWE możemy pójść o krok dalej i zastosować metrykę taksówkową.
h(v, g) = |v_x - g_x| + |v_y - g_y|

Algorytm A*

Mamy już sposób oceny potencjału wierzchołka. Jak to wykorzystać? Wystarczy do priorytetu dodać wartość heurystyki, to sprawi że bardziej obiecujące wierzchołki będą rozwijane wcześniej. Taka modyfikacja nosi nazwę algorytmu A*. Co ważne przy spójnej heurystyce nadal mamy gwarancję uzyskania optymalnego rozwiązania. Porównanie do UCS można przedstawić następująco:

astar vs ucs

A* przeszukuje przestrzeń stanów szybciej w kierunku rozwiązania niż w innych kierunkach. Sprawdźmy:

EsF688

so_good

Idealnie…

Implementacja

W związku z powyższym implementacja będzie wymagała jedynie niewielkich zmian.
Na początek funkcja heurystyczna

def heuristics(node, instance):
    node_pos = (node[0], node[1])
    target_pos = (instance.get_target_state()[0], instance.get_target_state()[1])
    return taxi(node_pos, target_pos)


def taxi(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

W obiekcie instance pojawiła się metoda get_target_state() która zwraca stan końcowy.

def astar(instance, h):
    closed = set()  # zbiór zamknięty
    # inicjujemy zbiór otwarty stanem początkowym. Decyzję ustawiamy na null
    # koszt na 0 - nie ma to znaczenia. Rodzicem jest również null (jest to
    # korzeń drzewa
    # fringe dla UCS jest kolejką priorytetową (niższy priorytet powoduje szybsze zdjęcie
    #elementu
    #enqueue - put
    #dequeue - get
    fringe = PriorityQueue()
    #format wierzchołka to:
    #(priorytet,[(stan, decyzja, koszt), rodzic])
    #jest to wymagane przez kolejkę.
    root_node = Node()
    root_node.parent = None
    root_node.cost = 0
    root_node.step = None
    root_node.state = instance.get_start_state()
    fringe.put((0, root_node))
    #znaleziony cel
    target = None

    while True:
        #jeśli zbiór otwarty jest pusty to nie istnieje droga do celu
        if fringe.empty():
            return []
        #pobierz kolejny węzeł z kolejki - ten o najniższym priorytecie
        #ignorujemy koszt pobrany z kolejki, zamiast niego używamy własności cost węzła
        node = fringe.get()[1]
        node_cost = node.cost

        #jeśli jesteśmy w stanie docelowym, ustaw cel i zakończ
        if instance.is_target_state(node.state):
            target = node
            break

        #jeśli węzeł nie był rozwijany
        if node.state not in closed:
            #dodaj go do zbioru zamkniętego (innymi słowy oznacz jako rozwinięty)
            closed.add(node.state)
            #rozwiń go
            children = instance.get_children(node.state)

            #print node.state, children
            #i dla każdego następnika
            for child in children:
                child_state, child_step, child_cost = child
                #dodaj informację o poprzedniku (node jest rodzicem child)
                #jako koszt ustaw sumę następnika i koszt dojścia do rodzica -
                #został on odczytany przy rozpakowywaniu krotki zwróconej przez
                #fringe.get()
                heuristic_cost = h(child_state, instance) #koszt do wyjścia oszacowany przez heurystykę
                vertex = Node()
                vertex.step = child_step
                vertex.cost = child_cost + node_cost
                vertex.parent = node
                vertex.state = child_state
                new_node = (vertex.cost + heuristic_cost, vertex) #priorytetem jest dotychczasowy
                #koszt + wartość heurystyki.
                #i wrzuć do kolejki (zbioru otwartego)
                fringe.put(new_node)

    #lista decyzji prowadzących do rozwiązania
    solution = []
    #zaczynamy od węzła z wynikiem
    i = target
    #dopóki ma rodzica (nie jesteśmy w korzeniu)
    while i.parent is not None:
        #dodaj decyzję która nas tutaj doprowadziła
        solution.append(i.step)
        #przejdź do rodzica
        i = i.parent
    #podążaliśmy od wyjścia do startu przez co trzeba odwrócić kolejność
    solution.reverse()

    return solution

Na koniec zobaczmy na porównanie UCS oraz A* dla kilku przykładowych problemów. Użyto heurystyki jak w powyższym kodzie.

Bez żadnych zmian możemy zastosować A* do problemu ze zbieraniem monet. (Heurystyka pozostała taka samo, dla lepszych efektów należało by w niej uwzględnić monety pozostałe na planszy). Tutaj niestety trudno jest pokazać dokładnie, które stany zostały odwiedzone.

Tak jak UCS, A* można wykorzystać do całkowicie innych problemów. „Wystarczy” opracować dobrą heurystykę.

Następnym razem zmusimy komputer do rozwiązania sudoku.

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s