Come implementare l'algoritmo AO *?

Question

Ho notato che alcune strutture dati vengono utilizzate quando implementiamo algoritmi di ricerca. Ad esempio, utilizziamo la coda per implementare BFS, stack per implementare DFS e min-heap per implementare l'algoritmo A *. In questi casi, non è necessario costruire l'albero di ricerca in modo esplicito.

Ma non riesco a trovare una struttura dati semplice per simulare il processo di ricerca dell'algoritmo AO *. Mi piacerebbe sapere se costruire l'albero di ricerca in modo esplicito è l'unico modo per implementare l'algoritmo AO *? Qualcuno può fornirmi un'implementazione efficiente? Apprezzo molto il vostro aiuto.

Answer 1

Disclaimer: Non ho implementato AO *, quindi potrei sbagliarmi.

L'implementazione di AO * non dovrebbe essere diverso da A *. Si utilizza un heap ma invece di avere solo un singolo nodo, ogni membro dovrebbe essere un vettore di nodi (uno o più nodi). In una certa misura dipende da come vengono date le (e-o) regole, ma la compilazione dell'heap dovrebbe essere davvero semplice. Quindi la risposta alla prima domanda è no, non c'è bisogno di costruire l'albero esplicitamente come nel senso che non lo fai per A *. Ricorda che un heap è in realtà una rappresentazione di un albero di ricerca, quindi potresti obiettare che stai davvero costruendo l'albero mentre lo attraversi. Riguardo a

Qualcuno può fornirmi un'implementazione efficiente?

è necessario mostrare qualche sforzo fornendo almeno qualche pseudocodice o ancora meglio una porzione di codice che mostri come si è attaccato il problema. Quindi possiamo venire con suggerimenti su come aumentare l'efficienza migliorando la struttura dei dati.