ricerca in ampiezza ramificazione fattore

Question

Il tempo di esecuzione di BFS è O (b^d)

b è il fattore di ramificazione d è la profondità (° livello) del grafico avvio nodo.

Ho cercato su google per un po ', ma ho ancora non vedo nessuno parlare di come essi capire questo "b"

fattore

Quindi so ramificazione significa "# di bambini che ogni nodo ha"

Eg, il fattore di ramificazione per un albero binario è 2.

quindi per un grafico BFS, è che b = media tutto il fattore di ramificazione di ciascun nodo nel nostro grafico.

o b = MAX (tra tutti i fattori di diramazione di ciascun nodo)?

Inoltre, indipendentemente dal modo in cui selezioniamo il b, sembra ancora ambiguo avvicinarci al nostro tempo di esecuzione. Ad esempio, se il nostro grafico ha 30000 nodi, solo 5 nodi hanno 10.000 ramificazioni e tutti gli altri 29955 nodi hanno solo 10 diramazioni. e abbiamo l'impostazione di profondità per essere 100.

Sembra O (b^d) non ha senso in questo caso.

Qualcuno può spiegare un po '. Grazie!

Answer 1

Il runtime che viene più spesso citato è che BFS è O (m + n) dove m è il numero di fronti e n il numero di nodi. Questo perché ogni vertice viene elaborato una volta e ogni lato al massimo due volte.

Penso che O (b^d) sia usato quando si usa BFS su, per esempio, forzare brute una partita di scacchi, dove ogni posizione ha un fattore di ramificazione relativamente costante e il motore deve cercare un certo numero di posizioni in profondità . Ad esempio, b è circa 35 per gli scacchi e Deep Blue ha una profondità di ricerca di 6-8 (fino a 20).

In questi casi, poiché il grafico è relativamente aciclico, b^d è più o meno lo stesso di m + n (sono uguali per gli alberi). O (b^d) è più utile dato che b è fisso e d è qualcosa che controlli.

Answer 2

nei grafici O (b^d), il b = MAX. Dal momento che è il caso peggiore. controllare questo link da Princeton http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Breadth-first_search.html - andare a parte la complessità tempo

Answer 3

citare Intelligenza Artificiale - Un approccio moderno da Stuart Russel e Peter Norvig:

tempo e lo spazio della complessità sono sempre considerati rispetto a qualche misura della difficoltà del problema. Nell'informatica teorica, la misura tipica è la dimensione del grafico dello spazio di stato, | V | + | E |, dove V è l'insieme di vertici (nodi) del grafico ed E è l'insieme di spigoli (collegamenti). Questo è appropriato quando il grafico è una struttura dati esplicita che viene inserita nel programma di ricerca. (La mappa della Romania ne è un esempio). Nella IA, il grafico è spesso rappresentato implicitamente dallo stato iniziale, dalle azioni e dal modello di transizione ed è spesso infi- nito. Per questi motivi, la complessità è espressa in termini di tre quantità: b, il fattore di ramificazione o il numero massimo di successori di qualsiasi nodo; d, la profondità del nodo obiettivo più superficiale (cioè il numero di passi lungo il percorso dalla radice); e m, la lunghezza massima di qualsiasi percorso nello spazio degli stati.Il tempo viene spesso misurato in termini di numero di nodi generati durante la ricerca e spazio in termini di numero massimo di nodi memorizzati nella memoria. Per la maggior parte, descriviamo la complessità del tempo e dello spazio per la ricerca su un albero; per un grafico, la risposta dipende da quanto "ridondanti" sono i percorsi nello spazio degli stati.

Questo dovrebbe dare una chiara comprensione circa la differenza tra O (| V | + | E |) e b^d