Perché è IDA $ ^ * $ più veloce di $ ^ * $?Perché Ida $ ^ * $ visitare più nodi di un $ ^ * $?

Question

Ho usato IDA $ ^ * $ per risolvere in modo ottimale l'8-puzzle e i miei amici usati a $ ^ * $ anche per questo (con lo stesso manhattan distanza heuristic).

Ho calcolato il tempo medio di corsa e il numero di nodi del mio algoritmo per 20 esempi e l'algoritmo del mio amico.La media del tempo per il mio algoritmo era molto più veloce dell'algoritmo del mio amico, ma il mio numero medio di nodi visitato è molto più del mio amico.

so Ida $ ^ * $ Visita ogni nodo più di una volta, ma perché è più veloce di una $ ^ * $ ?

Answer 1

Dal momento che hai già implementato IDA $ ^ * $ Hai certamente capito perché espande più nodi rispetto a una $ ^ * $ , cioè, inizia dallo stato di partenza con una nuova profondità prima traversata in ciascuna iterazione. Nota Prima che, il numero complessivo di nodi visitato da IDA $ ^ * $ , mentre necessariamente più grande di una $ ^ * $ non è molto più grande. La ragione è che il numero di nodi a ciascuna profondità progredisce secondo una serie geometrica con fattore $ B $ , il fattore di ramificazione. Di conseguenza, il numero di nodi in profondità $ d $ , $ B ^ d $ , è molto più grande della somma di tutti i nodi ampliati alle iterazioni precedenti, cioè, $ B ^ d> \ sum_ {i= 0} ^ {d-1} b ^ I $ . Da questa differenza, si scopre che IDA $ ^ * $ richiede $ \ frac {b} {b-1} $ Espansioni aggiuntive che è asintoticamente ottimale come il limite per il grande $ B $ è 1. Conclusione, per qualsiasi algoritmo in visita a tutti i nodi At profondità $ D $ è molto più difficile che visitare tutti i nodi alle profondità precedenti.

Nel caso in cui tu voglia approfondire di più in questo problema, ti consiglio vivamente di leggere la carta originale: Korf, Richard E. PROFONDA PRIMA ITERATIVA-APPRESSENZA: una ricerca ad albero ammissibile ottimale. Intelligenza artificiale (27), 97-109 del 1985. Vedi in particolare teorema 4.2:

.

PROFOND-First Iterativo-approfondimento è asintoticamente ottimale tra Albero di forza bruta ricerche in termini di tempo, spazio e lunghezza di soluzione.

Certo, offre soluzioni ottimali in modo che sia ammissibile e quindi, asintoticamente ottimale. Pratica solo le prime attraversali di profondità e pertanto, è asintoticamente ottimale in termini di spazio (richiedendo una buona implementazione solo $ o (d) $ ).

Per il momento, ho già delineato il principale motivo teorico, ma fammi sapere evidenziare tre motivi principali per cui è così veloce nella pratica:

.

1. Prima di tutto, per quasi tutti gli scopi, il tempo di esecuzione complessivo di qualsiasi algoritmo è dominato dal tempo necessario per espandere i nodi (altre operazioni sono piuttosto semplici e atomiche). È infatti quando si espande i nodi che IDA $ ^ * $ può essere straordinariamente veloce perché:

   1.1. Ida $ ^ * $ è implementato in modo ricorsivo in modo che tutto ciò di cui hai bisogno è prendere lo stato dato come argomento e per generare un bambino alla volta (per il tuo caso specifico Significa semplicemente scambiare lo spazio vuoto con una piastrella adiacente, questa è una sola dichiarazione!). Tuttavia, per una classe $ ^ * $ L'operazione di espansione richiede: Innanzitutto, schioccando uno stato dalla coda, quindi generando tutti i suoi figli (cioè spostare le piastrelle vuote in tutto Eventuali direzioni).

   1.2. Mentre l'operazione precedente fa qualche differenza, quella veramente importante è che una classe $ ^ * $ richiede nodi di ordinamento in aperto. Anche se lo fai con un 1-secchio (che prenderebbe $ o (1) $ ), nota che IDA $ ^ * $ non richiede affatto di ordinare i nodi, in modo che mentre è una classe $ ^ * $ richiede tempo che è lineare nel numero di nodi espansi, Ida $ ^ * $ non prende affatto.

2. In terzo luogo, uno dei contributi dei migliori algoritmi di ricerca (come una $ ^ * $ ) è che evitano di riesaminare i nodi Usando un elenco chiuso (che nonostante il suo nome viene solitamente implementato come un set !!). IDA $ ^ * $ Non ha Duplicate-Detection Meccanismi e quindi, ancora, una classe $> ^ * $ Esegue un funzionamento aggiuntivo che non viene eseguito affatto da IDA $ ^ * $ . Se vuoi saperne di più su Duplicate-Detection in IDA $ ^ * $ Vedi: Relefeld, a.; Marsland, T. T. Enhanced Iterative-Deeping Search. Transazioni IEEE sull'analisi del modello e sull'intelligenza della macchina (16) 7, 701-710, 1994.

L'ultimo punto è veramente rilevante. Nel caso del puzzle delle piastrelle scorrevoli non ci sono ancora molte trasposizioni e il ciclo più breve è composto da 12 mosse, in modo che il numero di riespirazione non sia così grande. Mettendo tutti questi insieme, Ida $ ^ * $ è una macchina killer per tutte le dimensioni del puzzle di piastrelle scorrevoli.

Tuttavia, nonostante tutti i suoi vantaggi, potrebbe non essere di interesse pratico in quelle applicazioni che hanno un gran numero di trasposizioni. Ci sono stati vari tentativi di superare questa difficoltà

Con un successo limitato, vedere ad esempio:

Dow, P. Alex;KORF, RICHARD E. DUPLICARE EVITAMENTO IN PROFONDA PRIMA CERCA CON APPLICAZIONI A TreeWidth.Conferenza congiunta internazionale sull'intelligenza artificiale, 480-485, 2009.

Spero che questo aiuti,