Am nevoie de un exemplu pentru a calcula penetranța și factorul de ramificare a arborelui de căutare în căutarea euristică a spațiului de stare. Definițiile sunt după cum urmează. Penetranță $ P $ este definit de
$ \ qquad \ displaystyle P = \ frac {L} {T} $
și factor de ramificare $ B $ este definit de
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
unde $ L $ este lungimea căii de la rădăcină la soluție și $ T $ numărul total de noduri extinse.
Răspuns
Luați în considerare următorul arbore de căutare. Algoritmul de căutare euristică începe căutarea la nodul rădăcină. Nodurile neexpandite sunt marcate cu gri.
Din anumite motive, euristica este ghidată spre subarborele cel mai stâng, când, de fapt, nodul obiectivului se află în subarborele din dreapta, marcat cu verde.
Noduri care au au fost mărite cu roșu. După ce sub-arborele cel mai stâng atrăgător s-a dovedit a fi o fundătură, euristica este acum, din fericire, ghidată direct spre obiectiv. Din situația din figura anterioară, vom extinde un total de trei noduri noi înainte de a ajunge la obiectiv.
Din figura de mai sus, lungimea căii către obiectiv este de 3 USD. Există noduri extinse de 17 USD. Prin urmare, penetranță este de 3 $ / 17 \ aproximativ 0,43 $.
factorul de ramificare este numărul maxim de succesori ai oricărui nod. De exemplu, factorul de ramificare a unui arbore binar este de 2 $, deoarece fiecare nod are cel mult doi copii. La fel, în arborele de căutare de mai sus, factorul de ramificare este de 3 $.
Ce se pare că vă interesează nu este factorul de ramificare, ci factorul de ramificare efectiv $ B ^ * $ care este o modalitate pentru a caracteriza calitatea unui euristic. Dacă numărul total de noduri extinse este de $ T $, iar lungimea căii către obiectiv este de $ L $ (acest lucru este mai frecvent cunoscut s adâncime ), atunci $ B ^ * $ este factorul de ramificare pe care l-ar avea un arbore uniform de adâncime $ L $ pentru a conține noduri $ T + 1 $. Prin urmare,
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Dacă conectați valorile pe care le-am obținut în căutare, adică $ T = 17 $ și $ L = 3 $, primiți $ B ^ * \ aproximativ 2.165 $. Aceasta este exact aceeași valoare pe care o obțineți folosind ecuația; este doar o reprezentare diferită pentru același lucru.
Factorul de ramificare eficient poate varia de la o instanță la alta, dar este oarecum constant pentru probleme destul de grele. O euristică bine concepută ar avea o valoare de $ B ^ * $ aproape de $ 1 $, permițând rezolvarea rezonabilă a problemelor destul de mari la un preț rezonabil.
Comentarii
- Rezolvând formula pentru $ B $, tu obțineți $ B \ aproximativ 2.165 $. Mă întreb care este interpretarea acestei valori. ' este aproape de factorul mediu de ramificare al tuturor nodurilor interioare, dar nu la fel.
- @MAcad De fapt, ceea ce vă interesează nu este factorul de ramificare, ci factorul de ramificare eficient care este departe de a caracteriza calitatea unui euristic. I îmi voi actualiza răspunsul.
- @Juho Cred că dacă folosesc formula factorului de ramificare, voi testa multe numere în LHS și le voi calcula și voi verifica egal cu RHS, după cum urmează: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 nu este egal T = 17 deci trebuie să testăm B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 rezultatul aproape de T, astfel încât să putem testa B = 2.1 și așa mai departe până când ajungem la rezultatul T !!!! Cred că această formulă se poate folosi așa :))))