Jaka jest różnica między wersjami przeszukiwania wykresów i przeszukiwania drzewa w odniesieniu do wyszukiwań DFS, A * w sztucznej inteligencji ?

Sądząc po istniejących odpowiedziach, wydaje się, że jest wiele nieporozumień co do tej koncepcji.

Problemem jest zawsze wykres

Rozróżnienie między przeszukiwaniem drzewa a przeszukiwaniem wykresów nie jest zakorzenione w fakcie, czy graf problemu jest drzewem, czy wykresem ogólnym. Zawsze zakłada się, że masz do czynienia z ogólnym wykresem. Różnica polega na wzorze przejścia używanym do przeszukiwania wykresu, który może mieć kształt wykresu lub drzewa.

Jeśli masz do czynienia z problemem w kształcie drzewa , oba warianty algorytmu prowadzą do równoważnych wyników. Możesz więc wybrać prostszy wariant wyszukiwania drzewa.

Różnica między wyszukiwaniem wykresu i drzewa

Twój podstawowy algorytm przeszukiwania wykresów wygląda mniej więcej tak. Z węzłem początkowym start, skierowanymi krawędziami jako successorsi goalspecyfikacją używaną w warunku pętli. openprzechowuje węzły w pamięci, które są obecnie rozważane, listę otwartą . Zauważ, że poniższy pseudokod nie jest poprawny pod każdym względem (2).

Wyszukiwanie drzew

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

W zależności od tego, jak zaimplementujesz select from open, otrzymujesz różne warianty algorytmów wyszukiwania, takie jak wyszukiwanie w głębi (DFS) (wybierz najnowszy element), wyszukiwanie wszerz (BFS) (wybierz najstarszy element) lub wyszukiwanie jednolitych kosztów (wybierz element o najniższym koszcie ścieżki ), popularne wyszukiwanie A-star poprzez wybranie węzła o najniższym koszcie i wartości heurystycznej , i tak dalej.

Powyższy algorytm nazywa się przeszukiwaniem drzewa . Będzie wielokrotnie odwiedzać stan podstawowego wykresu problemu, jeśli istnieje wiele skierowanych ścieżek do niego, kończących się w stanie początkowym. Możliwe jest nawet odwiedzanie stanu nieskończoną liczbę razy, jeśli leży on w ukierunkowanej pętli. Ale każda wizyta odpowiada innemu węzłowi w drzewie wygenerowanym przez nasz algorytm wyszukiwania. Ta pozorna nieefektywność jest czasami pożądana, jak wyjaśniono później.

Wyszukiwanie wykresów

Jak widzieliśmy, wyszukiwanie drzewa może wielokrotnie odwiedzać stan. W związku z tym kilka razy przejrzy „poddrzewo” znalezione po tym stanie, co może być kosztowne. Wyszukiwanie wykresów rozwiązuje ten problem, śledząc wszystkie odwiedzone stany na zamkniętej liście . Jeśli nowo znaleziony następca nextjest już znany, nie zostanie umieszczony na liście otwartej:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

Porównanie

Zauważamy, że przeszukiwanie wykresów wymaga więcej pamięci, ponieważ śledzi wszystkie odwiedzane stany. Może to zrekompensować mniejsza lista otwarta, co skutkuje lepszą wydajnością wyszukiwania.

Optymalne rozwiązania

Niektóre metody implementacji selectmogą zagwarantować zwrot optymalnych rozwiązań - np. Najkrótsza ścieżka lub ścieżka przy minimalnym koszcie (dla wykresów z kosztami dołączonymi do krawędzi). Zasadniczo ma to miejsce zawsze, gdy węzły są rozbudowywane w kolejności rosnącego kosztu lub gdy koszt jest niezerową dodatnią stałą. Powszechnym algorytmem, który implementuje ten rodzaj selekcji, jest wyszukiwanie jednolitych kosztów lub, jeśli koszty krokowe są identyczne, BFS lub IDDFS . IDDFS pozwala uniknąć agresywnego zużycia pamięci przez BFS i jest ogólnie zalecany do wyszukiwania bez informacji (inaczej brutalnej siły), gdy rozmiar kroku jest stały.

ZA*

Również (bardzo popularny) algorytm przeszukiwania drzewa A * zapewnia optymalne rozwiązanie, gdy jest używany z dopuszczalną heurystyką . Algorytm przeszukiwania grafów A * zapewnia jednak tę gwarancję tylko wtedy, gdy jest używany ze spójną (lub „monotoniczną”) heurystyką (warunek silniejszy niż dopuszczalność).

(2) Wady pseudokodu

Dla uproszczenia przedstawiony kod nie:

• radzi sobie z niepowodzeniem wyszukiwania, tzn. działa tylko wtedy, gdy można znaleźć rozwiązanie

Drzewo to szczególny przypadek wykresu, więc wszystko, co działa na wykresach ogólnych, działa w przypadku drzew. Drzewo to wykres, na którym między każdą parą węzłów znajduje się dokładnie jedna ścieżka. Oznacza to, że nie zawiera on żadnych cykli, jak stwierdza poprzednia odpowiedź, ale skierowany graf bez cykli (DAG, skierowany graf acykliczny) niekoniecznie jest drzewem.

