Skrypt, czy Nie-Skrypt

Ta cz�� koncentruje si� na zadziwiaj�co u�ytecznej matematycznej abstrakcji zwanej grafem. B�dziesz cz�sto u�ywa� wykres�w w sztucznej inteligencji gry. W rzeczywisto�ci ju� je widzia�e�: diagramy b�belkowe przej�cia stanu z cz�ci s� rodzajem wykresu. Grafiki i ich m�odsi bracia, drzewa, s� stale u�ywane przez programist�w AI. Mo�na ich u�ywa� do wielu r�nych rzeczy - od umo�liwienia agentom gry efektywnego podr�owania mi�dzy dwoma punktami, do decydowania, co zbudowa� w grze strategicznej i rozwi�zywania zagadek. Pierwsza cz�� zostanie po�wi�cona wprowadzeniu ci� do r�nych rodzaj�w wykres�w i zwi�zanej z nimi terminologii. Dowiesz si�, czym s� wykresy, jak mo�na ich u�ywa� i jak je efektywnie kodowa�. W pozosta�ej cz�ci rozdzia�u opisano szczeg�owo wiele algorytm�w wyszukiwania dost�pnych w celu wykorzystania pe�nej mocy graf�w.

Wykresy

Podczas opracowywania sztucznej inteligencji do gier jednym z najcz�stszych zastosowa� graf�w jest reprezentowanie sieci �cie�ek, kt�rymi agent mo�e si� porusza� po swoim �rodowisku. Kiedy si� tego nauczy�em, by�em zdezorientowany, poniewa� przez ca�e �ycie zna�em wykres, kt�ry wygl�da jak wykresy, kt�rych nauczy�em si� rysowa� w szkole

Zawsze uwa�a�em, �e wykresy s� przydatne do wizualizacji wzlot�w i upadk�w niekt�rych w��ciwo�ci, takich jak wykresy temperatur pokazane w telewizyjnych prognozach pogody lub danych o sprzeda�y, i tym podobne, wi�c zastanawia�em si�, jak taki wykres m�g�by ewentualnie mo�e by� u�ywany do reprezentowania �cie�ek tn�cych wok� �cian i przeszk�d w �rodowisku gry. Je�li nigdy nie studiowa�e� teorii graf�w, to prawdopodobnie tak my�lisz o grafach. My�l�, �e tak w�a�nie jeste

To ten sam wykres, ale zmieni�em etykietowanie osi, aby reprezentowa� wsp�rz�dne x i y przestrzeni kartezja�skiej, dodaj�c kilka kosmetycznych ozd�b, dzi�ki czemu teraz reprezentuje �cie�k� wij�c� si� w pobli�u rzeki. W rzeczywisto�ci wygl�da na co�, co przeci�tny cz�owiek na ulicy nazwa�by map�. Rzeczywi�cie, ca�y obraz jest map�, ale szereg punkt�w po�rednich i ��cz�ca je �cie�ka s� reprezentowane przez bardzo prosty wykres. Teraz zdaj� sobie spraw�, �e niekt�rzy z was b�d� my�le�, �e to nie jest wielka sprawa, ale wierz�, �e dla wielu ta subtelna zmiana perspektywy mo�e by� objawieniem. To z pewno�ci� by�o dla mnie. W terminologii graficznej punkty drogi nazywane s� w�z�ami (lub czasami wektorami), a �cie�ki ��cz�ce je nazywane s� kraw�dziami (lub czasami �ukami). Rysunek poni�szy pokazuje kilka innych przyk�ad�w wykres�w. Jak wida�, mog� one przyjmowa� szeroki zakres konfiguracji.

W szerszym kontek�cie wykres jest symboliczn� reprezentacj� sieci i chocia� w�z�y i kraw�dzie mog� reprezentowa� relacj� przestrzenn�, tak� jak w omawianym wcze�niej przyk�adzie, nie musi tak by�. Wykresy mog� s�u�y� do reprezentowania wszelkiego rodzaju sieci, od sieci telefonicznych i sieci WWW po obwody elektroniczne i sztuczne sieci neuronowe.

UWAG.A Wykresy mog� by� pod��czone lub niepo��czone. Wykres uwa�a si� za po��czony, gdy mo�liwe jest prze�ledzenie �cie�ki mi�dzy poszczeg�lnymi w�z�ami. Wykresy A, B, D i E na powy�szym rysunku s� przyk�adami po��czonych wykres�w. Wykresy C i F s� przyk�adami niepowi�zanych wykres�w.

Bardziej formalny opis

Wykres G mo�na formalnie zdefiniowa� jako zbi�r w�z��w lub wierzcho�k�w, N, ��cz�cy si� z zestawem kraw�dzi, E. Cz�sto mo�na to znale�� jako:

G = {N, E} (5.1)

Je�li ka�dy w�ze� na wykresie jest oznaczony liczb� ca�kowit� z zakresu od 0 do (N-1), kraw�d� mo�e by� teraz okre�lana przez w�z�y, kt�re ��czy, na przyk�ad 3-5 lub 19-7. wszelkie wykresy maj� wywa�one kraw�dzie - zawieraj� informacje o koszcie przej�cia z jednego w�z�a do drugiego. Na przyk�ad na wykresie pokazanym wcze�niej na rysunku koszt przej�cia kraw�dzi to odleg�o�� mi�dzy dwoma po��czonymi w�z�ami. Na wykresie przedstawiaj�cym drzewo technologiczne gry RTS przypominaj�cej Warcraft kraw�dzie mog� wskazywa� zasoby potrzebne do ulepszenia ka�dej jednostki.

UWAGA. Chocia� wykres mo�e mie� wiele po��cze� z tym samym w�z�em lub nawet po��czenia zap�tlone ��cz�ce w�ze� z samym sob�, funkcje te rzadko s� niezb�dne do sztucznej inteligencji w grze i nie b�d� omawiane na nast�pnych stronach.

Drzewa

Wi�kszo�� programist�w zna struktur� danych drzewa. Drzewa s� szeroko stosowane we wszystkich dyscyplinach programowania. Jednak mo�esz nie zdawa� sobie sprawy, �e drzewa s� podzbiorem wykres�w obejmuj�cych wszystkie wykresy acykliczne (nie zawieraj�ce �cie�ek cyklicznych). Wykres E na rysunku powy�ej jest drzewem i prawdopodobnie jest to kszta�t, kt�ry znasz, ale wykres D jest r�wnie� drzewem. Wykres F to las drzew.

G�sto�� wykresu

Stosunek kraw�dzi do w�z��w wskazuje, czy wykres jest rzadki czy g�sty. Rzadkie wykresy maj� kilka po��cze� na w�ze�, a wykresy g�ste wiele.

pokazuje przyk�ad obu typ�w. Aby zmniejszy� z�o�ono�� i ograniczy� zu�ycie procesora i pami�ci do minimum, powiniene� preferowa� rzadkie wykresy, gdy tylko jest to mo�liwe, na przyk�ad podczas projektowania wykresu do wykorzystania w planowaniu �cie�ki. Wiedza, czy wykres jest g�sty, czy rzadki, jest pomocna przy wyborze odpowiedniej struktury danych do kodowania struktury wykresu, poniewa� implementacja, kt�ra jest wydajna dla g�stego wykresu, prawdopodobnie nie b�dzie wydajna dla tego, kt�ry jest rzadki

Dwugraf

Do tej pory zak�adali�my, �e je�li mo�liwe jest przejazd z w�z�a A do w�z�a B, mo�liwe jest r�wnie� wykonanie czynno�ci odwrotnej. Nie zawsze tak mo�e by�. Czasami mo�e by� konieczne zaimplementowanie wykresu, w kt�rym po��czenia s� kierunkowe. Na przyk�ad, twoja gra mo�e mie� "po�lizg �mierci" umieszczony nad rzek�. Agent powinien by� w stanie przej�� tylko w jedn� stron� - od g�ry do do�u - dlatego musimy znale�� spos�b na reprezentacj� tego rodzaju po��czenia. Alternatywnie mo�e by� mo�liwe podr�owanie mi�dzy dwoma w�z�ami w dowolnym kierunku, ale koszt ka�dego przej�cia mo�e by� inny. Dobrym przyk�adem jest to, je�li chcesz, aby Twoi agenci brali pod uwag� pochy�o�ci terenu. W ko�cu pojazd �atwo i sprawnie i szybko zje�d�a w d�, ale zu�ywa o wiele wi�cej paliwa, aby pojazd porusza� si� pod g�r�, a jego maksymalna pr�dko�� b�dzie znacznie mniejsza. Mo�emy odzwierciedli� te informacje za pomoc� wykresu zwanego digraph lub w skr�cie DAG. Digraf ma kraw�dzie skierowane lub w jedn� stron�. W�z�y, kt�re definiuj� skierowan� kraw�d� s� znane jako para uporz�dkowana i okre�la kierunek kraw�dzi. Na przyk�ad, uporz�dkowana para 16-6 wskazuje, �e mo�liwe jest przej�cie z w�z�a 16 do w�z�a 6, ale nie z w�z�a 6 do 16. W tym przyk�adzie w�ze� 16 jest znany jako w�ze� �r�d�owy, a w�ze� docelowy 6.

Kraw�dzie s� rysowane za pomoc� strza�ek wskazuj�cych ich kierunek. Podczas projektowania struktury danych dla wykres�w cz�sto pomocne jest my�lenie o grafach bezkierunkowych jako o wykrojach z dwiema kraw�dziami ��cz�cymi ka�d� po��czon� par� w�z��w. Jest to wygodne, poniewa� oba typy wykres�w (skierowane i nieukierowane) mog� by� nast�pnie reprezentowane przez t� sam� struktur� danych. Na przyk�ad rzadki, nieukierowany wykres pokazany na rycinie 5.4 mo�e by� reprezentowany przez wykr�j pokazany poni�ej

Zanim przejdziemy do implementacji kodu dla wykresu, rzu�my okiem na niekt�re z rzeczy, do kt�rych mo�esz u�y� wykresu przy opracowywaniu sztucznej inteligencji gry, zaczynaj�c od najpopularniejszego zastosowania: nawigacji lub wyszukiwania �cie�ek.

Wykresy nawigacyjne
Wykres nawigacyjny to abstrakcja wszystkich lokalizacji w �rodowisku gry, kt�re mog� odwiedza� agenci gry, oraz wszystkich po��cze� mi�dzy tymi punktami. W zwi�zku z tym dobrze zaprojektowany nawigator to struktura danych obejmuj�ca wszystkie mo�liwe �cie�ki w �rodowisku gry, dlatego jest bardzo przydatny, poniewa� pomaga agentom gier w podj�ciu decyzji, jak dosta� si� z punktu A do punktu B. Ka�dy w�ze� na wykresie przedstawia zazwyczaj pozycj� kluczowy obszar lub obiekt w �rodowisku, a ka�da kraw�d� reprezentuje po��czenia mi�dzy tymi punktami. Ponadto ka�da kraw�d� b�dzie wi�za�a si� z kosztami, co w najprostszym przypadku reprezentuje odleg�o�� mi�dzy w�z�ami, kt�re ��czy. Ten typ wykresu znany jest matematykom jako wykres euklidesowy. Rysunek poni�ej pokazuje wykres nawigacyjny utworzony dla �rodowiska o ma�ych �cianach i wyr�nia �cie�k� przez ten wykres.

Chcia�bym wyja�ni�, �e agent gry nie ogranicza si� do poruszania si� wzd�u� kraw�dzi wykresu, jakby to by� poci�g jad�cy po szynach. Agent mo�e przej�� do dowolnej niezak��conej pozycji w �rodowisku gry, ale u�ywa wykresu nawigacyjnego do negocjowania swojego �rodowiska - do planowania �cie�ek mi�dzy dwoma lub wi�cej punktami i przechodzenia przez nie. Na przyk�ad, je�li agent umieszczony w punkcie A uzna, �e konieczne jest przej�cie do po�o�enia B, mo�e u�y� nawigatora, aby obliczy� najlepsz� tras� mi�dzy w�z�ami znajduj�cymi si� najbli�ej tych punkt�w. Rysunek powy�szy jest typowy dla wykresu nawigacyjnego utworzonego dla strzelanki FPS. Inne typy gier mog� uzna� inny uk�ad w�z��w za bardziej skuteczny. Na przyk�ad gry typu RTS / RPG cz�sto oparte s� na siatce kafelk�w lub kom�rek, przy czym ka�da p�ytka reprezentuje inny rodzaj terenu, np. Traw�, drog�, b�oto itp. Dlatego wygodnie jest utworzy� wykres za pomoc� �rodka punkty ka�dej p�ytki i przypisywanie koszt�w kraw�dzi na podstawie odleg�o�ci mi�dzy kom�rkami wa�onymi dla typu terenu, po kt�rym przesuwa si� kraw�d�. Takie podej�cie pozwala agentom gry �atwo obliczy� �cie�ki, kt�re omijaj� wod�, wol� podr�owa� po drogach od b�ota i w�drowa� po g�rach. Rysunek pokazuje rodzaj uk�adu kom�rek, kt�rego mo�na si� spodziewa� w RTS / RPG.

Poniewa� niekt�re gry RTS / RPG mog� wykorzystywa� dos�ownie setki tysi�cy kom�rek, wad� tego podej�cia jest to, �e wykresy mog� by� bardzo du�e, kosztowne do przeszukania i zajmuj� du�e ilo�ci pami�ci. Na szcz�cie dla tw�rc�w AI, niekt�rych z tych problem�w mo�na unikn��, stosuj�c techniki, kt�rych nauczysz si� w dalszej cz�ci

WSKAZ�WKA. Je�li tworzysz "ukryte", takie jak gry Thief and Thief 2 firmy Looking Glass Studios / Eidos Interactive, mo�esz u�y� nawigatora, kt�rego kraw�dzie s� wywa�one przez to, ile d�wi�ku posta� przemie�ci wzd�u� kraw�dzi. Kraw�dzie, kt�re mo�na pokonywa� cicho, takie jak te wzd�u� dywanu, mia�yby niskie ci�ary warto�ci, a g�o�ne kraw�dzie wysokie warto�ci. Projektowanie wykres�w w ten spos�b pozwala postaciom w grze znale�� najcichsz� �cie�k� mi�dzy dwoma pokojami.

Wykresy zale�no�ci

Wykresy zale�no�ci s� u�ywane w grach typu zarz�dzanie zasobami w celu opisania zale�no�ci mi�dzy r�nymi budynkami, materia�ami, jednostkami i technologiami dost�pnymi dla gracza. Rysunek pokazuje cz�� wykresu zale�no�ci utworzonego dla takiej gry. Ten rodzaj wykresu u�atwia sprawdzenie, jakie s� wymagania wst�pne do utworzenia ka�dego rodzaju zasobu.

Wykresy zale�no�ci s� nieocenione przy projektowaniu sztucznej inteligencji dla tego rodzaju gatunku, poniewa� AI mo�e ich u�ywa� do decydowania o strategiach, przewidywania przysz�ego statusu przeciwnika i skutecznego przydzielania zasob�w. Oto kilka przyk�ad�w opartych na wykresie pokazanym na rysunku.

1. Je�li AI przygotowuje si� do bitwy i stwierdzi, �e �ucznicy b�d� korzystni, mo�e zbada� wykres zale�no�ci, aby stwierdzi�, �e zanim b�dzie w stanie wyprodukowa� �ucznik�w, musi najpierw upewni� si�, �e ma koszary i technologi� strza�. Wie r�wnie�, �e aby produkowa� strza�y, musi mie� tartak produkuj�cy drewno. Dlatego je�li AI ma ju� tartak, mo�e przeznaczy� zasoby na budow� koszar lub odwrotnie. Je�li sztuczna inteligencja nie ma koszar ani tartaku, mo�e dodatkowo sprawdzi� wykres technologii, aby ustali�, �e prawdopodobnie korzystne jest zbudowanie koszar przed tartakiem. Dlaczego? Poniewa� koszary s� warunkiem wst�pnym dla trzech r�nych rodzaj�w jednostek bojowych, podczas gdy tartak jest warunkiem koniecznym do produkcji drewna. Sztuczna inteligencja stwierdzi�a ju�, �e bitwa jest nieuchronna, wi�c powinna zda� sobie spraw� (oczywi�cie je�li poprawnie j� zaprojektowa�e�), �e powinna jak najszybciej wk�ada� zasoby w tworzenie jednostek bojowych, poniewa�, jak wszyscy wiemy, rycerze i piechota �o�nierze robi� lepszych wojownik�w ni� drewniane deski!

2. Je�li wrogi pieszy �o�nierz nios�cy bro� dotrze na terytorium AI, AI mo�e przejecha� przez wykres do ty�u, aby stwierdzi�, �e:

• Wr�g musia� ju� zbudowa� ku�ni� i tartak.
• Wr�g musia� opracowa� technologi� prochu.
• Wr�g musi produkowa� zasoby drewna i �elaza.

Dalsze badanie wykresu wskaza�oby, �e wr�g prawdopodobnie ma armaty lub je obecnie buduje. Paskudny! AI mo�e wykorzysta� te informacje do wyboru najlepszego planu ataku. Na przyk�ad sztuczna inteligencja wiedzia�aby, �e aby nie dopu�ci� do dotarcia na jej terytorium kolejnych wrog�w z broni�, powinna celowa� w ku�ni� i tartak wroga. Mo�e r�wnie� wywnioskowa�, �e wys�anie zab�jcy w celu uderzenia wroga kowala znacznie os�abi�oby jego wroga i by� mo�e po�wi�ci�by �rodki na stworzenie zab�jcy na ten cel.

3. Cz�sto technologia lub okre�lona jednostka jest kluczem do zwyci�stwa dru�yny. Je�li koszty budowy ka�dego zasobu s� przypisane do kraw�dzi wykresu zale�no�ci, wtedy AI mo�e wykorzysta� te informacje do obliczenia najbardziej wydajnej trasy do wytworzenia tego zasobu

Wykresy stanu

Wykres stanu reprezentuje ka�dy mo�liwy stan, w kt�rym mo�e znajdowa� si� system, oraz przej�cia mi�dzy tymi stanami. Ta kolekcja potencjalnych stan�w systemu jest znana jako przestrze� stan�w. Wykres tego typu mo�na przeszuka�, aby sprawdzi�, czy dany stan jest mo�liwy, lub znale�� najbardziej efektywn� tras� do okre�lonego stanu. Sp�jrzmy na prosty przyk�ad z uk�adank� "Towers of Hanoi"

W tej prostej wersji uk�adanki znajduj� si� trzy ko�ki - A, B i C - i trzy pier�cienie o r�nych rozmiarach, kt�re pasuj� na ko�ki. Pier�cienie zaczynaj� si� ustawia� w porz�dku wielko�ci nad ko�kiem A. Celem uk�adanki jest przesuwanie pier�cieni, a� wszystkie zostan� ustawione na ko�ku C, r�wnie� w kolejno�ci wielko�ci. Jednocze�nie mo�na przenosi� tylko jeden pier�cie�. Pier�cie� mo�na umie�ci� na pustym ko�ku lub na pier�cieniu wi�kszym od niego. Mo�emy przedstawi� przestrze� stanu tej uk�adanki za pomoc� wykresu, na kt�rym ka�dy w�ze� reprezentuje jeden z mo�liwych stan�w, w kt�rych mo�e znajdowa� si� uk�adanka. Kraw�dzie wykresu przedstawiaj� przej�cia mi�dzy stanami: Je�li mo�liwe jest przej�cie bezpo�rednio z jednego stanu do drugiego, b�dzie kraw�d� ��cz�ca oba stany; w przeciwnym razie nie b�dzie po��czenia. Wykres jest tworzony przez utworzenie najpierw w�z�a, kt�ry zawiera stan pocz�tkowy uk�adanki. Jest to znane jako w�ze� g��wny. W�ze� g��wny jest nast�pnie rozwijany przez dodanie do wykresu wszystkich stan�w mo�liwych do uzyskania z tego w�z�a, a nast�pnie ka�dy z tych stan�w jest rozszerzany i tak dalej, a� wszystkie mo�liwe stany i przej�cia zostan� dodane do wykresu. Poprzedni stan ka�dego stanu nazywany jest stanem nadrz�dnym, a nowy stan nazywany jest dzieckiem stanu nadrz�dnego. Rysunek pokazuje ten proces. Strza�ka ��cz�ca dwa stany oznacza, �e jeden stan mo�na osi�gn�� z drugiego, przesuwaj�c jeden z dysk�w. Wykres szybko si� komplikuje, wi�c pomin��em wiele mo�liwych stan�w, aby u�atwi� dostrze�enie jednej ze �cie�ek prowadz�cych do rozwi�zania.

Wykres stanu mo�na �atwo przeszuka�, aby znale�� stan celu. W tym przyk�adzie stanem bramki jest taki, w kt�rym wszystkie elementy s� umieszczone na ko�ku C we w�a�ciwej kolejno�ci. Przeszukuj�c przestrze� stan�w mo�na nie tylko znale�� jedno rozwi�zanie, ale tak�e znale�� ka�de mo�liwe rozwi�zanie lub rozwi�zanie wymagaj�ce najmniejszej liczby ruch�w (lub najwi�kszej liczby ruch�w, je�li tego w�a�nie szukasz). �rednia liczba w�z��w podrz�dnych promieniuj�cych z ka�dego w�z�a nadrz�dnego jest znana jako czynnik rozga��ziaj�cy wykresu. W przypadku niekt�rych problem�w, takich jak omawiany tutaj przyk�ad �amig��wki, wsp�czynnik rozga��zienia jest niski - rz�du od jednej do trzech ga��zi na w�ze� - co umo�liwia przedstawienie za pomoc� wykresu ca�ej przestrzeni stanu w pami�ci komputera. Jednak w wielu domenach wsp�czynnik rozga��zienia jest znacznie wy�szy, a liczba potencjalnych stan�w ogromnie ro�nie wraz ze wzrostem odleg�o�ci od w�z�a g��wnego (g��boko�� wykresu). W tego typu systemach niemo�liwe jest przedstawienie ca�ej przestrzeni stan�w, poniewa� szybko przekroczy mo�liwo�ci pami�ci nawet najbardziej wydajnego komputera. Nawet je�li taki wykres m�g�by zosta� zapisany, wyszukiwanie zajmie jeszcze eony. W rezultacie tego rodzaju wykresy s� tworzone i przeszukiwane poprzez rozwini�cie kilku w�z��w naraz, zwykle (ale nie zawsze) przy u�yciu algorytm�w, kt�re kieruj� wyszukiwanie w kierunku celu.

Implementowanie klasy grafu

Dwie popularne struktury danych u�ywane do reprezentowania wykres�w to macierze przyleg�o�ci i listy przyleg�o�ci. Wykresy macierzy adiakencji wykorzystuj� dwuwymiarow� macierz boolean�w lub liczb zmiennoprzecinkowych do przechowywania informacji o po��czeniu wykresu. Warto�ci logiczne s� u�ywane, je�li nie ma kosztu zwi�zanego z przemierzaniem kraw�dzi, a zmiennoprzecinkowe s� u�ywane, gdy istnieje powi�zany koszt, na przyk�ad w przypadku wykresu nawigacyjnego, w kt�rym ka�da kraw�d� reprezentuje odleg�o�� mi�dzy dwoma w�z�ami. Dok�adne wdro�enie zale�y oczywi�cie od projektanta i jego potrzeb problem. Rycina. pokazuje, jak wygl�da macierz przylegania dla wykre�lnika na rycinie wcze�niej

Ka�de "1" oznacza po��czenie mi�dzy dwoma w�z�ami, a ka�de "0" oznacza brak po��czenia. Po odczytaniu warto�ci bezpo�rednio z macierzy z rysunku 5.12 wiemy, �e nie ma po��czenia od w�z�a 2 do 6, ale istnieje kraw�d� ��cz�ca 4 do 2. Macierze adiacyencji s� intuicyjne, ale dla du�ych rzadkich graf�w ten typ reprezentacji jest nieefektywna, poniewa� wi�kszo�� matrycy jest u�ywana do przechowywania niepotrzebnych warto�ci zerowych. Znacznie lepsza struktura danych dla rzadkich wykres�w (najcz�ciej wyst�puj�cych wykres�w w grze AI) to lista s�siedztwa. Dla ka�dego obecnego w�z�a wykres listy przyleg�o�ci przechowuje po��czon� list� wszystkich s�siednich kraw�dzi. Rysunek pokazuje, jak to dzia�a w poprzednim przyk�adzie.

Listy adiakencji s� skuteczne do przechowywania rzadkich wykres�w, poniewa� nie marnuj� miejsca na przechowywanie zerowych po��cze�. Ilo�� miejsca wymagana do przechowywania wykresu przy u�yciu tego typu struktury danych jest proporcjonalna do N + E (liczba w�z��w + liczba kraw�dzi), podczas gdy dla macierzy s�siedniej jest proporcjonalna do N2 (liczba w�z��w do kwadratu). Poniewa� wi�kszo�� wykres�w, kt�re mo�na napotka� podczas tworzenia gier AI, jest niewielka, lista zgodno�ci b�dzie cz�sto twoj� wybran� struktur� danych. Maj�c to na uwadze, sp�jrzmy na kod �r�d�owy wymagany do zaimplementowania takiego wykresu.

Klasa GraphNode

GraphNode zawiera minimaln� ilo�� informacji wymaganych przez w�ze� do reprezentacji wykresu listy przyleg�o�ci: unikalny numer identyfikacyjny lub indeks. Oto lista deklaracji w�z�a wykresu:

class GraphNode
{
protected:
// ka�dy w�ze� ma indeks. Prawid�owy indeks to> = 0
int m_iIndex;
public:
GraphNode (): m_iIndex (invalid_node_index) {}
GraphNode (int idx): m_iIndex (idx) {}
virtual ~ GraphNode () {}
int Index () const;
void SetIndex (int NewIndex);
};

Poniewa� cz�sto konieczne jest, aby w�ze� zawiera� dodatkowe informacje, GraphNode jest zwykle u�ywany jako klasa bazowa, z kt�rej mo�na uzyska� niestandardowe w�z�y. Na przyk�ad w�z�y wykresu nawigacyjnego musz� przechowywa� informacje przestrzenne, a w�z�y wykresu zale�no�ci musz� zawiera� informacje o reprezentowanych przez nich zasobach. Klasa w�z�a zaprojektowana do u�ycia w grafie nawigacyjnym mo�e wygl�da� mniej wi�cej tak:

template
klasa NavGraphNode: public GraphNode
{
protected:
// pozycja w�z�a
Vector2D m_vPosition;
// cz�sto b�dziesz potrzebowa� w�z�a navgraph, aby zawiera� dodatkowe informacje.
// Na przyk�ad w�ze� mo�e reprezentowa� odbi�r, taki jak zbroja, w kt�rej
// case m_ExtraInfo mo�e by� wyliczon� warto�ci� oznaczaj�c� typ odbioru,
// umo�liwiaj�c w ten spos�b algorytmowi wyszukiwania przeszukanie wykresu dla okre�lonych element�w.
// Id�c o krok dalej, m_ExtraInfo mo�e by� wska�nikiem do wyst�pienia
// typ elementu, z kt�rym w�ze� jest powi�zany. Pozwoli�oby to na algorytm wyszukiwania
// aby sprawdzi� status odbioru podczas wyszukiwania.
extra_info m_ExtraInfo;
public:
/ * POMINI�TY INTERFEJS * /
};

