Wyszukiwanie wiązki

W informatyce przeszukiwanie wiązek to heurystyczny algorytm wyszukiwania , który eksploruje graf, rozszerzając najbardziej obiecujący węzeł w ograniczonym zbiorze . Wyszukiwanie wiązki to optymalizacja wyszukiwania od najlepszego, która zmniejsza wymagania dotyczące pamięci. Wyszukiwanie najlepsze od pierwszego to przeszukiwanie grafów, które porządkuje wszystkie rozwiązania cząstkowe (stany) zgodnie z pewną heurystyką. Jednak w wyszukiwaniu wiązek tylko określona liczba najlepszych rozwiązań cząstkowych jest przechowywana jako kandydaci. Jest to zatem algorytm zachłanny .

Termin „przeszukiwanie wiązki” został wymyślony przez Raja Reddy'ego z Carnegie Mellon University w 1977 roku.

Detale

Wyszukiwanie wiązki wykorzystuje przeszukiwanie wszerz do budowy drzewa wyszukiwania . Na każdym poziomie drzewa generuje wszystkie następniki stanów na bieżącym poziomie, sortując je według rosnącego kosztu heurystycznego. Jednak przechowuje tylko określoną z góry liczbę $najlepszych$ stanów na każdym poziomie (zwaną szerokością wiązki) Tylko te stany są dalej rozwijane. Im większa szerokość wiązki, tym mniej stanów jest przycinanych. Przy nieskończonej szerokości wiązki żadne stany nie są przycinane, a przeszukiwanie wiązki jest identyczne z przeszukiwaniem wszerz . Szerokość wiązki ogranicza pamięć wymaganą do przeprowadzenia wyszukiwania. Ponieważ stan docelowy może potencjalnie zostać przycięty, wyszukiwanie wiązki poświęca kompletność (gwarancję, że algorytm zakończy się rozwiązaniem, jeśli takie istnieje). Wyszukiwanie wiązki nie jest optymalne (to znaczy nie ma gwarancji, że znajdzie najlepsze rozwiązanie).

Używa

Wyszukiwanie wiązki jest najczęściej używane do utrzymania łatwości obsługi w dużych systemach z niewystarczającą ilością pamięci do przechowywania całego drzewa wyszukiwania. Na przykład był używany w wielu tłumaczenia maszynowego . (Obecnie stan techniki wykorzystuje głównie neuronowym tłumaczeniu maszynowym ). Aby wybrać najlepsze tłumaczenie, każda część jest przetwarzana i pojawia się wiele różnych sposobów tłumaczenia słów. Najlepsze najlepsze tłumaczenia zgodnie z ich strukturą zdań są zachowywane, a pozostałe są odrzucane. Następnie tłumacz ocenia tłumaczenia według zadanego kryterium, wybierając tłumaczenie, które najlepiej odpowiada celom. Pierwsze użycie wyszukiwania wiązką miało miejsce w Harpy Speech Recognition System, CMU 1976.

Warianty

Wyszukiwanie wiązek zostało zakończone przez połączenie go z przeszukiwaniem w głąb , co skutkuje przeszukiwaniem stosu wiązek i przeszukiwaniem wiązek w pierwszej kolejności , oraz z wyszukiwaniem ograniczonej rozbieżności, co skutkuje przeszukiwaniem wiązek przy użyciu śledzenia ograniczonej rozbieżności (BULB). Wynikowe algorytmy wyszukiwania to algorytmy działające w dowolnym momencie , które szybko znajdują dobre, ale prawdopodobnie nieoptymalne rozwiązania, takie jak wyszukiwanie wiązek, a następnie wycofują się i kontynuują znajdowanie ulepszonych rozwiązań, aż do uzyskania zbieżności do rozwiązania optymalnego.

W kontekście wyszukiwania lokalnego nazywamy przeszukiwanie wiązką lokalną określonym algorytmem, który rozpoczyna wybieranie losowo generowanych stanów, a następnie $na$ każdym poziomie drzewa wyszukiwania zawsze bierze pod uwagę ${\ displaystyle \ beta$ nowe stany spośród wszystkich możliwych następców obecnych, aż do osiągnięcia celu.

Ponieważ wyszukiwanie wiązek lokalnych często kończy się na lokalnych maksimach, powszechnym rozwiązaniem jest wybieranie kolejnych $losowy$ , z prawdopodobieństwem zależnym od heurystycznej oceny stanów. Ten rodzaj wyszukiwania nazywa się przeszukiwaniem wiązki stochastycznej .

Inne warianty to elastyczne wyszukiwanie wiązki i wyszukiwanie wiązki odzyskiwania .