Je me demande quels sont les avantages et les inconvénients de ces deux algorithmes. Je veux écrire addemup c ++ résolu, mais je suis Pas sûr de l'algorithme (IDA ou DFID) Devrais-je utiliser.
Le meilleur article que j'ai trouvé est celui-ci , mais il semble trop vieux - '93. Tout nouveau?
Je pense que l'IDA * serait mieux, mais ...? Toute autre idée?
Des idées et des informations seraient utiles.
merci! (:
edit: Un bon article sur l'IDA * et une bonne explication de l'algorithme?
Edit2: ou une bonne fonction heuristique pour ce jeu? Je ne sais pas comment penser à certains: /
3 Réponses :
Consultez Russell & Norvig , chapitres 3 et 4 et réalisez que l'IDA * est difficile à programme correctement. Vous voudrez peut-être essayer la meilleure première recherche (RBFS) récursive (RBFS), également décrite par R & N, ou Uni Old AN *. Ce dernier peut être implémenté à l'aide d'un std :: priority_queue .
IIRC, R & N décrit IDA * dans la première édition, puis l'a remplacée par des RBFS dans la seconde. Je n'ai pas encore vu la troisième édition.
En ce qui concerne votre deuxième édition, je n'ai pas examiné le jeu, mais une bonne procédure de dérivation des heuristiques est celle de problèmes détendus . Vous enlevez les règles du jeu jusqu'à ce que vous obteniez une version pour laquelle la heuristique est facilement exprimée et mise en œuvre (et pas cher à calculer). Ou, à la suite d'une approche ascendante, vous vérifiez les règles principales pour voir lequel admet une heuristique facile, puis essayez cela et ajoutez d'autres règles que vous en avez besoin.
Merci (: mais il semble que IDA * soit plus approprié pour ce jeu, si je ne me trompe pas. En raison de mes recherches, je pense que c'est l'algorithme correct pour ce problème. Comme vous dites que c'est très difficile, j'espère que c'est très difficile, j'espère que Quelqu'un va me convaincre dans le contraire ..: / :)
@Kiril: Avez-vous essayé d'implémenter un algorithme de recherche? Choisir l'algorithme de droite pour ce type de tâche n'est pas une science exacte: vous devrez en essayer plusieurs jusqu'à ce que vous en trouviez un qui fonctionne bien. Il se peut qu'un simple algorithme soit tout ce dont vous avez besoin.
ARGH, tu as raison. Je n'ai pas essayé. Mais je n'ai pas beaucoup de temps pour les tests, je me demandais simplement s'il y a un algorithme recommandé pour ce genre de jeux. Addemup semble (un littel) comme un problème de 8-puzzle, qui est résolu le plus efficacement en utilisant IDA *. Mais tu as raison, je suis d'accord.
"Le plus efficacement résolu par l'IDA *" ne signifie toujours pas grand chose sans préciser l'heuristique. Je recommande d'essayer des identifiants (ou DFID comme votre source l'appelle) sur des instances progressivement plus difficiles jusqu'à ce qu'elle casse, puis implémentez un * ou des RBFS si et quand il le fait. Il y a beaucoup de choix à faire lors de la mise en œuvre de la recherche, c'est pourquoi personne n'a écrit la bibliothèque pour elle.
Merci beaucoup pour l'information et pour vous aider (: apprécié. +1 Pour l'attention, les explications et suggérant R & N. 10Q
Le livre Russel & Norvig est une excellente référence sur ces algorithmes et je vais donner à Larsmans un virtuel haut-cinq pour le suggérer; Cependant, je suis en désaccord que IDA * est de manière appréciable de programmer que A *. Je l'ai fait pour un projet où j'ai dû écrire un IA pour résoudre un casse-tête en bloc coulissant - le problème familier d'avoir une grille N x N de carreaux numérotés, et à l'aide de l'espace libre unique pour glisser des carreaux jusqu'à ce qu'ils soient Dans l'ordre croissant.
rappel: g (n) = coût du chemin, la distance de l'initiale à l'état actuel
h (n) = heuristique, l'estimation du coût de l'état actuel à l'état final. Être une heuristique admissible (et assurer ainsi une optimalité * de *), vous ne pouvez en aucun cas surestimer le coût. Voir cette question pour plus d'informations sur les effets de la surestimation / sous-estimation des heuristiques sur un * .
N'oubliez pas que l'approfondissement itératif A * est juste
flimit augmente avec chaque itération extérieure; Avec chaque itération, vous êtes approfondissement la recherche.
Merci beaucoup, cela m'a vraiment aidé (: accepté.
@Aphex dans votre implémentation, une * et l'itération finale de l'IDA * utilise le même espace. La mise en œuvre proposée initiale (voir Citeserx.ist.psu.edu/ ViewDoc / Résumé? DOI = 10.1.1.91.288 ), l'auteur utilise une première recherche de profondeur-première dans chaque itération d'IDA * avec l'avantage qu'il n'y a pas besoin de stocker des listes ouvertes et fermées d'un * (il y a Une liste visitée pendant DFS qui doit être stockée si le graphique n'est pas un arbre).
C'est l'idée d'IDA *; La chance que vous puissiez trouver la solution dans une certaine profondeur (espérons-la plus peu profonde) sans avoir à traverser des nœuds plus profonds. Ce que vous et cet article décrit semble être IDDFS - approfondissement itératif de profondeur-première recherche (également appelé DFID) - pas d'approfondissement itératif A *.
@Aphex L'article indiqué est la publication originale de l'IDA *. L'algorithme a été introduit en raison de sa consommation de mémoire réduite (ce qui le rend applicable au problème particulier abordé dans l'article, résolvant un cube de Rubik, alors qu'un * ou un A * avec une limite de profondeur ne serait pas).
DFID n'est qu'un cas particulier d'IDA * où la fonction heuristique est la constante 0; En d'autres termes, il n'a aucune disposition pour introduire des heuristiques. Si le problème n'est pas suffisamment petit qu'il puisse être résolu sans utiliser des heuristiques, il semble que vous n'ayez aucun choix que d'utiliser IDA * (ou un autre membre de la famille A *). Cela dit, IDA * n'est vraiment pas si difficile: le implémentation < / a> fourni par les auteurs d'Aima n'est que d'environ une demi-page de code LISP; J'imagine qu'une implémentation C ++ ne devrait pas prendre plus de deux fois cela.
Ah, merci beaucoup pour votre réponse! J'utiliserai certainement IDA *. +1 de moi.
DFID n'est-il pas juste un cas particulier d'IDA * où la fonction heuristique est constamment 0? Donc, essentiellement, vous demandez si vous devriez utiliser une fonction heuristique.
@huaiyuan: C'est un cas particulier, mais pas de sens utile.