Pami�taj, �e chocia� wymieniona tutaj klasa w�z��w u�ywa wektora 2D do przedstawienia pozycji w�z�a, wykres mo�e istnie� w dowolnej liczbie wymiar�w, kt�re ci si� podobaj�. Je�li tworzysz wykres nawigacyjny dla gry 3D, po prostu u�yj wektor�w 3D. Wszystko b�dzie dzia�a� tak samo.

Klasa GraphEdge

Klasa GraphEdge zawiera podstawowe informacje wymagane do oznaczenia po��czenia mi�dzy dwoma w�z�ami grafowymi. Oto kod:

class GraphEdge
{
protected:
// Kraw�d� ��czy dwa w�z�y. Prawid�owe wska�niki w�z��w s� zawsze dodatnie.
int m_iFrom;
int m_iTo;
// koszt przej�cia kraw�dzi
double m_dCost;
public:
GraphEdge (int from, int to, double cost): m_dCost (cost),
m_iFrom (od),
m_iTo (do)
{}
GraphEdge (int from, int to): m_dCost (1.0),
m_iFrom (od),
m_iTo (do)
{} GraphEdge (): m_dCost (1.0),
m_iFrom (invalid_node_index),
m_iTo (invaid_node_index)
{}

Czasami przydaje si� mo�liwo�� utworzenia GraphEdge z jednym lub obydwoma wska�nikami ustawionymi na "nieprawid�ow�" (ujemn�) warto��. Wyliczona warto�� invaid_node_index w pliku NodeTypeEnumerations.h jest tutaj u�ywana , aby zainicjowa� From i To w domy�lnym konstruktorze.

virtual ~ GraphEdge () {}
int From () const;
void SetFrom (int NewIndex);
int To () const;
void SetTo (int NewIndex);
double Cost () const; void SetCost (double NewCost);
};

Je�li pracujesz na platformie, na kt�rej wykorzystanie pami�ci jest znacznie wi�kszym problemem ni� szybko�� wyszukiwania wykresu, mo�esz uzyska� dobre oszcz�dno�ci na wykresach opartych na kom�rkach (lub wykresach o r�wnej lub wi�kszej g�sto�ci), nie zapisuj�c jawnie kosztu ka�dego kraw�d�. Zamiast tego mo�na zaoszcz�dzi� pami��, pomijaj�c pole kosztu z klasy GraphEdge i obliczy� koszt "w locie" za pomoc� funkcji atrybut�w jego dw�ch s�siednich w�z��w. Na przyk�ad, je�li koszt kraw�dzi jest r�wny odleg�o�ci mi�dzy dwoma w�z�ami, funkcj� b�dzie odleg�o�� euklidesowa. Co� jak:

//cost from A to B
cost = Distance(NodeA.Position, NodeB.Position)

Poniewa� na tym wykresie jest zwykle osiem razy wi�cej kraw�dzi ni� wierzcho�k�w, oszcz�dno�� pami�ci mo�e by� znaczna, gdy zaanga�owana jest du�a liczba w�z��w

Klasa SparseGraph

W�z�y i kraw�dzie wykresu s� zgrupowane razem w klasie SparseGraph. Jest to zaimplementowane jako szablon klasy, dzi�ki czemu ten typ wykresu mo�e wykorzystywa� dowolne odpowiednie typy w�z��w i kraw�dzi. Algorytmy dzia�aj�ce na wykresach powinny mie� szybki dost�p do w�z�a i danych brzegowych. Maj�c to na uwadze, klasa SparseGraph zosta�a zaprojektowana w taki spos�b, aby klucze numeryczne indeksu ka�dego w�z�a bezpo�rednio w wektorze w�z��w grafowych (m_Nodes) i wektorze list kraw�dzi przyleg�o�ci (m_Edges), co daje czas wyszukiwania O (1). Stwarza to jednak problem, gdy w�ze� jest usuwany z wykresu, poniewa� gdyby mia� zosta� r�wnie� usuni�ty z m_Nodes, ca�e indeksowanie dla w�z��w o wy�szym indeksowaniu by�oby uniewa�nione. Dlatego zamiast usuwa� w�ze� z wektora, jego indeks jest ustawiony na wyliczon� warto�� invalid_node_index i wszystkie metody SparseGraph traktuj� t� warto�� tak, jakby nie by�o w�z�a. Oto lista deklaracji SparseGraph.

template
class SparseGraph
{
public:
// mo�liwia �atwy dost�p klienta do typ�w kraw�dzi i w�z��w u�ywanych na wykresie
typedef edge_type EdgeType;
typedef node_type NodeType;
// kilka innych przydatnych typedefs
typedef std::vector NodeVector;
typedef std::list EdgeList;
typedef std::vector EdgeListVector;
private:
// w�z�y, kt�re sk�adaj� si� na ten wykres
NodeVector m_Nodes;
// wektor list kraw�dzi przyleg�o�ci. (ka�dy klucz indeksu w�z�a do
// listy kraw�dzi powi�zanych z tym w�z�em)
EdgeListVector m_Edges;
// czy to jest ukierunkowany wykres?
bool m_bDigraph;
// indeks nast�pnego w�z�a, kt�ry ma zosta� dodany
int m_iNextNodeIndex;
/ * DODATKOWE SZCZEGӣY POMINOWANE * /
public:
//ctor
SparseGraph(bool digraph): m_iNextNodeIndex(0), m_bDigraph(digraph){}
// zwraca w�ze� o podanym indeksie
const NodeType& GetNode(int idx)const;
// wersja non-const
NodeType& GetNode(int idx);
// metoda const uzyskiwania odniesienia do kraw�dzi
const EdgeType& GetEdge(int from, int to)const;
// wersja non const
EdgeType& GetEdge(int from, int to);
// pobiera nast�pny wolny indeks w�z�a
int GetNextFreeNodeIndex()const;
// dodaje w�ze� do wykresu i zwraca jego indeks
int AddNode(NodeType node);
// usuwa w�ze�, ustawiaj�c jego indeks na invalid_node_index
void RemoveNode(int node);
// metody dodawania i usuwania kraw�dzi
void AddEdge(EdgeType edge);
void RemoveEdge(int from, int to);

Zwr�� uwag�, w jaki spos�b klasa ma metody usuwania w�z��w i kraw�dzi. Jest to niezb�dna funkcja, je�li wykres jest dynamiczny i mo�e si� zmienia� w miar� post�pu gry. Na przyk�ad �atwo jest przedstawi� zak��cenie wywo�ane trz�sieniem ziemi, usuwaj�c (a czasem dodaj�c) kraw�dzie z wykresu nawigacyjnego. Alternatywnie, rozgrywka podobna do tej z Command & Conquer mo�e dodawa� i usuwa� kraw�dzie, gdy gracze buduj� lub niszcz� mosty i �ciany.

// zwraca liczb� aktywnych + nieaktywnych w�z��w obecnych na wykresie
int NumNodes () const;
// zwraca liczb� aktywnych w�z��w obecnych na wykresie
int NumActiveNodes () const;
// zwraca liczb� kraw�dzi obecnych na wykresie
int NumEdges () const;
// zwraca true, je�li wykres jest skierowany
bool isDigraph () const;
// zwraca true, je�li wykres nie zawiera �adnych w�z��w
bool isEmpty () const;
// zwraca true, je�li w�ze� z danym indeksem jest obecny na wykresie
bool isPresent (int nd) const;
// metody �adowania i zapisywania wykres�w z otwartego strumienia plik�w lub z
// nazwa pliku
bool Save (const char * FileName) const;
bool Save (std :: ofstream & stream) const;
bool Load (const char * nazwa_pliku);
bool Load (std :: ifstream & stream);
// czy�ci wykres gotowy do wstawienia nowego w�z�a
void Clear ();
// klienci iterator�w mog� uzyskiwa� dost�p do w�z��w i kraw�dzi
class ConstEdgeIterator;
class EdgeIterator;
class NodeIterator;
class ConstNodeIterator;
};

Z informacji w tej sekcji dowiedzia�e� si�, �e wykresy to pot�ne narz�dzie, kt�re masz do dyspozycji. Jednak sama struktura danych wykresu ma niewiele zastosowa�. Du�a cz�� mocy graf�w jest realizowana tylko wtedy, gdy s� one obs�ugiwane przez algorytmy zaprojektowane do ich eksploracji, albo w celu znalezienia okre�lonego w�z�a lub znalezienia �cie�ki mi�dzy w�z�ami. Pozosta�a cz�� jest po�wi�cona jest badaniu kilku z tych algorytm�w.

Algorytmy wyszukiwania wykres�w

Teoria graf�w jest popularnym obszarem bada� matematyk�w i opracowano wiele algorytm�w do wyszukiwania i eksploracji topologii wykresu. Korzystaj�c z algorytm�w wyszukiwania, mo�na mi�dzy innymi:

• Odwied� ka�dy w�ze� na wykresie, skutecznie mapuj�c topologia� wykresu
• Znajd� dowoln� �cie�k� mi�dzy dwoma w�z�ami. Jest to przydatne, je�li chcesz znale�� w�ze�, ale tak naprawd� nie zale�y ci na tym, jak tam dotrze�. Na przyk�ad tego rodzaju wyszukiwania mo�na u�y� do znalezienia jednego (lub wi�cej) rozwi�zania puzzli Wie�e Hanoi.
• Znajd� najlepsz� �cie�k� mi�dzy dwoma w�z�ami. To, co jest "najlepsze", zale�y od problemu. Je�li przeszukiwany wykres jest grafem nawigacyjnym, najlepsz� �cie�k� mo�e by� najkr�tsza �cie�ka mi�dzy dwoma w�z�ami, �cie�ka, kt�ra zabiera agenta mi�dzy dwoma punktami w najszybszym czasie, �cie�ka omijaj�ca lini� wzroku wroga lub najcichsza �cie�ka (? la Thief). Je�li wykres jest wykresem stanu, takim jak uk�adanka z Wie� Hanoi, to najlepsza �cie�ka b�dzie t�, kt�ra dojdzie do rozwi�zania w jak najmniejszej liczbie krok�w

Zanim przejd� do drobiazg�w, chcia�bym wyja�ni�, �e wielu z was na pocz�tku b�dzie mia�o trudno�ci z zrozumieniem niekt�rych z tych algorytm�w. W rzeczywisto�ci uwa�am, �e algorytmy wyszukiwania graf�w powinny zawiera� ostrze�enie zdrowotne. W�a�ciwe by�oby co� takiego:

OSTRZE�ENIE!

Strze� si�! Algorytmy wyszukiwania maj� zdolno�� tworzenia w przeci�tnym ludzkim m�zgu strasznych frustracji i dezorientacji, co prowadzi do b�l�w g�owy, nudno�ci i braku snu. Spontaniczne i nadmierne wycie nie jest niczym niezwyk�ym. Nale�y pami�ta�, �e te objawy s� powszechne na wczesnych etapach krzywej uczenia si� i nie s� generalnie powodem do niepokoju. Zwyk�a us�uga jest zwykle wznawiana w rozs�dnym czasie. (Je�li objawy utrzymuj� si�, trzymaj si� z dala od ruchliwych dr�g, �yletek i za�adowanej broni. Zasi�gnij porady medycznej przy najbli�szej okazji.)

Powa�nie, jednak dla wielu os�b te rzeczy mog� by� trudne do zrozumienia. Z tego powodu po�wi�c� czas na wyja�nienie ka�dego algorytmu. Bardzo wa�ne jest, aby zrozumie� teori� i nie u�ywa� tych technik w spos�b "wycinaj i wklej", poniewa� cz�sto mo�esz chcie� zmodyfikowa� algorytm zgodnie z w�asnymi wymaganiami. Bez zrozumienia, jak dzia�aj� te wyszukiwania, wszelkie modyfikacje b�d� prawie niemo�liwe, a ty b�dziesz drapa� si� po g�owie z frustracj�.

Niedoinformowane wyszukiwania graf�w

Niedoinformowane wyszukiwania graf�w lub �lepe wyszukiwania, jak to czasem bywa znane, przeszukuje wykres bez wzgl�du na zwi�zane z nim koszty kraw�dzi. Mog� jednak rozr�nia� poszczeg�lne w�z�y i kraw�dzie, umo�liwiaj�c im identyfikacj� w�z�a docelowego lub rozpoznanie wcze�niej odwiedzonych w�z��w lub kraw�dzi. Jest to jedyna informacja wymagana do pe�nego zbadania wykresu (do odwiedzenia ka�dego w�z�a) lub znalezienia �cie�ki mi�dzy dwoma w�z�ami.

G��bokie pierwsze wyszukiwanie

Poznaj ma�ego Billy′ego. Billy stoi przy wej�ciu do typowego parku rozrywki: zlepek przeja�d�ek i innych atrakcji oraz �cie�ki wij�ce si� przez park, kt�ry je ��czy. Billy nie ma mapy, ale ch�tnie odkrywa, jakie przeja�d�ki i inn� rozrywk� ma do zaoferowania park. Na szcz�cie Billy wie o teorii graf�w i szybko dostrzega podobie�stwo mi�dzy uk�adem parku rozrywki a wykresem. Widzi, �e ka�d� atrakcj� mo�na przedstawi� za pomoc� w�z�a, a �cie�ki mi�dzy nimi za pomoc� kraw�dzi. Wiedz�c o tym, Billy mo�e zapewni�, �e odwiedzi ka�d� atrakcj� i zejdzie ka�d� �cie�k�, u�ywaj�c algorytmu wyszukiwania zwanego pierwszym wyszukiwaniem g��bokim lub w skr�cie DFS. Pierwsze wyszukiwanie g��bokie jest tak nazwane, poniewa� wyszukuje, przesuwaj�c jak najg��biej na wykresie. Kiedy uderza w �lepy zau�ek, wraca do p�ytszego w�z�a, gdzie mo�e kontynuowa� eksploracj�. Na przyk�adzie parku tematycznego dzia�a ten algorytm:

