Est la gourmande meilleur premier algorithme de recherche différente de la première algorithme de recherche?

Est le gourmand meilleur premier algorithme de recherche différente de la première algorithme de recherche?

La page wiki a un paragraphe distinct sur Gourmand BFS mais c'est un peu moins clair.

Ma compréhension est que la Goulue BFS est juste BFS où le "nœud meilleur de l'ouverture" dans la page wikipedia de l'algorithme est une fonction heuristique on calcule pour un nœud. Donc, la mise en œuvre de cette:

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
   a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
   b. Otherwise: change recorded parent if this new path is better than previous one.
done

avec "le meilleur nœud d'OUVRIR un" heuristique de la fonction de l'estimation de la proximité du nœud est de l'objectif, est en fait Gourmand BFS. Suis-je le droit?

EDIT: Commentaire sur Anonymouse réponse:

Donc, essentiellement, une gourmande BFS n'a pas besoin d'une "liste OUVERTE" et doit fonder ses décisions que sur le nœud actuel? Est cet algorithme GBFS:

1. Set START as CURRENT node
2. Add CURRENT to Path [and optinally, to CLOSED?]
3. If CURRENT is GOAL, exit
4. Evaluate CURRENT's successors
5. Set BEST successor as CURRENT and go to 2.
InformationsquelleAutor Alex | 2011-12-04
  1. 26

    "Meilleur d'abord" pourrait permettre de la révision de la décision, alors que, dans un algorithme glouton, les décisions devraient être définitifs, et elle n'est pas modifiée.

    Par exemple, A*-la recherche est une des meilleures de la première recherche, mais il n'est pas gourmand.

    Notez, toutefois, que ces termes ne sont pas toujours utilisés avec les mêmes définitions. "Gourmand" signifie habituellement que la décision n'est jamais révisé, finalement, d'accepter des solutions sous optimales à l'avantage des améliorations dans la gestion du temps. Cependant, je parie que vous trouverez des situations où les "gourmands" est utilisé pour la combinaison de la "meilleure première + parcours en profondeur d'abord", comme dans "essayez de développer la meilleure étape suivante jusqu'à ce que nous nous heurtons à une impasse, puis revenir à l'étape précédente et continuer avec le prochain meilleur" (que j'appellerais une "priorité de la profondeur d'abord").

    Aussi, cela dépend du niveau d'abstraction dont vous parlez. A* n'est pas gourmand en la construction d'un chemin". C'est bien avec la tenue d'un grand ensemble d'ouvrir des chemins autour de. Cependant, il est gourmand en "l'élargissement de l'espace de recherche" vers le vrai chemin le plus court.

    InformationsquelleAutor Anony-Mousse
  2. 2

    BFS est une instance de l'arbre de recherche et graph search algorithmes dans lequel un nœud est sélectionné pour l'expansion basée sur la fonction d'évaluation f(n) = g(n) + h(n), où g(n) est la longueur du chemin de la racine à n et h(n) est une estimation de la longueur du chemin de n à l'objectif de nœud. Dans un algorithme BFS, le nœud ayant le plus faible de l'évaluation (c'est à dire plus bas f(n)) est sélectionné pour l'expansion.

    Gourmand BFS suit la fonction d'évaluation f(n) = h(n), qui est juste la fonction heuristique h(n), qui estime que la proximité de n à l'objectif. Par conséquent, gourmand BFS essaye de développer le nœud qui est pensé pour être plus proche de l'objectif, sans prendre en compte précédemment réunis des connaissances (c'est à dire g(n)).

    Pour résumer, la principale différence entre ces (même) les méthodes de recherche de la fonction d'évaluation.

    Comme une note de côté, l'algorithme A* est un premier algorithme de recherche dans lequel l'heuristique de la fonction h est recevable heuristique (c'est à dire h est toujours une sous-estimation de l'heuristique parfait la fonction h*, pour tous les n). A* n'est pas un gredy algorithme BFS parce que sa fonction d'évaluation est f(n) = g(n) + h(n).

    InformationsquelleAutor Hina Alvi
  3. 0

    Comme je le comprends, "best-first search" est seulement un nom collectif d'une technique de recherche qui vous permet d'utiliser une heuristique d'évaluation de la fonction h(n).
    Donc, A* et avide de mieux d'abord de recherche sont des algorithmes qui tombent dans cette catégorie.

    InformationsquelleAutor Dominik Antal