Qual è il punto dell'algoritmo IDA * vs A *

Question

Non capisco come lo IDA* risparmi spazio di memoria. Da come ho capito IDA* è A* con approfondimento iterativo.

Qual è la differenza tra la quantità di memoria A* utilizza vs IDA*.

L'ultima iterazione di IDA* non si comporta esattamente come A* e utilizza la stessa quantità di memoria. Quando rintraccio IDA* mi rendo conto che deve anche ricordare una coda di priorità dei nodi che si trovano sotto la soglia f(n).

Capisco che la prima ricerca dell'ID-depth aiuta la ricerca approfondita per prima, permettendole di fare una ricerca per ampiezza prima senza dover ricordare ogni nodo. Ma ho pensato che A* si comporta già come la profondità prima, perché in esso ignora alcuni sotto-alberi lungo la strada. In che modo l'approfondimento progressivo fa sì che usi meno memoria?

Un'altra domanda è Profondità prima ricerca con approfondimento iterativo consente di trovare il percorso più breve facendolo comportarsi in larghezza prima come. Ma A* restituisce già il percorso ottimale più breve (dato che l'euristica è ammissibile). In che modo l'approfondimento iterativo lo aiuta. Mi sembra che l'ultima iterazione di IDA * sia identica a A*.

Answer 1

In IDA*, a differenza di A*, non è necessario mantenere un gruppo di nodi provvisori che si desidera visitare, pertanto il consumo di memoria è dedicato solo alle variabili locali della funzione ricorsiva.

Sebbene questo algoritmo è più basso sul consumo di memoria, ha i suoi difetti:

differenza A *, IDA * non utilizzare la programmazione dinamica e quindi spesso finisce esplorando gli stessi nodi molte volte. (IDA* In Wiki)

La funzione euristica deve ancora essere specificato per il vostro caso, al fine di non eseguire la scansione di tutto il grafico, ma la memoria della scansione richiesta in ogni momento è solo il percorso che si sta effettuando la scansione senza i suoi nodi circostanti.

Ecco una demo della memoria richiesta in ogni algoritmo:

Nel A* algoritmo di tutti i nodi ed i loro nodi circostanti deve essere incluso nella "necessità di visita "lista mentre nello IDA* ottieni i nodi successivi" pigramente "quando raggiungi il suo nodo di anteprime in modo da non doverlo includere in un set extra.

Come accennato nei commenti, IDA* is basically just IDDFS with heuristics: