* Algorithme De Recherche

Je voudrais avoir quelque chose a clarifié en ce qui concerne à la suite d'Un* exemple de Recherche:

* Algorithme De Recherche

Les sections en surbrillance avec le rouge des ellipses sont les domaines que je ne comprends pas; il semble que {S,B} f=2+6=8 a été pris/déplacés ou copiés à partir de Expand S (ci-dessus) et utilisé dans Expand A. Il apparaît également que {S,A,X} f=(1+4)+5=10 a été pris/déplacés ou copiés à partir de Expand A et utilisé dans Expand B.

Quelqu'un pourrait m'expliquer pourquoi cela se produit? Je suis capable de lire le graphique parfaitement bien et n'ont pas de difficultés dans l'interprétation - c'est simplement le fait que je ne sais pas pourquoi ladite chemins/routes ont été reproduits ailleurs.

Merci.

OriginalL'auteur MusTheDataGuy | 2011-05-01

  1. 8

    C'est de prendre le meilleur élément, de le retirer et de le remplacer avec de l'expansion (l'insertion de nouveaux éléments dans la position appropriée dans la liste). Pensez-y comme ça:

    Développez S:

    • {S,A} f = 1+5 = 6
    • {S,B} f = 2+6 = 8

    Développez Un:

    • {S,A} f = 1+5 = 6
    • {S,B} f = 2+6 = 8
    • {S,A,X} f = (1+4)+5 = 10
    • {S,A,Y} f = (1+7)+8 = 16

    Développez B:

    • {S,B} f = 2+6 = 8
    • {S,A,X} f = (1+4)+5 = 10
    • {S,B,C} f = (2+7)+4 = 13
    • {S,A,Y} f = (1+7)+8 = 16
    • {S,B,D} f = (2+1)+15 = 18
    Génial, merci - qui semble aider.
    Monsieur, je suis nouveau à l'intelligence artificielle, et dans le contexte de ce schéma, j'ai un doute que ici * Un* sont nécessaires pour calculer tous les chemins possibles.* alors comment est-il utile ? et dans Riche et chevalier ses mentionné que h' ne devrait pas surestimer h, et dans le wikipedia de ses écrits que le coût estimé (h') doit toujours être au moins égaux ou supérieurs au coût réel de la réalisation de l'objectif. Donc, cela signifie que nous devons calculer tous les chemins possibles à l'avance? est-ce vrai ? ou ai-je raté quelque chose. Serait une grande aide Sir.

    OriginalL'auteur

  2. 2

    Les chemins ne sont pas dupliqués, elles restent simplement comme des chemins que l'algorithme n'a pas exploré encore. * Fonctionne par le maintien d'un ensemble ouvert, c'est l'ensemble des nœuds de l'algorithme sait déjà comment l'atteindre (et par quel coût), mais il n'a pas essayé de les étendre encore.

    À chaque itération de l'algorithme choisit un nœud à développer à partir de l'ensemble ouvert (celui avec la plus petite f la fonction - la fonction f est la somme du coût de l'algorithme, on sait déjà qu'il faut pour obtenir le noeud (g) et l'algorithme d'estimation de combien il en coûtera pour obtenir à partir du nœud de l'objectif (h, l'heuristique).

    http://en.wikipedia.org/wiki/A*_search_algorithm

    regarder le pseudo-code, comme vous pouvez le voir, l'ensemble ouvert est utilisé. Donc la ligne en bas - ce n'est pas que l'algorithme fonctionne en dupliquant\copie\déplacement des chemins ou des nœuds à partir d'une itération à l'autre - il tout simplement fait son travail sur le même ensemble de nœuds (bien sûr, les nœuds ne sont ajoutés et supprimés de la collection).

    Espère que cela aide...

    OriginalL'auteur