Od wej�cia do parku (w�ze� �r�d�owy) Billy odnotowuje opis i �cie�ki, kt�re rozci�gaj� si� na zewn�trz (kraw�dzie) na kartce papieru. Nast�pnie wybiera jedn� ze �cie�ek do zej�cia. Nie ma znaczenia, mo�e wybra� jeden losowo, pod warunkiem, �e jest to �cie�ka, kt�rej nie zbada�. Za ka�dym razem, gdy �cie�ka prowadzi Billy′ego do nowej atrakcji, notuje jej nazw� i �cie�ki z ni� zwi�zane. Ilustracje oznaczone od A do D na rycinie przedstawiaj� kilka pierwszych krok�w tego procesu.

Cienkie czarne linie reprezentuj� niezbadane �cie�ki a pod�wietlone linie pokazuj� �cie�ki, kt�re Billy postanowi� zej��. Kiedy osi�ga pozycj� pokazan� w D, Billy zauwa�a, �e ze statku pirackiego nie prowadz� �adne nowe �cie�ki (w mowie graficznej ten w�ze� jest znany jako w�ze� ko�cowy). Dlatego, aby kontynuowa� wyszukiwanie, cofa si� do kina 3D, gdzie istniej� dalsze niezbadane �cie�ki do przej�cia. Patrz rysunek E.

Kiedy dotrze do Lodowego Blastera, s� cztery niezbadane �cie�ki do wypr�bowania. Pierwsze dwie, po kt�rych nawiguje, prowadz� z powrotem do wcze�niej odwiedzonych miejsc - Wej�cia i Funhouse - wi�c ka�d� �cie�k� oznaczy jako zbadan� przed powrotem do Ice Blaster, aby wypr�bowa� inn� tras�. W ko�cu znajduje �cie�k� prowadz�c� do automat�w. Patrz rysunek F, G i H. Ten proces przesuwania si� do przodu przez wykres tak daleko, jak to mo�liwe, zanim nast�pi powr�t do wcze�niej niezbadanych �cie�ek, trwa do momentu zmapowania ca�ego parku rozrywki. Kroki od I do L na rysunku przedstawiaj� kilka kolejnych etap�w procesu. Rycina poni�szy pokazuje gotowy wykres po tym, jak

UWAGA Przy danym w�le �r�d�owym pierwsze wyszukiwanie g��boko�ci mo�e jedynie zagwarantowa�, �e wszystkie w�z�y i kraw�dzie zostan� odwiedzone na po��czonym wykresie. Pami�taj, �e po��czony wykres to taki, na kt�rym mo�na dotrze� do dowolnego w�z�a z dowolnego innego. Je�li przeszukujesz niepowi�zany wykres, taki jak C na rysunku wcze�niej, algorytm nale�y rozwin��, aby zawiera� w�ze� �r�d�owy dla ka�dego pod-wykresu.

Implementacja algorytmu

DFS jest zaimplementowany jako szablon klasy i mo�e by� u�ywany z dowoln� implementacj� grafu (np. G�sty wykres) przy u�yciu tego samego interfejsu, co pokazana wcze�niej klasa SparseGraph. Najpierw przejrzyjmy deklaracj� klasy, a nast�pnie opisz� sam algorytm wyszukiwania.

template
class Graph_SearchDFS
{
private:
// w celu zwi�kszenia czytelno�ci
enum {visited, unvisited, no_parent_assigned};
// utw�rz typy typef dla typ�w kraw�dzi i w�z��w u�ywanych przez wykres
typedef typename graph_type::EdgeType Edge;
typedef typename graph_type::NodeType Node;
private:
// odniesienie do wykresu do przeszukania
const graph_type & m_Graph;
// rejestruje indeksy wszystkich odwiedzanych w�z��w je�li
// wyszukiwanie trwa
std::vector m_Visited;

m_Visited zawiera t� sam� liczb� element�w, co w�z�y na wykresie. Ka�dy element jest pocz�tkowo ustawiony jako niezwiedzony. W miar� post�pu wyszukiwania za ka�dym razem, gdy odwiedzany jest w�ze�, odpowiadaj�cy mu element w m_Visited zostanie ustawiony na odwiedzony.

// to utrzymuje tras� wybran� do celu
std::vector m_Route;

m_Route zawiera r�wnie� t� sam� liczb� element�w, co na w�le na wykresie. Ka�dy element jest pocz�tkowo ustawiony na no_parent_assigned. W miar� przeszukiwania wykresu ten wektor przechowuje tras� do w�z�a docelowego, rejestruj�c elementy nadrz�dne ka�dego w�z�a pod odpowiednim indeksem. Na przyk�ad, je�li �cie�ka do celu pod��a za w�z�ami 3 - 8 - 27, to m_Route [8] b�dzie zawiera� 3, a m_Route b�dzie zawiera� 8.

/ indeksy w�z�a �r�d�owego i docelowego
int m_iSource,
m_iTarget;

Podczas eksploracji wykresu najcz�ciej szukasz okre�lonego celu (lub cel�w). Aby ponownie u�y� analogii do parku rozrywki, wygl�da to tak, jakby� szuka� konkretnej jazdy, na przyk�ad kolejki g�rskiej. Maj�c to na uwadze, algorytmy wyszukiwania zwykle wykorzystuj� warunek zako�czenia, zwykle w postaci indeksu w�z�a docelowego.

//true, je�li �cie�ka do celu zosta�a znaleziona
bool m_bFound;
//ta metoda wykonuje wyszukiwanie w DFS
bool Search();

Ta metoda jest kodem, kt�ry implementuje algorytm pierwszego wyszukiwania g��boko�ci. Za chwil� zanurzymy si� w jej wn�trzno�ci.

Graph_SearchDFS(const graph_type& graph,
int source,
int target = -1 ):
m_Graph(graph),
m_iSource(source),
m_iTarget(target),
m_bFound(false),
m_Visited(m_Graph.NumNodes(), unvisited),
m_Route(m_Graph.NumNodes(), no_parent_assigned)
{
m_bFound = Search();
}
//zwraca warto�� true, je�li w�ze� docelowy zosta� zlokalizowany
bool Found()const{return m_bFound;}
//zwraca wektor indeks�w w�z��w, kt�re zawieraj� najkr�tsz� �cie�k�
//od �r�d�a do celu
std::list GetPathToTarget()const;
};

Algorytm wyszukiwania DFS jest implementowany przy u�yciu wska�niki do kraw�dzi std :: stack const zawieraj�cych wykres, kt�ry wyszukuje. Stos jest struktur� danych ostatnia, pierwsza wysz�a (zwykle w skr�cie LIFO). Stos jest u�ywany w podobny spos�b, jak arkusz papieru, kt�rego nasz przyjaciel Billy u�ywa� do eksploracji parku tematycznego: Kraw�dzie s� popychane na nim w trakcie wyszukiwania, tak jak Billy zapisywa� �cie�ki podczas eksploracji. Rzu� okiem na kod metody wyszukiwania, a nast�pnie przedstawi� ci przyk�ad, aby upewni� si�, �e rozumiesz, jak dzia�a jego magia.

template
bool Graph_SearchDFS::Search()
{
//utw�rz standardowy stos wska�nik�w do kraw�dzi
std::stack stack;
// stw�rz atrap� i umie�� na stosie
Edge Dummy(m_iSource, m_iSource, 0);
stack.push(&Dummy);
// gdy na stosie s� kraw�dzie, szukaj dalej
while (!stack.empty())
{
//z�ap nast�pn� kraw�d�
const Edge* Next = stack.top();
//usu� kraw�d� ze stosu
stack.pop();
//zanotuj element nadrz�dny w�z�a, na kt�ry wskazuje ta kraw�d�
m_Route[Next->To] = Next->From();
//i oznacz jako odwiedzone
m_Visited[Next->To()] = visited;
//je�li cel zosta� znaleziony, metoda mo�e zwr�ci� sukces
if (Next->To() == m_iTarget)
{
return true;
}
// popchnij kraw�dzie prowadz�ce od w�z�a, na kt�ry wskazuje ta kraw�d�
// stos (pod warunkiem, �e kraw�d� nie wskazuje wcze�niej
// odwiedzony w�ze�)
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, Next->To());
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
if (m_Visited[pE->To()] == unvisited)
{
stack.push(pE);
}
}
}//podczas
// braku �cie�ki do celu> return false;
}

Aby pom�c Ci zrozumie�, przeanalizujmy prosty przyk�ad. U�ywaj�c niekierowanego wykresu pokazany na poni�szym rysunku, powiedzmy, �e chcemy wyszuka� w�ze� 3 (w�ze� docelowy), rozpoczynaj�c wyszukiwanie od w�z�a 5 (w�ze� �r�d�owy).

Wyszukiwanie rozpoczyna si� od utworzenia sztucznej kraw�dzi - prowadz�cej od w�z�a �r�d�owego z powrotem do w�z�a �r�d�owego - i umieszczenia go na stosie.

Pod�wietlenie wskazuje, �e kraw�d� znajduje si� na stosie. Wyszukiwanie odbywa si� po wprowadzeniu p�tli while. Podczas gdy s� jeszcze niezbadane kraw�dzie stosu, algorytm iteruje nast�puj�ce kroki. Komentarze w nawiasach opisuj� sytuacj� dla pierwszej iteracji w p�tli.

1. Usu� najwy�sz� kraw�d� ze stosu. (Atrapa kraw�dzi [5-5].)
2. Zanotuj element nadrz�dny w�z�a docelowego kraw�dzi, wstawiaj�c indeks elementu nadrz�dnego do wektora m_Routes, w elemencie, do kt�rego odwo�uje si� indeks w�z�a docelowego. (Poniewa� kraw�d� fikcyjna jest u�ywana do uruchomienia algorytmu, rodzicem w�z�a 5 jest r�wnie� w�ze� 5. Dlatego m_Routes [5] jest ustawiony na 5.)
3. Zaznacz w�ze� docelowy kraw�dzi jako odwiedzony, przypisuj�c odwiedzone wyliczenie do odpowiedniego indeksu w wektorze m_Visited

(m_Visited [5] = visited).
4. Test na zako�czenie. Je�li w�ze� docelowy kraw�dzi jest w�z�em docelowym, wyszukiwanie mo�e zwr�ci� sukces. (5 nie jest w�z�em docelowym, wi�c wyszukiwanie jest kontynuowane).
5. Je�li w�ze� docelowy kraw�dzi nie jest celem, to pod warunkiem, �e w�ze�, na kt�ry wskazuje bie��ca kraw�d�, nie zosta� jeszcze odwiedzony, wszystkie s�siednie kraw�dzie zostan� wypchni�te na stos. (Kraw�dzie [5-2], [5-4] i [5-6] s� wpychane w stos.)

Rysunek poni�szy pokazuje stan gry algorytmu po jednej iteracji p�tli while. Szary kolor w�z�a �r�d�owego wskazuje, �e zosta� on oznaczony jako odwiedzony.

W tym momencie algorytm rozga��zia si� z powrotem na pocz�tek p�tli while, zsuwa nast�pn� kraw�d� ze szczytu stosu (kraw�d� [5-2]), zaznacza w�ze� docelowy jako odwiedzony (w�ze� 2) i notuje elementu nadrz�dnego w�z�a docelowego (w�ze� 5 jest elementem nadrz�dnym w�z�a 2). Nast�pnie algorytm bierze pod uwag�, kt�re kraw�dzie powinny zosta� zepchni�te na stos. W�ze� 2 (do kt�rego kraw�dzi [5-2] wskazuje) ma dwie s�siednie kraw�dzie: [2-1] i [2-5]. W�ze� 5 zosta� oznaczony jako odwiedzony, wi�c kraw�d� [2-5] nie zostaje dodana do stosu. Poniewa� w�ze� 1 nie zosta� odwiedzony, prowadz�ca do niego kraw�d� [2-1] jest wypychana na stos. Zobacz rysunek 5.20. Gruba czarna linia z [5-2] wskazuje, �e konkretna kraw�d� nie b�dzie dalej rozpatrywana.

Po raz kolejny algorytm rozga��zia si� z powrotem na pocz�tek p�tli while i zrzuca nast�pn� kraw�d� ze stosu (kraw�d� [2 -1]), zaznacza w�ze� docelowy jako odwiedzony (w�ze� 1) i zapisuje informacje o jego rodzicu (w�le 2 jest rodzicem w�z�a 1). W�ze� 1 ma kraw�dzie prowadz�ce do w�z�a 3 i w�z�a 2. W�ze� 2 zosta� ju� odwiedzony, wi�c tylko kraw�d� [1-3] jest wypychana na stos.

Tym razem, gdy algorytm wyskakuje ze stosu nast�pn� kraw�dzi� [1-3], po zwyk�ej procedurze zaznaczania w�z�a docelowego i odnotowywania elementu nadrz�dnego, algorytm stwierdza, �e zlokalizowa� cel, w kt�rym to momencie algorytm ko�czy dzia�anie. Na tym etapie status jest pokazany na rysunku

Podczas wyszukiwania �cie�ka do w�z�a docelowego jest przechowywana w wektorze m_Route (przedstawionym na poprzednich rysunkach tabel� u�ywan� do przechowywania rodzic�w ka�dego w�z�a). Metoda GetPathToTarget wyodr�bnia te informacje i zwraca je jako wektor liczb ca�kowitych reprezentuj�cych indeksy w�z��w, kt�rych agent musi przestrzega�, aby przej�� od �r�d�a do celu. Oto jak wygl�da kod �r�d�owy:

template
std::list Graph_SearchDFS::GetPathToTarget()const
{
std::list path;
// po prostu zwr�� pust� �cie�k�, je�li nie znaleziono �cie�ki do celu lub je�li
// nie okre�lono celu
if (!m_bFound || m_iTarget<0) return path;
int nd = m_iTarget;
path.push_back(nd);
while (nd != m_iSource)
{
nd = m_Route[nd];
path.push_back(nd);
}
return path;
}

