Criteri di terminazione per bidirezionale Ricerca

Question

Secondo la maggior parte della lettura che ho fatto, un algoritmo di ricerca bidirezionale è detto per terminare quando la "avanti" e frontiere "arretrate" prima si intersecano. Tuttavia, nella sezione 3.4.6 della Intelligenza Artificiale: un approccio moderno , Russel e Norvig stato:

  

bidirezionale di ricerca è implementata sostituendo il test gol con un controllo per vedere   se le frontiere dei due ricerche intersezione; se lo fanno, una soluzione è stata trovata.   È importante rendersi conto che la prima soluzione trovata potrebbe non essere ottimale, anche se il   due ricerche sono entrambi in ampiezza; qualche ulteriore ricerca è necessaria per assicurarsi che non ci   Non è un collegamento attraverso il traferro.

ho considerato questa dichiarazione per un bel po 'di tempo, ma sono in grado di trovare un esempio di questo comportamento. chiunque può fornire un grafico esempio in cui il primo incrocio tra le frontiere avanti e all'indietro di un BFS bidirezionali o A * ricerca non è il percorso più breve?

Modifica Chiaramente BFS non troverà il percorso più breve in un grafico ponderata. Sembra che questo estratto si riferisce BFS bidirezionali su un grafo non orientato. In alternativa, Sarei interessato a vedere un controesempio utilizzando bidirezionale A * su un grafo pesato.

Answer 1

Non so se questo è ciò che avevano in mente Russel e Norvig, ma se il grafico è ponderata (cioè alcuni bordi sono più di altri), il più breve percorso potrebbe avere più passaggi rispetto un'altra che sarebbe trovato prima in una BFS. Anche se il numero di passi è la stessa, il migliore non potrebbe essere trovato prima; prendere in considerazione un grafico con sei nodi:

(A-> B) = (A-> C) = 0

(B-> D) = 2

(C-> E) = 1

(D> F) = (E-> F) = 0

Dopo un passo avanti da A e uno indietro tra F, frontiera avanti è {B, C} ed il confine all'indietro è {D, E}. Il ricercatore ora si espande B e hey! intersezione! (A-> B-> D> F) = 2. Ma dovrebbe ancora cercare un po 'più lontano per scoprire che (A-> C> E-> F) è meglio.

Answer 2

Io penso che abbia a che fare con il modo bidirezionale di ricerca è implementata.

Il pseudocodice per BFS più o meno così:

until frontier.empty?
    node <- frontier.pop()
    add node to explored
    for each child not in expored or frontier:
        if child is goal then
            return path
        add child to frontier

Immaginate attuazione di ricerca bidirezionale in questo modo:

until frontierForward.emtpy? or frontierBackward.empty?
    node <- frontierForward.pop()
    add node to exploredForward
    for each child not in exporedForward or frontierForward:
        if child in frontierBackward then
            return pathForward + pathBackward
        add child to frontierForward

    Do something similar but now searching backwards

Fondamentalmente, fasi di BFS BFS e "in avanti", "indietro" alternati. Ora immaginate un grafico come questo:

    B-C-D
  /       \
A           E
  \       /
    F - G

Le piste prima in avanti e indietro di BFS ci darebbe uno stato come questo:

1) expandedForward = A ; frontierForward = B, F
2) expandedBackward = E ; frontierBackward = D, G

Ora l'algoritmo sceglie il nodo successivo per espandere dalla frontiera in avanti e raccoglie B.

3) expandedForward = A, B ; frontierForward = F, C

Ora corriamo indietro un BFS ed espandere il nodo D. D's bambino, C, è nella frontiera in avanti, in modo da restituire il percorso A - B - C - D -. E

Credo che questo è ciò che Russel e Norvig dove riferendosi a. Se l'implementazione non considera questo scenario si potrebbe dare una soluzione che non è ottimale.

Si deve finire in espansione tutti i nodi della frontiera che hanno lo stesso "profondità", prima di decidere che ha trovato una soluzione ottimale. Oppure alternare ricerche in avanti e indietro da BFS strato e non dal nodo (espandere avanti tutti i nodi nel livello 0, espandere arretrate tutti i nodi strato 0, espandere tutti i nodi nel livello 1, ecc.)

Answer 3

In un (costo unitario) grafo pesato, BFS bidirezionale ha trovato la soluzione ottimale quando colpisce l'incrocio, come Russell & Norvig stessi menzionato a pagina 80 della edizione di '' AIMA '' 2003:

  

bidirezionale ricerca è implementata da avere uno o entrambi i ricerche controllare ogni nodo prima di essere espansa per vedere se è nella frangia dell'altro albero di ricerca [...] L'algoritmo è completa e ottimale ( per i costi di passo uniforme) se entrambe le ricerche sono in ampiezza [.]

(per "l'espansione di un nodo", R & N significa generare successori. Corsivo.)

Answer 4

un triangolo semplice sarebbe soddisfare la condizione, con i lati essendo 6,6,10 con il percorso ottimale passa attraverso il segmento di lunghezza 10. In bidirezionale, le ricerche algoritmo del percorso più breve in avanti, allora inverso sarebbe anche prendere il percorso più breve, si sarebbero incontrati, un percorso completo viene trovato

, ma chiaramente 2 segmenti di 6 + 6 è peggio di un segmento di lunghezza 10.