Discuter:Algorithme A*

Un article de Wikipédia, l'encyclopédie libre.

	Algorithme A* fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
B	Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. (Voir les statistiques)
Faible	Cet article a été classé comme d'Importance faible selon le Tableau d'évaluation du projet. (Contester?)

Dans ce rapprochant le plus de la destination, ne l'atteignant pas forcément, ce qui peut coûter beaucoup de temps de calcul. obscur ?

merci... c'est reformulé ~ þaצo ♫ 16 jun 2005 à 12:53 (CEST)

Je sais pas s'il existe un article sur la planification au sens de l'IA. Il serait bien que l'article A* pointe vers ce dernier, en expliquant que cet algorithme est un algorithme de planification.. Pfv2 2 octobre 2005 à 17:19 (CEST)

heu qu'entant tu par planification ? je ne connai pas cette notion. ~ þayo ♫^♪♫♪ 2 octobre 2005 à 17:59 (CEST)

Je trouve cette idée redondant et bien moins précise que "recherche de chemin", une recherche de chemin implique que c'est un algorithme de planification d'un déplacement prochain (si je comprend bien ce principe de planification). ~ þayo ♫^♪♫♪ 2 octobre 2005 à 18:28 (CEST)

Je parle de la discipline "AI planning" (Planification en intelligence artificielle). Le problème classique de planification en IA est de trouver un suite d'actions dans un espace d'états pour à partir d'un état initial arriver à un état final. L'algorithme A* est un algorithme pour ce type de problème, habituellement donné comme exemple dans les cours d'introduction à l'intelligence artificielle. Toutefois, il n'est pas très efficace. Il existe des algorithmes beaucoup plus efficace que A*, tel que GRAHPLAN. Il y a aussi d'autres algorithmes très efficaces tel que TLPLAN (qui prend en entrée des descriptions en logique temporelle pour éliminer des chemins) et SHOP (basé sur une description hiérarchiques des actions). À part le problème classique de planification, il y a la planification non déterministe (c'est-à-dire que les actions peuvent ne pas mener à l'état prévu selon une certaine probabilité, qu'on n'est pas certain de connaître l'état actuel, etc.), la planification de trajectoire (par exemple pour des bras de robots), la planification en tenant compte du temps, d'un coût pour chaque action, etc. C'est un domaine très vaste, qui peut faire appel à des notions comme les chaînes de markov, etc. En français, on appelle un planificateur un logiciel basé qui permet de trouver un plan(AI planner). En somme, je pense qu'il devrait y avoir une page sur la planification. Je n'ai pas cru en voir une jusqu'à présent.Pfv2 4 octobre 2005 à 19:41 (CEST) Dans wikipédia anglais, il y a une page, quoique peu élaborée sur le AI planning, ou automated planning[1] Pfv2

Pour se qui est de la partie "efficacé", cela dépendant de se que l'on entand par la. Il y a toujour le même compromis entre vitesse et memoire. L'efficasité est donc toujour toute relative. Pour le reste comme ca me dépasse je te laisse juger :D toutefois "la recherche de chemin" me semble être un sous ensemble de se que tu appel "panification" ~ þayo ♫^♪♫♪ 4 octobre 2005 à 21:41 (CEST)

Question d'efficacité, je peux te garantir que GRAPHPLAN est énormément plus rapide que A* et cela en utilisant une quantité de mémoire beaucoup plus petite. A* est un algorithme naif, dans le sens où c'est un exellent exemple pédagogique; il est simple, mais pas très efficace en mémoire ou en temps. Oui, l'idée de base de la planification en IA est de chercher un chemin, quoiqu'il y a plusieurs variantes (avec nondéterminisme des actions, qui ne trouve pas toujours le chemin le plus court, etc., comme je l'ai expliqué plus haut). Toutefois, j'ai jamais vu "recherche par chemin" sur le site d'un chercheur, ou comme titre d'un livre, ou d'une conférence scientifique. Le terme usuel pour désigner ce champs de recherche s'appelle "planification" (AI planning). Desfois dans la littérature en anglais, on voit aussi "state space search" (exploration d'un espace-états). En tout cas, je vais essayer de débuter une page sur le sujet Planification_en_intelligence_artificielle Et on pourrait faire un lien vers A* etc. Pfv2 5 octobre 2005 à 02:27 (CEST)