To bardzo prosta metoda. Zaczyna si� od przetestowania, aby zobaczy�, jaki jest element nadrz�dny w�z�a docelowego, a nast�pnie element nadrz�dny tego w�z�a i tak dalej, a� do osi�gni�cia w�z�a �r�d�owego. W przyk�adzie, kt�ry pod��a�e� na kilku ostatnich stronach, �cie�ka, kt�r� zwraca ta metoda, to 5 - 2 - 1 - 3.

UWAGA W celu zapewnienia szybko�ci i wydajno�ci implementacje algorytm�w wyszukiwania opisanych w tym rozdziale s� zaprojektowane do dzia�ania na wykresach utworzonych przed wyszukiwaniem. Jednak w przypadku niekt�rych problem�w nie b�dzie mo�na tego zrobi�, poniewa� oczekiwany rozmiar wykresu jest albo zbyt du�y, aby mo�na go by�o zapisa� w pami�ci, albo dlatego, �e trzeba oszcz�dza� pami��, tworz�c tylko te w�z�y i kraw�dzie, kt�re s� niezb�dne do wyszukiwania. Na przyk�ad, je�li chcesz przeszuka� przestrze� stanu gry, takiej jak szachy, nie mo�na zbudowa� wykresu stanu przed wyszukiwaniem ze wzgl�du na ogromn� liczb� mo�liwych stan�w. Zamiast tego w�z�y i kraw�dzie musz� by� tworzone w miar� wyszukiwania.

DFS w akcji

Aby przekaza� u�yteczne informacje wizualne, stworzy�em program demonstracyjny, kt�ry pokazuje r�ne wyszukiwania wykres�w na wykresie nawigacyjnym uk�adu siatki. Ten typ uk�adu w�z��w jest powszechnie spotykany w grach opartych na kafelkach, w kt�rych w�ze� jest umieszczony na �rodku ka�dej p�ytki, a kraw�dzie ��cz� si� z najbli�szymi o�mioma s�siadami. Linie pionowe i poziome reprezentuj� granice kafelk�w, kropki s� w�z�ami wykresu, a cienkie linie wychodz�ce z w�z��w s� kraw�dziami ��cz�cymi. Niestety zrzut ekranu jest drukowany w skali szaro�ci, wi�c mo�e nie by� �atwo zobaczy� wszystko wyra�nie. Je�li jeste� blisko komputera, polecam uruchomi� plik wykonywalny PathFinder.exe i nacisn�� klawisz "G", aby wy�wietli� wykres.

UWAGA. Chocia� w prawdziwym �wiecie po��czenia diagonalne w demonstracji PathFinder s� d�u�sze ni� po��czenia pionowe i poziome, pierwsze wyszukiwanie g��boko�ci nie ma wiedzy na temat �adnego zwi�zanego z tym kosztu kraw�dzi i dlatego traktuje wszystkie kraw�dzie jako r�wne.

W wersji demo u�y�em uk�adu w�z��w opartego na siatce, poniewa� u�atwia tworzenie eksperymentalnych wykres�w poprzez blokowanie kafelk�w w celu reprezentowania przeszk�d lub zr�nicowanego terenu. Nie oznacza to jednak, �e Twoja gra musi korzysta� z wykresu opartego na siatce. Podkre�lam ten punkt, poniewa� cz�sto widz�, �e nowicjusze maj� trudno�ci ze zrozumieniem, w jaki spos�b wykres mo�e mie� dowolny kszta�t inny ni� siatka. M�wi� na przyk�ad: "Wiem, jak dzia�a algorytm wyszukiwania XYZ dla opartych na kafelkach gier RTS, ale czy mo�na go u�y� w moim FPS?" Cz�sto spotykam si� z tego rodzaju pytaniami i przypuszczam, �e dzieje si� tak, poniewa� wi�kszo�� prezentacji, samouczk�w i artyku��w na temat wyszukiwania �cie�ek pokazuje przyk�ady przy u�yciu uk�adu w�z�a oparty na siatce (z powod�w ju� wymienionych) i my�l�, �e ludzie zak�adaj�, �e tak w�a�nie musi by�. Prosz� … B�agam, nie pope�niaj tego samego b��du! Wykresy mog� mie� dowolny kszta�t (i dowoln� liczb� wymiar�w). W ka�dym razie wr��my do DFS. Zrzut ekranu pokazuje prost� map�, kt�r� utworzy�em, blokuj�c niekt�re kafelki jako przeszkody.

Poniewa� jest wydrukowany w skali szaro�ci, sprawi�em, �e w�z�y �r�d�owy i docelowy s� lepiej widoczne, zaznaczaj�c je odpowiednio kwadratem i krzy�em. Liczby w prawym dolnym rogu pokazuj� liczb� w�z��w i kraw�dzi na podstawowym wykresie

Ulepszenia systemu plik�w DFS

Niekt�re wykresy mog� by� bardzo g��bokie, a DFS mo�na �atwo op�ni�, przechodz�c zbyt daleko z�� cie�k�. W najgorszym scenariuszu system plik�w DFS mo�e nie by� w stanie wyprowadzi� si� z niew�a�ciwego wyboru na pocz�tku wyszukiwania, powoduj�c trwa�e zablokowanie. Jako przyk�ad za��my, �e chcesz znale�� rozwi�zanie losowo pomieszanego Kostki Rubika. Ca�a przestrze� stanu dla tego problemu jest ogromna i zabrania generowania pe�nego wykresu stanu przed jakimkolwiek wyszukiwaniem, dlatego w�z�y s� tworzone w locie, poniewa� ka�dy stan jest rozwijany, zaczynaj�c od w�z�a g��wnego. W pewnym momencie wyszukiwania algorytm DFS mo�e wybra� kraw�d� prowadz�c� do pod grafu przestrzeni stanu, kt�ry nie zawiera stanu rozwi�zania, ale jest zbyt du�y, aby mo�na go by�o w pe�ni rozwin��, bior�c pod uwag� dost�pn� moc obliczeniow�. Powoduje to, �e rozwi�zanie nigdy nie jest zwracane przez DFS, a komputer skutecznie zawiesi�. Na szcz�cie mo�na temu zapobiec, ograniczaj�c liczb� g��boko�ci wyszukiwania algorytmu DFS przed rozpocz�ciem cofania. Nazywa si� to wyszukiwaniem g��boko�ci. Korzystaj�c z wyszukiwania z ograniczon� g��boko�ci�, pod warunkiem, �e g��boko�� jest t�, kt�r� algorytm mo�e przeszukiwa�, bior�c pod uwag� dost�pn� moc obliczeniow�, DFS zawsze zwr�ci rozwi�zanie, je�li takie istnieje na tej g��boko�ci. Jednak wyszukiwanie z ograniczon� g��boko�ci� ma powa�n� wad�. Sk�d wiesz, jaki limit ustawi� dla maksymalnej g��boko�ci wyszukiwania? W przypadku wi�kszo�ci problematycznych domen nie mo�na oceni�, jaki powinien by� ten limit. Korzystaj�c z Kostki Rubika jako przyk�adu, rozwi�zaniem mo�e by� trzy kroki do przodu lub pi�tna�cie. Je�li maksymalna g��boko�� wyszukiwania jest ustawiona na dziesi��, mo�e, ale nie musi znale�� rozwi�zania. Je�li jest ustawiony zbyt wysoko, liczba mo�liwych stan�w mo�e spowodowa� zawieszenie wyszukiwania. Na szcz�cie istnieje spos�b na obej�cie tego problemu: iteracyjne pog��bianie DFS. Iteracyjne wyszukiwanie pog��bienia polega na u�yciu DFS do przeszukiwania wykresu z limitem g��boko�ci r�wnym jeden, nast�pnie g��boko�� druga, potem trzy itd., A� do zako�czenia wyszukiwania. Chocia� na pierwszy rzut oka mo�e si� to wydawa� marnotrawstwem zasob�w, poniewa� w�z�y na p�ytszych g��boko�ciach s� przeszukiwane wiele razy, w rzeczywisto�ci wi�kszo�� w�z��w zawsze znajduje si� na granicy poszukiwa�. Jest to szczeg�lnie prawdziwe w przypadku przeszukiwania wykres�w o wysokim wsp�czynniku rozga��zienia. Bior�c pod uwag� wsp�czynnik rozga��zienia wynosz�cy osiem, podobnie jak wykres na demie PathFinder, liczba w�z��w na skraju jest pokazana w tabeli

Wyobra�am sobie, �e niekt�rzy z was mog� my�le� co� w stylu "Ale je�li podczas normalnego wyszukiwania DFS g��boko�� n zawiesz� komputer, to na pewno, gdy iteracyjne pog��bianie DFS osi�gnie t� sam� g��boko��, zawiesi tak�e komputer!" Odpowied� brzmi: tak, je�li IDDFS mo�e wej�� tak g��boko, pojawi� si� problemy, ale sekretem stosowania iteracyjnego pog��biania jest narzucenie granicy, zwykle definiowanej jako limit czasowy. Po up�ywie czasu przeznaczonego na wyszukiwanie algorytm ko�czy si� bez wzgl�du na osi�gni�ty poziom. Nast�pstwem tego metodycznego podej�cia jest to, �e bior�c pod uwag� wystarczaj�c� ilo�� czasu i prawid�owy cel, iteracyjne pog��bianie DFS nie tylko znajdzie cel, ale znajdzie cel w jak najmniejszej liczbie krok�w.

Linia na poni�szym zrzucie ekranu ilustruje �cie�k�, kt�r� podj�� DFS w poszukiwaniu celu. Jak wida�, meandruje wok� prawie ca�ego obszaru mapy, zanim natknie si� na w�ze� docelowy, wyra�nie pokazuj�c, �e chocia� DFS znajduje cel, nie gwarantuje znalezienia najlepszej trasy do celu.

Nale�y r�wnie� zauwa�y� w tym przyk�adzie, �e DFS nie zbada� �adnych kraw�dzi poza �cie�k� do w�z�a docelowego. Gdy w�ze� docelowy mo�na osi�gn�� wieloma �cie�kami, jest to wsp�lna cecha systemu plik�w DFS, co czyni go szybkim algorytmem do zastosowania, gdy d�ugo�� cie�ki jest nieistotna (tj. Przy przeszukiwaniu przestrzeni stan�w w celu sprawdzenia, czy istnieje konkretny stan w przeciwie�stwie do okre�lenie najszybszej trasy do tego stanu).

Szeroko�� Pierwszego Wyszukiwania

Chocia� zwyk�y system plik�w DFS gwarantuje znalezienie w�z�a docelowego na po��czonym wykresie, nie gwarantuje znalezienia najlepszej �cie�ki do tego w�z�a - �cie�ki zawieraj�cej najmniej kraw�dzi. W poprzednim przyk�adzie DFS da�o �cie�k� obejmuj�c� trzy kraw�dzie, mimo �e najlepsza �cie�ka obejmuje dwie: 5-4-3. Algorytm BFS wysuwa si� z w�z�a �r�d�owego i bada ka�dy z w�z��w, do kt�rych prowadz� jego kraw�dzie, przed rozwini�ciem z tych w�z��w i sprawdzanie wszystkich kraw�dzi, z kt�rymi si� ��cz� itd. Mo�esz my�le� o wyszukiwaniu jako eksploracji wszystkich w�z��w, kt�re s� jedn� kraw�dzi� od w�z�a �r�d�owego, nast�pnie wszystkie w�z�y dwie kraw�dzie dalej, a nast�pnie trzy kraw�dzie i tak dalej, a� do znalezienia w�z�a docelowego. Dlatego te�, gdy tylko cel zostanie zlokalizowany, �cie�ka do niego prowadz�ca ma gwarancj� jak najmniejszej liczby kraw�dzi. (Mog� istnie� inne �cie�ki o r�wnej d�ugo�ci, ale nie b�dzie kr�tszej �cie�ki).

Implementacja algorytmu

Algorytm dla BFS jest prawie dok�adnie taki sam, jak dla DFS, z tym wyj�tkiem, �e u�ywa stosu kolejki pierwsze wej�cie, pierwsze wyj�cie (FIFO) zamiast stosu. W zwi�zku z tym kraw�dzie czasu s� pobierane z kolejki w tej samej kolejno�ci, w jakiej s� umieszczane w kolejce. Sp�jrz na kod �r�d�owy metody wyszukiwania BFS.

template
bool Graph_SearchBFS< graph_type>::Search()
{
// stw�rz standardow� kolejk� kraw�dzi wska�nika
std::queue Q;
// utw�rz atrap� i umie�� w kolejce
const Edge Dummy(m_iSource, m_iSource, 0);
Q.push(&Dummy);
// zaznacz w�ze� �r�d�owy jako odwiedzony
m_Visited[m_iSource] = visited;
// gdy w kolejce s� kraw�dzie, szukaj dalej
while (!Q.empty())
{
// z�ap nast�pn� kraw�d�
const Edge* Next = Q.front();
Q.pop();
// zaznacz element nadrz�dny tego w�z�a
m_Route[Next->To()] = Next->From();
// wyj�cie, je�li cel zosta� znaleziony
if (Next->To() == m_iTarget)
{
return true;
}
// pchnij kraw�dzie prowadz�ce od w�z�a na ko�cu tej kraw�dzi
// do kolejki
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, Next->To());
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();

pE=ConstEdgeItr.next())
{
// je�li w�ze� jeszcze nie by� odwiedzany, mo�emy go przes�a� na
// kraw�d� do kolejki
if (m_Visited[pE->To()] == unvisited)
{
Q.push(pE);
// w�ze� jest tutaj oznaczony jako odwiedzony, ZANIM zostanie sprawdzony, poniewa�
// zapewnia, �e w kolejce b�dzie zawsze umieszczonych maksymalnie N kraw�dzi,
// zamiast kraw�dzi E.
m_Visited[pE->To()] = visited;
}
}
}
// brak �cie�ki do celu
return false;
}

