J'ai remarqué que différentes structures de données sont utilisées lorsque nous implémentons des algorithmes de recherche. Par exemple, nous utilisons des files d'attente pour implémenter la recherche en largeur, des piles pour implémenter la recherche en profondeur en premier et des tas en min pour implémenter l' algorithme A * . Dans ces cas, nous n'avons pas besoin de construire explicitement l'arbre de recherche.
Mais je ne trouve pas de structure de données simple pour simuler le processus de recherche de l' algorithme AO * . Je voudrais savoir si la construction explicite de l'arbre de recherche est le seul moyen d'implémenter l'algorithme AO *? Quelqu'un peut-il me fournir une mise en œuvre efficace?
Réponses:
En ce qui concerne cet article chaque fois que vous développez un nœud dans l'algorithme AO *, vous devez revenir en arrière pour mettre à jour le coût estimé de tous ses prédécesseurs.
Lorsque vous utilisez une structure de données linéaire pour contenir les nœuds, vous devez parcourir les éléments de données de manière séquentielle et un seul élément de données peut être directement pris (pile, file d'attente, file d'attente prioritaire…).
Dans AO *, chaque fois qu'un nœud est pris pour expansion en fonction de son coût estimé, l'algorithme itère sur tous les nœuds qui sont ses prédécesseurs (pour mettre à jour leur coût estimé). Cela signifie que vous devez parfois prendre l'élément en fonction de son coût estimé et parfois en fonction de son successeur. Aucun ordre de séquence ne peut remplir ces deux conditions dans le cas général. Il existe probablement un moyen d'utiliser des structures de données linéaires "imbriquées", mais cela devrait simplement imiter une structure arborescente, et il sera préférable de construire l'arborescence de recherche à la place.
la source
Je vais juste sortir de la description à laquelle vous avez lié, mais qu'en est-il d'un BST? Vous pourrez peut-être le construire pour équilibrer les nœuds non résolus. Cela pourrait vous faire gagner du temps à l'étape 2 et aiderait à réduire le temps global en fonction du nombre de traversées. Bien sûr, si vous équilibriez / triiez votre arbre en fonction de nœuds non résolus, vous seriez probablement au moins mieux qu'une structure de données plus simpliste, en conservant potentiellement le temps logarithmique.
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
la source