Potrzebuję przykładu, jak obliczyć penetrację i czynnik rozgałęzienia drzewa wyszukiwania w heurystycznym wyszukiwaniu w przestrzeni stanów. Definicje są następujące. Penetrance $ P $ jest zdefiniowane przez
$ \ qquad \ displaystyle P = \ frac {L} {T} $
i współczynnik rozgałęzienia $ B $ jest zdefiniowane przez
$ \ qquad \ Displaystyle \ Frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
gdzie $ L $ to długość ścieżki od katalogu głównego do rozwiązania, a $ T $ to całkowita liczba rozwiniętych węzłów.
Odpowiedź
Rozważmy następujące drzewo wyszukiwania. Twój heurystyczny algorytm wyszukiwania rozpoczyna wyszukiwanie w węźle głównym. Nierozszerzone węzły są zaznaczone na szaro.
Z jakiegoś powodu heurystyka jest kierowana w kierunku skrajnego lewego poddrzewa, kiedy w rzeczywistości węzeł celu znajduje się w prawym poddrzewie, oznaczonym kolorem zielonym.
Węzły, które mają rozszerzone są zaznaczone na czerwono. Po tym, jak atrakcyjne skrajne lewe poddrzewo okazało się ślepą uliczką, heurystyka jest teraz na szczęście kierowana bezpośrednio do celu. Z sytuacji z poprzedniego rysunku „rozszerzymy w sumie trzy nowe węzły przed dotarciem do celu.
Z powyższego rysunku wynika, że długość ścieżki do celu wynosi 3 USD. Istnieje 17 USD rozwiniętych węzłów. Dlatego penetracja wynosi 3/17 $ \ około 0,43 $.
Współczynnik rozgałęzienia to maksymalna liczba następców dowolnego węzła. Na przykład współczynnik rozgałęzienia drzewa binarnego wynosi 2 $, ponieważ każdy węzeł ma co najwyżej dwoje dzieci. Podobnie w powyższym drzewie wyszukiwania współczynnik rozgałęzienia wynosi 3 $.
Co wydaje się, że Cię interesuje nie czynnik rozgałęzienia, ale efektywny współczynnik rozgałęzienia $ B ^ * $, który jest sposobem scharakteryzować jakość heurystyki. Jeśli łączna liczba rozwiniętych węzłów to $ T $, a długość ścieżki do celu to $ L $ (jest to bardziej znane s głębokość ), to $ B ^ * $ jest współczynnikiem rozgałęzienia, jaki miałoby jednolite drzewo o głębokości $ L $, aby zawierać węzły $ T + 1 $. Dlatego
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Jeśli podłączasz wartości, które uzyskaliśmy podczas wyszukiwania, to znaczy $ T = 17 $ i $ L = 3 $, otrzymujesz $ B ^ * \ ok. 2,165 $. To jest dokładnie ta sama wartość, którą otrzymujesz używając swojego równania; to po prostu inna reprezentacja tej samej rzeczy.
Efektywny współczynnik rozgałęzienia może się różnić w różnych instancjach, ale jest nieco stały dla wystarczająco trudnych problemów. Dobrze zaprojektowana heurystyka miałaby wartość $ B ^ * $ blisko 1 $, co pozwala na rozsądne i tanie rozwiązywanie dość dużych problemów.
Komentarze
- Rozwiązując wzór na $ B $, uzyskać $ B \ około 2,165 $. Zastanawiam się, jaka jest interpretacja tej wartości. Jest ' zbliżona do średniego współczynnika rozgałęzienia wszystkich węzłów wewnętrznych, ale nie jest taka sama.
- @MAcad W rzeczywistości to, co Cię interesuje, to nie czynnik rozgałęzienia, ale efektywny czynnik rozgałęziający, który jest daleki od charakteryzowania jakości heurystyki. I ' zaktualizuję moją odpowiedź.
- @Juho Myślę, że jeśli użyję wzoru na współczynnik rozgałęzienia, przetestuję wiele liczb w LHS i obliczę go i sprawdzę równość z RHS w następujący sposób: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 różne od T = 17, więc musimy przetestować B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 wynik w pobliżu T, więc możemy testować B = 2,1 i tak dalej, aż osiągniemy wynik T !!!! Myślę, że tej formuły można użyć w ten sposób :))))