Jaka jest różnica między przeszukiwaniem wykresów a przeszukiwaniem drzewa?

98

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

Rayhanur Rahman
źródło

Odpowiedzi:

178

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
ziggystar
źródło
1
Dobra odpowiedź! Czy możesz wyjaśnić, co masz na myśli mówiąc o problemie drzewiastym ? Co więcej, w jaki sposób proponujesz zapisać ścieżkę pokonaną przez algorytm, aby osiągnąć cel, w przeciwieństwie do pełnego przejścia?
Brian
1
@Brian Problem w kształcie drzewa oznacza, że ​​szukany wykres jest drzewem. A jeśli chodzi o drugie pytanie: to zależy od problemu. Jedną z możliwości jest po prostu przechowywanie ścieżki do węzła razem z każdym rozwiniętym węzłem, jeśli jest to wykonalne.
ziggystar
5
Bardziej formalnie jest powiedzieć, że „pojedynczy stan” może być odwiedzany wiele razy poprzez przeszukiwanie drzewa, a NIE węzeł. Ponieważ każdy węzeł w drzewie wyszukiwania odpowiada pojedynczej ścieżce wzdłuż wykresu przestrzeni stanów i jest odwiedzany co najwyżej przez przeszukiwanie drzewa. (Choć nie jest to prawdą w przypadku Iteracyjnego Poszukiwania Pogłębiającego, które przechodzi przez drzewo z rosnącymi limitami głębokości, ale w tym przypadku również w każdej iteracji każdy węzeł jest odwiedzany tylko raz)
Nader Ghanbari
1
@NaderhadjiGhanbari To, stateczy nodejest bardziej odpowiednie dla wierzchołków bazowego wykresu problemu, w przeciwieństwie do wykresu przejścia, zależy od kontekstu. Jednak użycie statewierzchołków grafu problemu i nodewykresu przejścia może zdecydowanie poprawić klarowność odpowiedzi. Wkrótce spróbuję to przepisać. Dziękuję Ci.
ziggystar
TL; DR: przeszukiwanie wykresu używa zamkniętej struktury danych, podczas gdy przeszukiwanie drzewa nie.
shinzou,
7

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.

njlarsson
źródło
Hm, kontekst pytania nie jest dla mnie do końca jasny, ale patrząc na to ponownie po zobaczeniu Twojej odpowiedzi, @ziggystar, mam wrażenie, że wzmianka o A * i AI wskazuje, że możesz mieć rację i moja odpowiedź wyrwane z kontekstu. Zinterpretowałem „wyszukiwanie drzewa” jako „przeszukiwanie drzewa”. Nie „przeszukiwania ogólnego wykresu przy użyciu wzoru przechodzenia w kształcie drzewa”, co sugeruje twoja odpowiedź.
njlarsson
@njlarsson W mojej odpowiedzi zawarłem Twoje przeformułowanie. To dobre dla wyjaśnienia.
ziggystar
Dodałem uwagę na ten temat w odpowiedzi. Podejrzewam, że moja odpowiedź jest właściwa dla wielu ludzi, którzy trafiają tutaj przez Google itp., Nawet jeśli może to być wyrwane z kontekstu, o co chodziło Rayhanurowi Rahmanowi.
njlarsson
Widziałem wielu studentów, którzy mieli trudności ze studiowaniem algorytmów wyszukiwania, a Twoja odpowiedź po prostu ich wprowadza w błąd.
Nader Ghanbari
1
Odpowiedź dotyczy również algorytmów wyszukiwania, ale prawdą jest, że nie o to pytał plakat. Zobacz „Aktualizacja” w odpowiedzi - w marcu 2014 roku zdałem sobie sprawę, że źle zrozumiałem pytanie. Powodem, dla którego nie usuwam odpowiedzi, jest to, że może ona być nadal przydatna dla kogoś, kto przybył tutaj przez wyszukiwanie.
njlarsson
3

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.

0605002
źródło
3
Aby dodać do tego, jeśli naprawdę masz drzewo, nie musisz wykonywać wykrywania duplikatów w A *. Nadal będziesz potrzebować sposobu na wyodrębnienie ostatecznej ścieżki, więc nadal możesz mieć zamkniętą listę.
Nathan S.
W normalnych warunkach drzewo jest grafem skierowanym z co najwyżej jedną ścieżką między dowolnymi dwoma wierzchołkami. Oznacza to, że istnieją dwie różnice między wykresami a drzewami: ukierunkowana i niepowtarzalność ścieżki. Algorytm pracujący na DAG nie musi sprawdzać cykli, a algorytm pracujący na drzewie nie ma potrzeby sprawdzania duplikatów.
thiton
1
Terminologia jest różna, ale drzewa nie zawsze są traktowane jako ukierunkowane. W przypadku drzewa zakorzenionego , tj. Gdy jeden węzeł jest określony jako korzeń, istnieje domniemany kierunek, ale drzewa nie muszą być zakorzenione. Ponadto wykresy ogólne mogą być skierowane lub nieukierunkowane. Ponadto, jeśli wymagają tylko co najwyżej jedną ścieżkę pomiędzy dwoma wierzchołkami, to także lasy . Drzewo jest zwykle definiowane jako połączony wykres, tj. Musi istnieć dokładnie jedna ścieżka.
njlarsson
Ta odpowiedź odnosi się bardziej do różnicy między drzewami a grafami w teorii grafów, ale nie w przypadku różnych typów algorytmów wyszukiwania.
mlibby
1

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.

Mohamed Horani
źródło
Ta odpowiedź jest myląca, ponieważ wydaje się mieszać sytuację, w której problemem jest drzewo lub wykres, z tym, czy sam algorytm wyszukiwania używa drzewa lub wykresu podczas wyszukiwania.
mlibby
1

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.

Madhi
źródło