DFID (Depth-First iterativo approfondimento) vs. IDA * (iterativo-Approfondire A *)

Question

Mi chiedo quali sono i vantaggi e gli svantaggi di questi due algoritmi. Voglio scrivere Addemup C ++ risolto, ma sono non certo algoritmo che (IDA o DFID) dovrei usare.

L'articolo migliore che ho trovato è questo , ma sembra troppo vecchio - '93. Qualsiasi più recente?

Credo IDA * sarebbe meglio, ma ..? Tutte le altre idee?

Tutte le idee e le informazioni sarebbe utile.

Grazie! (:

Modifica Alcuni buon articolo su IDA * e buona spiegazione dell'algoritmo?

EDIT2: o un po 'di buona funzione euristica per quella partita? Non ho idea di come pensare a qualche: /

Answer 1

Il libro Russel & Norvig è un ottimo riferimento questi algoritmi, e ti darò un larsmans virtuale ad alta cinque per suggerirlo; tuttavia non sono d'accordo che IDA * è in alcun modo apprezzabile più difficile da programma di A *. L'ho fatto per un progetto in cui ho dovuto scrivere una IA per risolvere un puzzle scorrevole blocca - il problema familiare di avere un N x N griglia di tessere numerate, e utilizzando lo spazio libero singolo a piastrelle scivolare fino a quando sono in ordine crescente.

Recall:

F(n) = g(n) + h(n).

TotalCost = PathCost + Heuristic.

  

g (n) = costo percorso, la distanza dalla iniziale allo stato attuale

     

h (n) = euristica, la stima dei costi da stato a stato attuale fine. non essere un euristica ammissibile (e quindi garantire A * 's ottimalità), è possibile in ogni caso sovrastima il costo. Vedere questa domanda per maggiori informazioni sugli effetti della sovrastima / sottostima euristica su A * .

Ricordate che iterativo Approfondimento A * è solo A * con un limite al valore F di nodi che si è permesso di traslazione . Questo FLimit aumenta con ciascuna iterazione esterna; con ogni iterazione sei approfondimento la ricerca.

Ecco il mio codice C ++ attuazione sia A * e * IDA per risolvere il suddetto scorrimento blocco puzzle. Si può vedere che io uso un std::priority_queue con un comparatore personalizzato per gli stati negozio Puzzle nella coda con priorità per il loro valore F. Potrai anche notare che l'unica differenza tra A * e * IDA è l'aggiunta di un controllo FLimit e un ciclo esterno che incrementi questo FLimit. Spero che questo aiuta a far luce su questo argomento.

Answer 2

Russell & Norvig , capitoli 3 e 4, e rendersi conto che IDA * è difficile programmare in modo corretto. Si potrebbe desiderare di provare ricorsive migliori prima ricerca (RBFS), descritto anche da R & N, o pianura vecchio A *. Quest'ultimo può essere implementato usando un std::priority_queue .

IIRC, R & N descritti IDA * nella prima edizione, poi sostituito con RBFS nel secondo. Non ho ancora visto la terza edizione.

Per quanto riguarda la tua seconda modifica, non ho guardato in partita, ma una procedura buona per la derivazione euristica è quello di problemi rilassato . Si toglie le regole del gioco fino a quando si deriva una versione per il quale l'euristica è facilmente espresso e realizzato (ed economico per calcolare). Oppure, seguendo un approccio bottom-up, di controllare le regole principali per vedere quale si ammette un'euristica facile, quindi provare che e aggiungere altre regole quando ne hai bisogno.

Answer 3

DFID è solo un caso speciale di IDA * dove la funzione euristica è la costante 0; in altre parole, non ha alcuna disposizione per l'introduzione di euristica. Se il problema non è abbastanza piccolo da poter essere risolto senza l'utilizzo di euristiche, sembra avere altra scelta che utilizzare IDA * (o qualche altro membro della famiglia A *). Detto questo, IDA * non è poi così difficile: l'attuazione fornito da AIMA di autori è solo circa mezza pagina di codice Lisp; Immagino un'implementazione C ++ non dovrebbe richiedere più del doppio.