Aby wyja�ni� ci algorytm, przejd�my do tego samego przyk�adu, co poprzednio. Rysunek poni�szy od�wie�y twoj� pami��.

BFS zaczyna si� jak DFS. Najpierw tworzona jest sztuczna kraw�d� [5-5] i wpychana do kolejki. Nast�pnie w�ze� �r�d�owy jest oznaczony jako odwiedzony.

Nast�pnie algorytm odnotowuje rodzica 5. Tak jak poprzednio, poniewa� pierwsz� kraw�dzi�, kt�r� nale�y wzi�� pod uwag�, jest kraw�d� fikcyjna, w�ze� 5 jest ustawiony jako macierzysty. Ta kraw�d� jest nast�pnie usuwana z przodu kolejki i dodawane s� wszystkie s�siednie kraw�dzie w�z�a 5 (te skierowane do niezapowiedzianych w�z��w).

Do tej pory wszystko wygl�da�o bardzo podobnie do DFS, ale tutaj algorytm zaczyna si� r�ni�. Nast�pnie kraw�d� [5-6] jest usuwana z kolejki. Zauwa�ono, �e w�ze� 5 jest rodzicem w�z�a 6. Poniewa� obie s�siednie kraw�dzie w�z�a 6 wskazuj� na wcze�niej odwiedzane w�z�y, nie s� dodawane do kolejki.

Dalej w kolejce jest kraw�d� [5-4]. Zauwa�ono, �e w�ze� 5 jest rodzicem w�z�a 4. W�ze� 4 ma trzy s�siednie kraw�dzie, ale tylko kraw�d� [4-3] wskazuje na nieoznaczony w�ze�, wi�c jest to jedyny umieszczony w kolejce.

Dalej jest kraw�d� [5-2]. Zauwa�ono, �e w�ze� 5 jest rodzicem w�z�a 2, a kraw�d� [2-1] jest umieszczona w kolejce.

Kraw�d� [4-3] jest nast�pna. W�ze� 4 jest uwa�any za element nadrz�dny w�z�a 3. Poniewa� w�ze� 3 jest r�wnie� w�z�em docelowym, w tym momencie algorytm wychodzi.

U�ywaj�c wektora m_Routes do przej�cia przez rodzic�w z w�z�a docelowego do �r�d�a, otrzymujemy �cie�k� 3-4-5. Jest to �cie�ka mi�dzy dwoma zawieraj�cymi najmniej kraw�dzi… najlepsza �cie�ka.

WSKAZ�WKA. Mo�esz przyspieszy� BFS (i wiele innych algorytm�w wyszukiwania wykres�w), uruchamiaj�c jednocze�nie dwa wyszukiwania, jedno rozpocz�te w w�le �r�d�owym, a drugie w w�le docelowym i zatrzymuj�c wyszukiwanie, gdy si� spotkaj�. Nazywa si� to wyszukiwaniem dwukierunkowym.

BFS w akcji

Uruchommy ponownie program PathFinder, aby zobaczy�, jak BFS dzia�a w prawdziwym �wiecie. Przede wszystkim my�l�, �e przyda�by ci si� prosty przyk�ad pokazany na zrzucie ekranu 5.4. (Je�li korzystasz z programu PathFinder, za�aduj plik no_obstacles_source_target_close.map i kliknij przycisk BF na pasku narz�dzi.)

W tym przypadku nie ma �adnych przeszk�d. W�ze� �r�d�owy jest umieszczony blisko w�z�a docelowego, a tylko kilka innych w�z��w (kafelk�w) oddziela je. Ponownie gruba linia pokazuje �cie�k� znalezion� przez algorytm BFS. Cienkie linie reprezentuj� wszystkie kraw�dzie, kt�re algorytm odwiedzi� w drodze do celu. To wyra�nie pokazuje, jak wentylatory BFS wychodz� z w�z�a �r�d�owego, a� do znalezienia w�z�a docelowego. Odwiedzane kraw�dzie tworz� kwadratowy kszta�t, poniewa� BFS, podobnie jak DFS, traktuje wszystkie kraw�dzie tak, jakby by�y r�wnej d�ugo�ci. �cie�ka skr�ca w lewo, a nast�pnie w prawo zamiast z tego samego powodu bezpo�rednio w kierunku w�z�a docelowego. Oba wykonuj� t� sam� liczb� krok�w, ale kszta�t �cie�ki jest ca�kowicie zale�ny od kolejno�ci, w kt�rej eksplorowane s� kraw�dzie ka�dego w�z�a. Zrzut ekranu 5.5 pokazuje dzia�anie BFS na tej samej mapie, kt�r� widzieli�my wcze�niej. Poprawa d�ugo�ci �cie�ki jest wyra�na, chocia� nale�y si� tego spodziewa�, poniewa� zwyk�y system plik�w DFS nie nadaje si� do wyszukiwania najkr�tszych �cie�ek. Jeszcze raz zwr�� uwag�, jak ka�da kraw�d� znajduje si� na tej samej g��boko�ci z dala od w�z�a �r�d�owego, poniewa� cel zosta� odwiedzony.

Niestety, poniewa� BFS jest tak systematyczny w swojej eksploracji, mo�e okaza� si� niewygodny w u�yciu na czymkolwiek innym ni� ma�e przestrzenie wyszukiwania. Je�li oznaczymy wsp�czynnik rozga��zienia jako b, a liczb� kraw�dzi, na kt�rej w�ze� docelowy jest oddalony od �r�d�a jako d (g��boko��), w�wczas liczb� zbadanych w�z��w podaje r�wnanie

Je�li badany wykres jest bardzo du�y i ma wysoki wsp�czynnik rozga��zienia, BFS zaprzepa�ci du�o pami�ci i b�dzie s�abo dzia�a�. Co gorsza, je�li przestrze� stanu ma tak wysoki wsp�czynnik rozga��zienia, �e uniemo�liwia utworzenie pe�nego wykresu przed wyszukiwaniem, wymagaj�c od BFS rozszerzenia w�z��w podczas eksploracji, wyszukiwanie mo�e potrwa� dos�ownie lata. W swojej ksi��ce Artificial Intelligence: A Modern Approach Russell i Norvig podaj� przyk�ad uk�adanki o wsp�czynniku rozga��zienia r�wnym 10; zak�adaj�c, �e rozwini�cie ka�dego w�z�a zajmuje jedn� milisekund�, BFS zajmie 3500 lat, aby osi�gn�� g��boko�� 14! Komputery sta�y si� znacznie szybszymi bestiami od czasu wydania pierwszego wydania tej ksi��ki, ale mimo to nadal by�by� starszym cz�owiekiem w ilo�ci czasu, jak� BFS zajmuje do tej g��boko�ci.

Wyszukiwania oparte na kosztach

W przypadku wielu domen problemowych powi�zany wykres b�dzie kosztowa� (czasami okre�lany jako ci�ar) zwi�zany z przechodzeniem przez kraw�d�. Na przyk�ad wykresy nawigacyjne zwykle maj� kraw�dzie o koszcie proporcjonalnym do odleg�o�ci mi�dzy po��czonymi w�z�ami. Aby znale�� najkr�tsze �cie�ki na wykresie, nale�y wzi�� pod uwag� te koszty. Po prostu nie wystarczy - tak jak poprzednio z BFS - znale�� cie�k� zawieraj�c� najmniejsz� liczb� kraw�dzi, poniewa� przy powi�zanym koszcie podr�owanie w d� wielu kr�tszych kraw�dzi mo�e by� znacznie ta�sze ni� dw�ch d�ugich.

Chocia� mo�na u�y� BFS lub DFS do wyczerpuj�cego wyszukiwania przez wszystkie trasy do w�z�a docelowego, sumuj�c koszty ka�dej �cie�ki, a nast�pnie wybieraj�c �cie�k� o najni�szych kosztach, jest to oczywi�cie bardzo nieefektywne rozwi�zanie. Na szcz�cie mamy do dyspozycji znacznie lepsze metody.

Edge Relaxation

Algorytmy wyszukiwania om�wione w pozosta�ej cz�ci oparte s� na technice zwanej relaksacj� kraw�dzi. W trakcie dzia�ania algorytm zbiera informacje o najlepszej znalezionej do tej pory �cie�ce (BPSF) od w�z�a �r�d�owego do dowolnego innego w�z�a w drodze do celu. Informacje te s� aktualizowane w miar� sprawdzania nowych kraw�dzi. Je�li nowo zbadana kraw�d� wnioskuje, �e �cie�ka do w�z�a mo�e zosta� skr�cona poprzez u�ycie jej zamiast istniej�cej najlepszej �cie�ki, w�wczas ta kraw�d� jest dodawana i �cie�ka jest odpowiednio aktualizowana. Ten proces relaksacji, podobnie jak w przypadku wszystkich operacji graficznych, jest znacznie �atwiejszy do zrozumienia, obserwuj�c schemat. Sp�jrz na rysunek

Na wykresie pokazanym w A najlepsza �cie�ka od 1 do 4 przez 3 nie jest poprawiona przez zbadanie kraw�dzi [5-4]. Dlatego relaks nie jest konieczny. Jednak w przypadku wykresu B kraw�d� [5-4] mo�e zosta� wykorzystana do stworzenia kr�tszej �cie�ki do 4; w rezultacie BPSF musi zosta� odpowiednio zaktualizowany poprzez zmian� elementu nadrz�dnego w�z�a 4 z 3 na 5 (podaj�c �cie�k� 1 - 2 - 5 - 4). Proces ten nazywa si� rozlu�nieniem kraw�dzi, poniewa� na�laduje spos�b, w jaki kawa�ek spr�ysty rozci�gni�ty wzd�u� kraw�dzi BPSF rozlu�ni�by si� (sta�by si� mniej napi�ty), gdy zostanie znaleziona kraw�d�, kt�ra u�atwia kr�tsz� �cie�k�. Ka�dy algorytm utrzymuje zmienn� std :: wektor liczb zmiennoprzecinkowych (indeksowanych wed�ug w�z��w) reprezentuj�cych najlepszy ca�kowity koszt dla ka�dego w�z�a znaleziony do tej pory przez algorytm. Bior�c pod uwag� og�lny przypadek pokazany na rysunku 5.32, pseudokod do rozlu�nienia �cie�ki wygl�da�by mniej wi�cej tak:

if (TotalCostToThisNode [t]> TotalCostToThisNode [n] + EdgeCost (n-to-t))
{
TotalCostToThisNode [t] = TotalCostToThisNode [n] + EdgeCost (n-to-t));
Parent (t) = n;
}

Drzewa najkr�tszej �cie�ki

Bior�c pod uwag� wykres, G i w�ze� �r�d�owy, drzewo najkr�tszej �cie�ki (SPT) jest poddrzewa G, kt�re reprezentuje najkr�tsz� �cie�k� od dowolnego w�z�a na SPT do w�z�a �r�d�owego. Ponownie, zdj�cie jest warte tysi�ca s��w, wi�c sp�jrz na Rysunek 5.33. Pokazuje SPT z korzeniem ustawionym w w�le 1.

Poni�sze algorytmy znajduj� najkr�tsze �cie�ki na wykresach wa�onych przez "wyhodowanie" najkr�tszego drzewa �cie�ek na zewn�trz od w�z�a �r�d�owego.

Algorytm Dijkstry

Profesor Edsger Wybe Dijkstra wni�s� do informatyki wiele cennych wk�ad�w, ale jednym z najbardziej znanych jest jego algorytm znajdowania najkr�tszych �cie�ek na wykresach wa�onych. Algorytm Dijkstry buduje najkr�tsze drzewo �cie�ek po jednej kraw�dzi, najpierw dodaj�c w�ze� �r�d�owy do SPT, a nast�pnie dodaj�c kraw�d�, kt�ra daje najkr�tsz� �cie�k� od �r�d�a do w�z�a, kt�ry nie jest jeszcze w SPT. W wyniku tego procesu SPT zawiera najkr�tsz� �cie�k� od ka�dego w�z�a na wykresie do w�z�a �r�d�owego. Je�li algorytm zostanie dostarczony z w�z�em docelowym, proces zostanie zako�czony, gdy tylko zostanie znaleziony. W momencie zako�czenia algorytmu wygenerowany SPT b�dzie zawiera� najkr�tsz� �cie�k� do w�z�a �r�d�owego od w�z�a docelowego i od ka�dego w�z�a odwiedzonego podczas wyszukiwania.

UWAGA HISTORYCZNA, Dijkstra jest r�wnie� znany z tego, �e zaprojektowa�a i zakodowa� kompilator Algol 60 oraz �arliwie pot�pia u�ycie instrukcji goto w programowaniu. Lubi� te� jego powiedzenie, �e "pytanie, czy komputery mog� my�le�, jest jak pytanie, czy �odzie podwodne potrafi� p�ywa�". Niestety Dijkstra zmar� w 2002 roku na raka. Przejd�my przez przyk�ad z wykorzystaniem tego samego wykresu, kt�ry widzia�e� na powy�szym rysunku, ale w tym przypadku w�z�em �r�d�owym b�dzie w�ze� 5. Najpierw w�ze� 5 jest dodawany do SPT, a kraw�dzie, kt�re go opuszczaj�, s� umieszczane na granicy wyszukiwania.

Algorytm nast�pnie sprawdza docelowe w�z�y kraw�dzi na granicy - 6 i 2 - i dodaje ten najbli�szy �r�d�u (w�ze� 2 w odleg�o�ci 1.9) do SPT. Nast�pnie wszelkie kraw�dzie opuszczaj�ce w�ze� 2 s� dodawane do granicy.

