Quelles sont les différences entre A * et la recherche gourmande au mieux?

Les deux algorithmes entrent dans la catégorie « meilleure première recherche » les algorithmes, qui sont des algorithmes qui peuvent utiliser à la fois les connaissances acquises jusquà présent lors de lexploration de lespace de recherche, noté $ g (n) $ , et une fonction heuristique, désignée par $ h (n) $ , qui estime la distance au nœud de but, pour chaque nœud $ n $ dans lespace de recherche (souvent représenté sous forme de graphique).

Chacun de ces algorithmes de recherche définit une « fonction dévaluation », pour chaque nœud $ n $ dans le graphe (ou espace de recherche), désigné par $ f (n) $ . Cette fonction dévaluation permet de déterminer quel nœud, lors de la recherche, est « développé » en premier, cest-à-dire quel nœud est dabord supprimé de la « frange » (ou « frontière », ou « border ») , afin de « visiter » ses enfants. En général, la différence entre les algorithmes de la catégorie « best-first » réside dans la définition de la fonction dévaluation $ f (n) $ .

Dans le cas de lalgorithme BFS gourmand , la fonction dévaluation est $ f (n) = h (n) $ , cest-à-dire que lalgorithme BFS gourmand étend dabord le nœud dont la distance estimée au but est la plus petite. Ainsi, BFS gourmand nutilise pas les « connaissances passées », cest-à-dire $ g (n) $ . Doù sa connotation «gourmande». En général, lalgorithme gourmand BST est pas complet , cest-à-dire quil y a toujours le risque de prendre un chemin qui ne amener au but. Dans lalgorithme BFS gourmand, tous les nœuds sur la frontière (ou frange ou frontière) sont conservés en mémoire, et les nœuds qui ont déjà été développés nont pas besoin dêtre stockés en mémoire et peuvent donc être supprimés. En général, le BFS gourmand est également pas optimal , cest-à-dire que le chemin trouvé peut ne pas être le meilleur. En général, la complexité temporelle est $ \ mathcal {O} (b ^ m) $ , où $ b $ est le facteur de branchement (maximum) et $ m $ est la profondeur maximale de larbre de recherche. La complexité de lespace est proportionnelle au nombre de nœuds de la frange et à la longueur du chemin trouvé.

Dans le cas de le A * algorithme , la fonction dévaluation est $ f (n) = g (n) + h (n) $ , où $ h $ est une fonction heuristique admissible . Le « star », souvent désigné par un astérisque, *, fait référence au fait que A * utilise une fonction heuristique admissible, ce qui signifie essentiellement que A * est optimal , cest-à-dire quil trouve toujours le chemin optimal entre le nœud de départ et le nœud de but. A * est également complet (sauf sil y a une infinité de nœuds à explorer dans lespace de recherche). La complexité temporelle est $ \ mathcal {O} (b ^ m) $ . Cependant, A * doit garder tous les nœuds en mémoire pendant la recherche, pas seulement ceux de la frange, car A *, essentiellement, effectue une « recherche exhaustive » (qui est « informée », dans le sens où elle utilise une fonction heuristique ).

En résumé, le BFS gourmand nest pas complet, pas optimal, a une complexité temporelle de $ \ mathcal {O} (b ^ m) $ et une complexité spatiale qui peut être polynomiale. A * est complet, optimal, et sa complexité temporelle et spatiale est de $ \ mathcal {O} (b ^ m) $ . Donc, en général, A * utilise plus de mémoire que BFS gourmand. A * devient peu pratique lorsque lespace de recherche est énorme. Cependant, A * garantit également que le chemin trouvé entre le nœud de départ et le nœud de but est le meilleur et que lalgorithme se termine finalement. Greedy BFS, en revanche, utilise moins de mémoire, mais ne fournit pas les garanties doptimalité et dexhaustivité de A *. Donc, quel algorithme est le «meilleur» dépend du contexte, mais les deux sont les «meilleures» premières recherches.

Remarque: en pratique, vous ne pouvez utiliser aucun de ces algorithmes: vous pouvez par exemple utilisez plutôt IDA * .

Commentaires

• Les commentaires ne sont pas pour discussion prolongée; cette conversation a été déplacée vers le chat .

Daprès le livre Intelligence artificielle: A Modern Approach (3e édition), par Stuart Russel et Peter Norvig, en particulier, section 3.5.1 Meilleure recherche gourmande en premier (p. 92)

La recherche gourmande au mieux essaie détendre le nœud le plus proche de lobjectif, au motif que cela est susceptible de conduire à une solution rapidement. Ainsi, il évalue les nœuds en utilisant uniquement la fonction heuristique; cest-à-dire $ f (n) = h (n) $ .

Dans ce même section, les auteurs donnent un exemple qui montre que la recherche gourmande best-first nest ni optimale ni complète.

Dans la section 3.5.2 Une * recherche: En minimisant le coût total estimé de la solution du même livre (p. 93), il indique

A * la recherche évalue les nœuds en combinant $ g (n) $ , le coût pour atteindre le nœud, et $ h (n) $ , le coût pour aller du nœud à lobjectif $$ f (n) = g (n) + h (n). $$

Puisque $ g (n) $ donne le coût du chemin du nœud de départ au nœud $ n $ , et $ h (n) $ est le coût estimé du chemin le moins cher à partir de $ n $ à lobjectif, nous avons $ f (n) $ = coût estimé de la solution la moins chère via $ n $ .

Ainsi, si nous essayons de trouver la solution la moins chère, une chose raisonnable à essayer en premier est le nœud avec la valeur la plus basse de $ g (n) + h (n) $ . Il savère que cette stratégie est plus que raisonnable: à condition que la fonction heuristique $ h (n) $ satisfasse certaines conditions, la recherche A * est à la fois complète et optimale. Lalgorithme est identique à la recherche à coût uniforme, sauf que A * utilise $ g + h $ au lieu de $ g $

Ce que vous avez dit nest pas totalement faux, mais lalgorithme A * devient optimal et complet si la fonction heuristique h est admissible, ce qui signifie que cette fonction ne surestime jamais le coût pour atteindre lobjectif. Dans ce cas, lalgorithme A * est bien meilleur que lalgorithme de recherche gourmande.

Commentaires

• cher pouvez-vous élaborer votre réponse. Désolé de le dire mais je nai pas compris votre point.
• @IramShah – TemmanRafk parle de la preuve que A * est à la fois optimal et complet. Pour ce faire, il est montré en raison de linégalité triangulaire que lheuristique qui estime la distance restante jusquà lobjectif nest pas une surestimation. Pour voir une explication plus complète, voir fr.wikipedia.org/wiki/Admissible_heuri stic