Jeśli jednak wiesz, że twój wykres ma pewne ograniczenia, np. Że jest to drzewo lub DAG, zwykle możesz znaleźć bardziej wydajny algorytm wyszukiwania niż dla nieograniczonego wykresu. Na przykład prawdopodobnie nie ma sensu używanie A * lub jego nieheurystycznego odpowiednika „algorytmu Dijkstry” na drzewie (gdzie i tak jest tylko jedna ścieżka do wyboru, którą można znaleźć za pomocą DFS lub BFS) lub na DAG (gdzie można znaleźć optymalną ścieżkę, biorąc pod uwagę wierzchołki w kolejności uzyskanej przez sortowanie topologiczne).

Jeśli chodzi o graf skierowany vs nieukierunkowany, graf nieukierunkowany jest szczególnym przypadkiem grafu ukierunkowanego, a mianowicie przypadkiem, w którym obowiązuje zasada: „jeśli istnieje krawędź (łącze, przejście) od u do v, istnieje również krawędź od v do u .

Aktualizacja : Zwróć uwagę, że jeśli zależy Ci na schemacie przeszukiwania wyszukiwania, a nie na strukturze samego wykresu, to nie jest odpowiedź. Zobacz np. Odpowiedź @ ziggystar.

Jedyną różnicą między wykresem a drzewem jest cykl . Wykres może zawierać cykle, drzewo nie może. Więc kiedy zamierzasz zaimplementować algorytm wyszukiwania na drzewie, nie musisz brać pod uwagę istnienia cykli, ale pracując z dowolnym wykresem, musisz je wziąć pod uwagę. Jeśli nie poradzisz sobie z cyklami, algorytm może ostatecznie wpaść w nieskończoną pętlę lub nieskończoną rekursję.

Kolejną kwestią do przemyślenia są właściwości kierunkowe wykresu, z którym masz do czynienia. W większości przypadków mamy do czynienia z drzewami, które reprezentują relacje rodzic-dziecko na każdej krawędzi. DAG (skierowany wykres acykliczny) również wykazuje podobne cechy. Ale wykresy dwukierunkowe są różne. Każda krawędź na wykresach dwukierunkowych reprezentuje dwóch sąsiadów. Zatem podejścia algorytmiczne powinny się nieco różnić dla tych dwóch typów grafów.

WYKRES VS DRZEWO

• Wykresy mają cykle
• Drzewa nie mają cykli „Na przykład wyobraź sobie jakieś drzewo w swojej głowie, gałęzie nie mają bezpośredniego połączenia z korzeniem, ale gałęzie mają połączenia z innymi gałęziami w górę”

Ale w przypadku AI Graph-search vs Tree-search

Przeszukiwanie wykresów ma dobrą właściwość, która polega na tym, że za każdym razem, gdy algorytm eksploruje nowy węzeł i oznacza go jako odwiedzony, „Niezależnie od użytego algorytmu” algorytm zazwyczaj bada wszystkie inne węzły, które są osiągalne z bieżącego węzła.

Na przykład rozważ poniższy wykres z 3 wierzchołkami AB i C i rozważ następujące krawędzie

AB, BC i CA, Cóż, istnieje cykl od C do A,

A kiedy DFS rozpocznie się od A, A wygeneruje nowy stan B, B wygeneruje nowy stan C, ale kiedy C zostanie zbadany, algorytm spróbuje wygenerować nowy stan A, ale A jest już odwiedzony, więc zostanie zignorowany. Chłodny!

A co z drzewami? Cóż, algorytm drzew nie zaznacza odwiedzanego węzła jako odwiedzonego, ale drzewa nie mają cykli, jak by to było w nieskończonych pętlach?

Rozważ to Drzewo z 3 wierzchołkami i rozważ następujące krawędzie

A - B - C zakorzenione w A, w dół. Załóżmy, że używamy algorytmu DFS

A wygeneruje nowy stan B, B wygeneruje dwa stany A i C, ponieważ drzewa nie mają opcji „Oznacz węzeł odwiedzony, jeśli jest eksplorowany”, więc może algorytm DFS ponownie eksploruje A, generując w ten sposób nowy stan B, a zatem wchodzimy w nieskończoną pętlę.

Ale czy zauważyłeś coś, pracujemy nad nieukierunkowanymi krawędziami, tj. Istnieje połączenie między AB i BA. oczywiście nie jest to cykl, ponieważ cykl implikuje, że wierzchołki muszą być> = 3, a wszystkie wierzchołki są różne z wyjątkiem pierwszego i ostatniego węzła.

ST A-> B-> A-> B-> A to nie jest cykl, ponieważ narusza właściwość cykliczną> = 3. Ale rzeczywiście A-> B-> C-> A jest cyklem> = 3 różne węzły Zaznaczone, pierwszy i ostatni węzeł są takie same Zaznaczone.

Ponownie rozważmy krawędzie drzewa, A-> B-> C-> B-> A, oczywiście nie jest to cykl, ponieważ istnieją dwa Bs, co oznacza, że ​​nie wszystkie węzły są różne.

Wreszcie możesz zaimplementować algorytm przeszukiwania drzewa, aby zapobiec dwukrotnemu eksplorowaniu tego samego węzła. Ale to ma konsekwencje.

Mówiąc prościej, drzewo nie zawiera cykli i gdzie, jak wykres, może. Dlatego podczas wyszukiwania powinniśmy unikać cykli w grafach, aby nie dostać się do nieskończonych pętli.

Innym aspektem jest to, że drzewo zazwyczaj ma pewnego rodzaju sortowanie topologiczne lub właściwość, taką jak drzewo wyszukiwania binarnego, która sprawia, że ​​wyszukiwanie jest tak szybkie i łatwe w porównaniu do wykresów.