Algorytm ponownie sprawdza docelowe w�z�y kraw�dzi na granicy. Koszt dotarcia do w�z�a 3 ze �r�d�a wynosi 5,0, a koszt dotarcia do w�z�a 6 to 3,0. W�ze� 6 jest zatem nast�pnym w�z�em, kt�ry zostanie dodany do SPT, a wszystkie kraw�dzie, kt�re go opuszcz�, zostan� dodane do granicy.

Proces powtarza si� jeszcze raz. Poniewa� koszt w�z�a 4 jest mniejszy ni� koszt w�z�a 3, jest on dodawany do SPT. Tym razem jednak jedyna kraw�d� z w�z�a 4 prowadzi do w�z�a 3 - w�z�a, kt�ry jest ju� w�z�em docelowym kraw�dzi na granicy. Tutaj zaczyna si� relaks kraw�dzi. Analizuj�c obie mo�liwe �cie�ki do 3, algorytm widzi, �e �cie�ka 5 - 2 - 3 ma koszt 5,0, a �cie�ka 5 - 6 - 4 - 3 wy�szy koszt 7,8. Dlatego kraw�d� [2-3] pozostaje na SPT, a kraw�d� [4-3] zostaje usuni�ta z dalszych rozwa�a�.

Wreszcie w�ze� 3 jest dodawany do SPT. Zobacz rysunek 5.38. Zwr�� uwag�, �e kraw�d� [3-5] nie zosta�a dodana do granicy. Wynika to z faktu, �e w�ze� 5 jest ju� w SPT i nie wymaga dalszego rozpatrywania. Dodatkowo zauwa�, �e w�ze� 1 nie zosta� dodany do SPT. Poniewa� istniej� tylko kraw�dzie prowadz�ce od w�z�a 1, jest on skutecznie izolowany od innych w�z��w na wykresie.

Implementowanie algorytmu Dijkstry

Wdro�enie algorytmu najkr�tszej �cie�ki Dijkstry mo�e by� pocz�tkowo bardzo zrozumia�e i przyznaj�, �e nie mog�em si� doczeka� napisania tej cz�ci, poniewa� uwa�am, �e nie b�dzie to �atwiejsze do wyja�nienia! My�l�, �e oboje musimy wzi�� g��boki oddech, zanim przejdziemy dalej. To jest o wiele lepsze. Dobra, zaczn� od pokazania deklaracji klasy. Komentarze w kodzie zawieraj� wyja�nienia ka�dej ze zmiennych sk�adowych, z kt�rych wi�kszo�� powinna brzmie� znajomo.

template
class Graph_SearchDijkstra
{
private:
// utw�rz typy typef dla typ�w w�z��w i kraw�dzi u�ywanych przez wykres
typedef typename graph_type::EdgeType Edge;
typedef typename graph_type::NodeType Node;
private:
const graph_type & m_Graph;
// ten wektor zawiera kraw�dzie, kt�re sk�adaj� si� na najkr�tsze drzewo �cie�ek -
// ukierunkowane poddrzewo wykresu, kt�re zawiera najlepsze �cie�ki
// ka�dy w�ze� SPT do w�z�a �r�d�owego.
std::vector m_ShortestPathTree;
// jest to indeksowane wed�ug indeksu w�z��w i zawiera ca�kowity koszt najlepszych
// �cie�ka znaleziona do danego w�z�a. Na przyk�ad m_CostToThisNode [5]
// utrzyma ca�kowity koszt wszystkich kraw�dzi, kt�re tworz� najlepsz� �cie�k�
// do w�z�a 5 znalezionego do tej pory w wyszukiwaniu (je�li w�ze� 5 jest obecny i ma
// odwiedzono oczywi�cie).
std::vector m_CostToThisNode;
// jest to indeksowany (wed�ug w�z��w) wektor "macierzystych" kraw�dzi prowadz�cych do w�z��w
// pod��czony do SPT, ale jeszcze go nie dodano.
std::vector m_SearchFrontier;
int m_iSource;
int m_iTarget;
void Search();
public:
Graph_SearchDijkstra(const graph_type& graph,
int source,
int target = -1):m_Graph(graph),
m_ShortestPathTree(graph.NumNodes()),
m_SearchFrontier(graph.NumNodes()),
m_CostToThisNode(graph.NumNodes()),
m_iSource(source),
m_iTarget(target)
{
Search();
}
// zwraca wektor kraw�dzi definiuj�cych SPT. Je�li podano cel
// w konstruktorze, b�dzie to SPT zawieraj�cy wszystkie w�z�y
// sprawdzane przed znalezieniem celu, w przeciwnym razie b�dzie on zawiera� wszystkie w�z�y
// na wykresie.
std::vector GetAllPaths()const;
// zwraca wektor indeks�w w�z��w obejmuj�cych najkr�tsz� �cie�k� // od �r�d�a do celu. Oblicza �cie�k�, pracuj�c // wstecz przez SPT z w�z�a docelowego std::list GetPathToTarget()const;
//zwraca ca�kowity koszt do celu
double GetCostToTarget()const;
};

Ten algorytm wyszukiwania jest implementowany przy u�yciu indeksowanej kolejki priorytetowej. Kolejka priorytetowa, w skr�cie PQ, to kolejka, kt�ra porz�dkuje elementy wed�ug priorytetu (wtedy nie ma niespodzianek). Ten typ struktury danych mo�na wykorzysta� do przechowywania docelowych w�z��w kraw�dzi na granicy wyszukiwania, w kolejno�ci rosn�cej odleg�o�ci (kosztu) od w�z�a �r�d�owego. Ta metoda gwarantuje, �e w�ze� z przodu PQ b�dzie w�z�em, kt�ry nie jest jeszcze w SPT, kt�ry jest najbli�ej w�z�a �r�d�owego. Czy do tej pory mam sens? Je�li nie, prosz� o znies�awienie mnie przed ponownym przeczytaniem tego akapitu. PQ musi by� w stanie utrzyma� przechowywane w nim elementy w uporz�dkowanej kolejno�ci. Oznacza to, �e ka�dy w�ze� wykresu musi mie� dodatkow� zmienn� sk�adow�, aby przechowywa� koszty skumulowane w tym w�le, aby operatorzy "lub" mogli zosta� przeci��eni, aby zapewni� prawid�owe zachowanie. Chocia� u�ycie dodatkowej zmiennej sk�adowej jest z pewno�ci� poprawnym rozwi�zaniem, wola�bym nie zmienia� istniej�cego w�z�a grafu, a poza tym mo�e to by� problematyczne, gdy uruchomionych jest wiele wyszukiwa� jednocze�nie, poniewa� ka�de wyszukiwanie b�dzie wykorzystywa� ten sam rekord danych . Mo�na temu zaradzi�, tworz�c kopie w�z��w, ale w�wczas cenna pami�� i szybko�� zostaj� utracone. Alternatyw� jest u�ycie indeksowanej kolejki priorytetowej (w skr�cie iPQ). Ten typ PQ indeksuje si� do wektora kluczy. W tym przyk�adzie klucze to skumulowane koszty dla ka�dego w�z�a przechowywane w wektorze m_CostToThisNode. W�ze� jest dodawany do kolejki przez wstawienie jego indeksu. Podobnie, gdy w�ze� jest pobierany z iPQ, zwracany jest jego indeks, a nie sam w�ze� (lub wska�nik do w�z�a). Tego indeksu mo�na nast�pnie u�y� do uzyskania dost�pu do w�z�a i jego danych za po�rednictwem m_Graph :: GetNode. Czas pokaza� ci kod �r�d�owy. Upewnij si�, �e nie spiesz si� i rozumiesz ka�d� lini� tego algorytmu; na d�u�sz� met� przyniesie ci dywidendy. Napisa�em obszerne komentarze w �r�dle, aby pom�c ci zrozumie�, ale je�li jeste� zwyk�ym �miertelnikiem, w�tpi�, aby same komentarze wystarczy�y, by "klikn��" przy pierwszym czytaniu. (Je�li po kilku odczytach nadal masz problemy z algorytmem, zdecydowanie zalecamy przejrzenie kodu na kartce papieru na prostym przyk�adzie).

