Percebi que diferentes estruturas de dados são usadas quando implementamos algoritmos de busca. Por exemplo, usamos filas para implementar a primeira pesquisa de largura, pilhas para implementar a pesquisa em profundidade e min-heaps para implementar o algoritmo A * . Nesses casos, não precisamos construir a árvore de pesquisa explicitamente.
Mas não consigo encontrar uma estrutura de dados simples para simular o processo de busca do algoritmo AO * . Gostaria de saber se a construção explícita da árvore de pesquisa é a única maneira de implementar o algoritmo AO *? Alguém pode me fornecer uma implementação eficiente?
Respostas:
Em relação a este artigo toda vez que você expande um nó no algoritmo AO *, deve voltar para atualizar todos os custos estimados de seus predecessores.
Ao usar a estrutura de dados linear para conter os nós, você deve percorrer os elementos de dados sequencialmente e apenas um elemento de dados pode ser obtido diretamente (pilha, fila, fila de prioridade ...).
No AO * sempre que um nó é levado para expansão com base em seu custo estimado, o algoritmo itera sobre todos os nós que são seus predecessores (para atualizar seu custo estimado). Isso significa que, às vezes, você deve usar um elemento com base em seu custo estimado e, outras vezes, em seu sucessor. Não há ordem de sequência que possa atender a essas duas condições no caso geral. Provavelmente, existe uma maneira de usar estruturas de dados lineares "aninhadas", mas deve apenas imitar uma estrutura em árvore, e será melhor construir a árvore de pesquisa.
fonte
Estou apenas saindo da descrição à qual você vinculou, mas e um BST? Você pode construí-lo para equilibrar os nós não resolvidos. Isso economizaria tempo na etapa 2 e ajudaria a manter o tempo geral baixo, dependendo do número de travessias. Obviamente, se você equilibrar / classificar sua árvore de acordo com os nós não resolvidos, provavelmente seria pelo menos melhor do que uma estrutura de dados mais simplista, mantendo potencialmente o tempo logarítmico.
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
fonte