Pourquoi ida $ ^ * $ plus rapide qu'un $ ^ * $?Pourquoi ida $ ^ * $ visite plus de nœuds que $ ^ * $?

Question

j'ai utilisé ida $ ^ * $ pour résoudre de manière optimale le 8-puzzle et mes amis ont utilisé une $ ^ * $ pour cela aussi (avec la même heuristique de distance de Manhattan).

J'ai calculé l'heure moyenne et le nombre de nœuds de mon algorithme pour 20 exemples et l'algorithme de mon ami.La moyenne temporelle de mon algorithme était beaucoup plus rapide que l'algorithme de mon ami, mais mon nombre moyen de nœuds visités est beaucoup plus que celui de mon ami.

je connais iDA $ ^ * $ visite chaque noeud plus d'une fois mais pourquoi est-ce plus rapide qu'une classe $ ^ * * $ ?

Answer 1

Depuis que vous avez déjà implémenté IDA $ ^ * $ Vous comprenez certainement pourquoi il développe plus de nœuds que d'une $ ^ * $ , c'est-à-dire qu'il commence à partir de l'état de démarrage avec une nouvelle travertielle de profondeur-première dans chaque itération. Notez d'abord que, le nombre total de nœuds visité par IDA $ ^ * $ , tandis nécessairement plus grand qu'une classe $ ^ * $ " n'est pas si grand plus grand. La raison en est que le nombre de nœuds à chaque profondeur progresse selon une série géométrique avec facteur $ B $ , le facteur de ramification. En conséquence, le nombre de nœuds à la profondeur $ d $ , $ b ^ d $ est beaucoup Plus grande que la somme de tous les nœuds étendus aux itérations précédentes, c'est-à-dire $ b ^ d> \ sum_ {i= 0} ^ {d-1} b ^ i $ . De cette différence, il s'avère que l'IDA $ ^ * $ nécessite $ \ frac {b} {b-1} $ Expansions supplémentaires qui sont asymptotiquement optimales que la limite de la grande $ B $ est 1. conclure, pour tout algorithme visiter tous les nœuds à la profondeur $ d $ est beaucoup plus difficile que de visiter tous les nœuds aux profondeurs précédentes.

Si vous souhaitez approfondir davantage dans ce numéro, je vous recommande vivement de lire le papier original: Korf, Richard E. Profond First-First-itératif-approfondissement: une recherche d'arbre admissible optimale. Intelligence artificielle (27), 97-109, 1985. Voir en particulier Théorème 4.2:

L'approfondissement itératif de première profondeur est asymptotiquement optimal parmi recherche d'arbres de force brute en termes de temps, d'espace et de longueur de Solution.

Bien sûr, il offre des solutions optimales afin qu'elle soit admissible et donc optimale asymptotique. Il proie uniquement des travers de profondeur-premiers et donc, il est asymptotiquement optimal en termes d'espace (nécessitant une bonne implémentation uniquement $ o (d) $ ).

Quant à ce moment-là, j'ai déjà décrit la principale raison théorique mais faites-moi savoir trois principales raisons pour lesquelles il est si rapide dans la pratique:

1. Tout d'abord, pour presque tous les fins, la durée de fonctionnement globale de tout algorithme est dominée au moment où elle prend pour augmenter les nœuds (d'autres opérations sont plutôt simples et atomiques). Il est en effet lors de l'expansion des nœuds que IDA $ ^ * $ peut être extrêmement rapide car:

   1.1. Ida $ ^ * $ est mis en œuvre de manière récursive de sorte que tout ce que vous avez besoin est de prendre l'état donné comme un argument et de générer un enfant à la fois (pour votre cas spécifique signifie simplement échanger le blanc avec une tuile adjacente, c'est une seule déclaration!). Cependant, pour un $ ^ * $ L'opération d'expansion nécessite: d'abord faire apparaître un état de la file d'attente, puis générant tous ses enfants (c'est-à-dire déplacer la tuile vierge dans tout directions possibles).

   1.2. Alors que l'opération précédente fait une certaine différence, le vraiment important est celui d'une $ ^ * $ nécessite des nœuds de tri en ouvert. Même si vous faites cela avec un 1-godet (qui prendrait $ o (1) $ ), notez que ida $ ^ * $ ne nécessite pas de trier des nœuds du tout, de sorte que pendant qu'un $ ^ * $ prend du temps qui est linéaire dans le nombre de nœuds élargi, Ida $ ^ * $ n'en prend aucun du tout.

2. troisièmement, l'une des contributions des algorithmes de recherche Best-First (tels que une $ ^ * $ ) est qu'ils évitent de ré-étendre les nœuds par Utilisation d'une liste fermée (qui, malgré son nom, est généralement implémentée en tant que jeu !!). Ida $ ^ * $ n'a pas les mécanismes de détection des doublons à nouveau, encore une fois, une $ ^ * $ Effectue une opération supplémentaire qui n'est pas effectuée du tout par IDA $ ^ * $ . Si vous voulez en savoir plus sur Duplicate-détection dans ida $ ^ * $ Voir: Reinefeld, A.; Marsland, T. Amélioration de la recherche d'approfondissement itératif. IEEE transactions sur l'analyse de modèle et l'intelligence de la machine (16) 7, 701-710, 1994.

Le dernier point est vraiment pertinent. Dans le cas du puzzle de carreaux coulissants, il n'y a pas beaucoup de transpositions et le cycle le plus court est composé de 12 mouvements, de sorte que le nombre de re-expansions n'est pas si grande. Mettre tous ces ensemble, ida $ ^ * $ est une machine à tuer pour toutes les tailles du puzzle de tuiles coulissantes.

Toutefois, malgré tous ses avantages, il pourrait ne pas être d'intérêt pratique pour les applications qui ont un grand nombre de transpositions. Il y a eu diverses tentatives pour surmonter cette difficulté

Avec succès limité, voir par exemple:

Dow, P. Alex;Korf, Richard E. Dupliquer l'évitement dans une première recherche en profondeur avec des applications à Treewidth.Conférence commune internationale sur l'intelligence artificielle, 480-485, 2009.

J'espère que cela aide,