template
void Graph_SearchDijkstra::Search()
{
// utw�rz indeksowan� kolejk� priorytetow�, kt�ra b�dzie sortowana od najmniejszej do najwi�kszej
//(od przodu do ty�u). Zauwa�, �e maksymalna liczba element�w iPQ
// mo�e zawiera� jest NumNodes (). Wynika to z faktu, �e �aden w�ze� nie mo�e by� reprezentowany
// w kolejce wi�cej ni� jeden raz.
IndexedPriorityQLow pq(m_CostToThisNode, m_Graph.NumNodes());
// umie�� w�ze� �r�d�owy w kolejce
pq.insert(m_iSource);
// gdy kolejka nie jest pusta
while(!pq.empty())
{
// pobierz w�ze� o najni�szym koszcie z kolejki. Nie zapomnij o warto�ci zwracanej
// jest * indeksem w�z�a *, a nie samym w�z�em. Ten w�ze� nie jest jeszcze w�z�em
// w SPT, kt�ry jest najbli�ej w�z�a �r�d�owego
int NextClosestNode = pq.Pop();
// przenie� t� kraw�d� z granicy wyszukiwania do drzewa najkr�tszej �cie�ki
m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
// je�li cel zosta� znaleziony, wyjd�
if (NextClosestNode == m_iTarget) return;
// teraz, aby rozlu�ni� kraw�dzie. Dla ka�dej kraw�dzi pod��czonej do nast�pnego najbli�szego w�z�a
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
// ca�kowity koszt dla w�z�a, na kt�ry wskazuje ta kraw�d�, to koszt dla
// aktualny w�ze� plus koszt po��czenia kraw�dzi.
double NewCost = m_CostToThisNode[NextClosestNode] + pE->Cost();
// je�li ta kraw�d� nigdy nie by�a na granicy, zanotuj koszt
// aby dotrze� do w�z�a, na kt�ry wskazuje, a nast�pnie dodaj kraw�d� do granicy
// i w�ze� docelowy do PQ.
if (m_SearchFrontier[pE->To()] == 0)
{
m_CostToThisNode[pE->To()] = NewCost;
pq.insert(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
// else przetestuj, czy koszt dotarcia do w�z�a docelowego za po�rednictwem
// aktualny w�ze� jest ta�szy ni� najta�szy dotychczas znaleziony koszt. Gdyby
// ta �cie�ka jest ta�sza, przypisujemy nowy koszt do miejsca docelowego
// w�ze�, zaktualizuj jego wpis w PQ, aby odzwierciedli� zmian�, i dodaj
// kraw�d� do granicy
else if ( (NewCost < m_CostToThisNode[pE->To()]) &&
(m_ShortestPathTree[pE->To()] == 0) )
{
m_CostToThisNode[pE->To()] = NewCost;
// poniewa� koszt jest mniejszy ni� poprzednio, PQ musi by�
// uciek� si� do tego.pq.ChangePriority(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
}
}
}

WSKAZ�WKA. Implementacja indeksowanej kolejki priorytetowej wykorzystuje stert� dwukierunkow� do przechowywania element�w. W przypadku rzadkich wykres�w, je�li ka�da zbadana kraw�d� powoduje popraw� koszt�w (wymaganie, aby IndexedPriorityQLow :: ChangePriority ny� wywo�any), algorytm podaje najgorszy czas dzia�ania Elog₂N, chocia� w praktyce czas dzia�ania b�dzie znacznie kr�tszy.

Dalsze ulepszenia pr�dko�ci mo�na uzyska�, stosuj�c stert� d-way, gdzie d jest funkcj� g�sto�ci wykresu. Tym razem najgorszym czasem dzia�ania b�dzie Elog_dN. Gdy wszystko jest ju� powiedziane i zrobione, algorytm najkr�tszej �cie�ki Dijkstry jest �adny dobry wykonawca i gwarantuje znalezienie najkr�tszej �cie�ki mi�dzy dwoma w�z�ami, je�li taki istnieje.

Algorytm Dijkstry w dzia�aniu

Uruchommy ponownie program PathFinder i sprawd�my, jak dzia�a algorytm Dijkstry na przyk�adach, kt�re widzieli�my wcze�niej. Zrzut ekranu ilustruje algorytm dzia�aj�cy na prosty problem

Wynik jest podobny do szeroko�ci pierwszego wyszukiwania, chocia� teraz drzewo zawieraj�ce badane kraw�dzie ma okr�g�y kszta�t. Wynika to z faktu, �e algorytm Dijkstry dzia�a z rzeczywistymi kosztami kraw�dzi, dlatego tym razem kraw�dzie uko�ne kosztuj� wi�cej, ni� poziomy lub pionowy. Maj�c to na uwadze, mo�esz zobaczy�, jak algorytm szuka� podobnej odleg�o�ci we wszystkich kierunkach przed osi�gni�ciem celu. Zrzut ekranu pokazuje algorytm Dijkstry dzia�aj�cy na bardziej z�o�onej mapie.

Podobnie jak BFS, algorytm Dijkstry analizuje bardzo du�o kraw�dzi. Czy nie by�oby wspaniale, gdyby algorytm m�g� otrzymywa� wskaz�wki w miar� przesuwania wyszukiwania we w�a�ciwym kierunku? Na szcz�cie dla nas jest to mo�liwe. Panie i panowie! Prosz�, z��cie oklaski i powitajcie A *!

Dijkstra z niespodziank�: A*

Algorytm Dijkstry szuka, minimalizuj�c dotychczasowy koszt �cie�ki. Mo�na go znacznie poprawi�, bior�c pod uwag�, umieszczaj�c w�z�y na granicy, szacowany koszt do celu z ka�dego rozwa�anego w�z�a. Oszacowanie to jest zwykle okre�lane jako heurystyczne, a nazwa nadana algorytmowi wykorzystuj�cemu t� metod� heurystycznie kierowanego wyszukiwania to A * (wymawiana ay-star). I to jest naprawd� dobre! Je�li heurystyka stosowana przez algorytm okre�la doln� granic� rzeczywistego kosztu (nie docenia kosztu) z dowolnego w�z�a do celu, w�wczas A* gwarantuje optymalne �cie�ki. W przypadku wykres�w zawieraj�cych informacje przestrzenne, takich jak wykresy nawigacyjne, mo�na u�y� kilku funkcji heurystycznych, z kt�rych najprostsz� jest odleg�o�� w linii prostej mi�dzy danymi w�z�ami. Jest to czasami okre�lane jako odleg�o�� euklidesowa. A* przebiega prawie identycznie jak algorytm wyszukiwania Dijkstry. Jedyna r�nica polega na obliczeniu koszt�w w�z��w na granicy wyszukiwania. Skorygowany koszt F dla w�z�a umieszczonego w kolejce priorytetowej (granicy wyszukiwania) oblicza si� jako:

F = G + H (5.3)

gdzie G jest ��cznym kosztem dotarcia do w�z�a, a H jest heurystycznym oszacowaniem odleg�o�ci do celu. W przypadku kraw�dzi E, kt�ra w�a�nie zesz�a z granicy i zosta�a dodana do SPT, pseudokod do obliczenia kosztu do w�z�a docelowego wygl�da nast�puj�co:

Koszt = Koszt skumulowany (E.From) + E.Koszt + KosztTo (docelowy)

Wykorzystuj�c w ten spos�b heurystyk�, zmodyfikowane koszty kieruj� wyszukiwanie w kierunku w�z�a docelowego zamiast promieniowa� r�wno na zewn�trz we wszystkich kierunkach. Powoduje to konieczno�� zbadania mniejszej liczby kraw�dzi, co przyspiesza wyszukiwanie i jest podstawow� r�nic� mi�dzy algorytmem A * i algorytmem Dijkstry.

UWAGA. Je�li ustawisz koszt heurystyczny na zero w A *, wynikowe wyszukiwanie zachowa si� dok�adnie tak samo jak algorytm Dijkstry. Rzu�my okiem na to, jak A * dzia�a na wykresach problem�w u�ywanych w programie PathFinder

A* w akcji

Zrzut ekranu pokazuje wynik dzia�ania A* na prostym przyk�adzie przyk�adowym �r�d�o-cel. Jak wida�, nie uwzgl�dniono �adnych obcych kraw�dzi, a �cie�ka prowadzi bezpo�rednio do celu. Zastosowan� funkcj� heurystyczn� jest odleg�o�� w linii prostej mi�dzy dwoma w�z�ami.

Zrzut ekranu jest r�wnie imponuj�cy. Zauwa�, jak ma�o kraw�dzi algorytm A * musia� wzi�� pod uwag� przed znalezieniem celu. W rezultacie czas potrzebny na wyszukiwanie jest znacznie kr�tszy ni� w przypadku innych wyszukiwa� (mimo �e do obliczenia kosztu heurystycznego wymagany jest z�y pierwiastek kwadratowy).

UWAGA. Wykazano, �e A* jest optymalnie wydajny. Innymi s�owy, �aden inny algorytm wyszukiwania nie rozszerzy mniejszej liczby w�z��w w poszukiwaniu �cie�ki o najni�szych kosztach mi�dzy �r�d�em a celem.

Wdro�enie A*

Klasa A* jest bardzo podobna do Graph_SearchDijkstra. Implementacja wyszukiwania wymaga utrzymania dw�ch standardowych wektor�w koszt�w: jeden dla kosztu F dla ka�dego w�z�a, kt�ry jest indeksowany przez kolejk� priorytetow�, i jeden dla kosztu G dla ka�dego w�z�a. Ponadto podczas tworzenia instancji tej klasy nale�y okre�li� jako parametr szablonu heurystyk�, kt�ra ma zosta� u�yta. Ta konstrukcja u�atwia stosowanie niestandardowej heurystyki z klas�, podobnie jak heurystyka na odleg�o�� na Manhattanie wspomniana pod koniec tego rozdzia�u. Oto deklaracja klasowa, kt�r� mo�esz przeczyta�:

template
class Graph_SearchAStar
{
private:
// utw�rz typedef dla typu kraw�dzi u�ywanego przez wykres
typedef typename graph_type::EdgeType Edge;
private:
const graph_type& m_Graph;
// indeksowane wed�ug w�z�a. Zawiera "rzeczywisty" skumulowany koszt dla tego w�z�a
std::vector m_GCosts;
// indeksowane wed�ug w�z�a. Zawiera koszt dodania m_GCosts [n] do
// heurystycznego kosztu od n do w�z�a docelowego. To jest wektor
// iPQ indeksuje do.
std::vector m_FCosts;
std::vector m_ShortestPathTree;
std::vector m_SearchFrontier;
int m_iSource;
int m_iTarget

// algorytm wyszukiwania A*
void Search();
public:
Graph_SearchAStar(graph_type& graph,
int source,
int target):m_Graph(graph),
m_ShortestPathTree(graph.NumNodes()),
m_SearchFrontier(graph.NumNodes()),
m_GCosts(graph.NumNodes(), 0.0),
m_FCosts(graph.NumNodes(), 0.0),
m_iSource(source),
m_iTarget(target)
{
Search();
}
// zwraca wektor kraw�dzi zbadanych przez algorytm
std::vector GetSPT()const;
// zwraca wektor indeks�w w�z��w, kt�re zawieraj� najkr�tsz� �cie�k�
// od �r�d�a do celu
std::list GetPathToTarget()const;
/ zwraca ca�kowity koszt do celu
double GetCostToTarget()const;
};

Strategie heurystyczne do u�ytku z t� klas� musz� zapewnia� statyczn� metod� obliczania z nast�puj�cym podpisem:

//oblicz koszt heurystyczny od w�z�a nd1 do w�z�a nd2 static double Calculate(const graph_type& G, int nd1, int nd2); Poniewa� wykres u�ywany przez demo PathFinder przedstawia informacje przestrzenne, koszt heurystyczny jest obliczany jako odleg�o�� w linii prostej (znana r�wnie� jako odleg�o�� euklidesowa) do w�z�a docelowego z ka�dego rozwa�anego w�z�a. Poni�szy kod pokazuje, w jaki spos�b taka heurystyka jest implementowana jako klasa, kt�rej mo�na u�y� jako parametru szablonu dla Graph_SearchAStar.

class Heuristic_Euclid
{
public:
Heuristic_Euclid(){}
// obliczy� odleg�o�� w linii prostej od w�z�a nd1 do w�z�a nd2
template
static double Calculate(const graph_type& G, int nd1, int nd2)
{
return Vec2DDistance(G.GetNode(nd1).Position, G.GetNode(nd2).Position);
}
}

Typ heurystyczny jest przekazywany jako parametr szablonu podczas tworzenia instancji klasy wyszukiwania A*. Oto jak program demonstracyjny PathFinder tworzy instancj� wyszukiwania A * przy u�yciu heurystyki euklidesowej:

//utw�rz kilka czcionek typedef, aby kod wygodnie znajdowa� si� na stronie
typedef SparseGraph NavGraph;
typedef Graph_SearchAStar AStarSearch; //utw�rz kilka czcionek typedef, aby kod wygodnie znajdowa� si� na stronie
AStarSearch AStar(*m_pGraph, m_iSourceCell, m_iTargetCell);

Implementacja metody wyszukiwania A* jest prawie identyczna jak w przypadku algorytmu najkr�tszej �cie�ki Dijkstry. Jedynym wyj�tkiem jest to, �e koszt dotarcia do okre�lonego w�z�a przed umieszczeniem go na granicy jest teraz obliczany jako G + H (zamiast tylko G). Warto�� H okre�la si�, wywo�uj�c metod� statyczn� heurystycznej klasy strategii.

template
void Graph_SearchAStar::Search()
{
// utw�rz indeksowan� kolejk� priorytetow� w�z��w. Kolejka da pierwsze�stwo
// do w�z��w o niskich kosztach F. (F = G + H)
IndexedPriorityQLow pq(m_FCosts, m_Graph.NumNodes());
// umie�� w�ze� �r�d�owy w kolejce
pq.insert(m_iSource);
// gdy kolejka nie jest pusta
while(!pq.empty())
{
// pobierz w�ze� o najni�szym koszcie z kolejki
int NextClosestNode = pq.Pop();
// przenie� ten w�ze� z granicy do drzewa opinaj�cego
m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
// je�li cel zosta� znaleziony, wyjd�
if (NextClosestNode == m_iTarget) return;
// teraz, aby przetestowa� wszystkie kraw�dzie do��czone do tego w�z�a
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
// oblicz koszt heurystyczny od tego w�z�a do celu (H)
double HCost = heuristic::Calculate(m_Graph, m_iTarget, pE->To());
// obliczy� "rzeczywisty" koszt dla tego w�z�a ze �r�d�a (G)
double GCost = m_GCosts[NextClosestNode] + pE->Cost();
// je�li w�ze� nie zosta� dodany do granicy, dodaj go i zaktualizuj
// koszty G i F.
if (m_SearchFrontier[pE->To()] == NULL)
{
m_FCosts[pE->T()] = GCost + HCost;
m_GCosts[pE->To()] = GCost;
pq.insert(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
// je�li ten w�ze� znajduje si� ju� na granicy, ale koszt dotarcia tutaj
// droga jest ta�sza ni� wcze�niej znaleziona, zaktualizuj koszty w�z�a
// i odpowiednio granica
else if ((GCost < m_GCosts[pE->To()]) &&
(m_ShortestPathTree[pE->To()]==NULL))
{
m_FCosts[pE->To()] = GCost + HCost;
m_GCosts[pE->To()] = GCost;
pq.ChangePriority(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
}
}
}

WSKAZ�WKA. Je�li pracujesz ze �cis�ymi wymaganiami dotycz�cymi pami�ci, mo�esz ograniczy� ilo�� pami�ci u�ywanej przez A * lub wyszukiwanie Dijkstry, ograniczaj�c liczb� w�z��w umieszczonych w kolejce priorytetowej. Innymi s�owy, tylko n najlepszych w�z��w jest przechowywanych w kolejce. To sta�o si� znane jako wyszukiwanie wi�zki.

Heurystyka na dystansie na Manhattanie

Widzia�e�, jak mo�na u�y� klasy algorytmu wyszukiwania A* w heurystyce euklidesowej (odleg�o�� w linii prostej). Inn� funkcj� heurystyczn� popularn� w�r�d programist�w gier, kt�re maj� tabele graficzne z topologi� podobn� do siatki, takich jak gry wojenne oparte na kafelkach, jest odleg�o�� Manhattanu mi�dzy dwoma w�z�ami: suma przesuni�cia w kafelkach w pionie i poziomie. Na przyk�ad odleg�o�� Manhattanu mi�dzy w�z�ami na rysunku wynosi 10 (6 + 4).

Odleg�o�� Manhattanu daje wzrost pr�dko�ci w stosunku do heurystyki euklidesowej, poniewa� do oblicze� nie jest wymagany pierwiastek kwadratowy

Podsumowanie<

Powiniene� teraz dobrze rozumie� wykresy i algorytmy, kt�rych mo�esz u�y� do ich przeszukiwania. Podobnie jak w przypadku wi�kszo�ci technik sztucznej inteligencji, twoje zrozumienie ogromnie wzro�nie dzi�ki praktycznemu do�wiadczeniu, dlatego zach�cam do podj�cia przynajmniej niekt�rych z poni�szych problem�w.

Praktyka czyni mistrza

1. Za pomoc� o��wka i papieru prze�led� algorytm DFS, BFS i Dijkstry dla poni�szego wykresu. Dla ka�dego wyszukiwania u�yj innego w�z�a pocz�tkowego i ko�cowego. Dodatkowe punkty zostan� przyznane za u�ycie stylu i koloru.

2. Utw�rz heurystyczn� klas� polityki odleg�o�ci Manhattan, aby oszacowa� odleg�o�� mi�dzy w�z�em a celem na wykresie nawigacyjnym. Spr�buj heurystyki z r�nymi wykresami. Czy jest lepsza czy gorsza ni� heurystyka euklidesowa dla graf�w opartych na siatce?

3. Euklidesowa heurystyka oblicza odleg�o�� w linii prostej mi�dzy w�z�ami. Obliczenia te wymagaj� u�ycia pierwiastka kwadratowego. Utw�rz heurystyk�, kt�ra dzia�a w przestrzeni z kwadratem odleg�o�ci i zwr�� uwag� na kszta�t tworzonych �cie�ek.

4. Utw�rz program, aby znale�� najlepsze rozwi�zanie dla wie� typu n-disk. Uk�adanka Hanoi, w kt�rej n mo�e by� dowoln� liczb� ca�kowit� dodatni�. Aby to zrobi�, musisz przepisz algorytm BFS, aby w�z�y i kraw�dzie zosta�y dodane do pliku wykres stanu w trakcie wyszukiwania. To doskona�y spos�b na przetestowanie twoje zrozumienie materia�u przedstawionego w tej cz�ci

5. Teraz zmodyfikuj algorytm utworzony w 4, aby wyszuka� najlepsze rozwi�zanie za pomoc� iteracyjnego pog��biania DFS. Jak to si� por�wnuje?

6. U�yj algorytmu A*, aby rozwi�za� potasowan� Kostk� Rubika. Du�o uwagi po�wi�� zaprojektowaniu funkcji heurystycznej. Jest to trudny problem, szukaj�c potencjalnie ogromnej przestrzeni wyszukiwania, wi�c najpierw wypr�buj sw�j algorytm na sze�cianie oddalonej tylko o jeden obr�t od rozwi�zania, a nast�pnie o dwa itd.

Skrypt, czy Nie-SkryptProgramownie A.I. Gier

Skrypt, czy Nie-Skrypt