Algorithme A Star

Hello,

Bon tout d'abord une remarque sur le petit tutorial sur l'Algo A*

"
Voilà, vous savez comment fonctionne l'algorithme A*. Il ne donne pas toujours la meilleure solution mais il en donne une bonne. On pourrait comparer ses performances avec celles de l'algorithme de Dijkstra. Dijkstra donne la meilleure solution, mais A* est plus rapide.
"

Ah bon, A* ne donne pas la meilleure solution ? Il me semble que malgré que ce soit une heuristique elle donne toujours la meilleure solution, exactement comme Dijkstra (Contre exemple si vous pensez que j'ai tort...). Je pense que l'intérêt de Dijkstra est ailleurs (buts multiples...)

"
Utilisez une structure de liste triée pour repérer rapidement le meilleur noeud
"

J'aurais aimé en savoir plus sur cette structure de liste triée.

En fait je ne comprends pas vraiment pourquoi on utilise un tas pour chercher le noeud de cout miminum, ça revient à faire une opération en 0(log n) alors qu'on peut vraissemblablement la faire en O(1)... (Faut vraiment que je le code cet algo, mais je ne pense pas me tromper vu que j'ai déjà implémenté Dijkstra...)

J'ai lu cet article :
http://www.gamasutra.com/features/20...pinter_pfv.htm
Je ne comprends pas trop le paragraphe A faster implementation of A*
Quelle utilité de placer le point central [30,30] ?
Quelle structure de données utilise t'il pour coder l'Open List ?

Et je recherche aussi cet article
"Real-Time Pathfinding for Multiple Objects" by Swen Vincke (June 1997).
Plein d'articles qui le citent, mais impossible de le trouver...

Merci pour vos contributions....

Citation:

---

Envoyé par Rumpel

Ah bon, A* ne donne pas la meilleure solution ?

---

Ca dépend si tu t'arrête à la première solution ou pas. A* est fait pour trouver rapidement une bonne solution, si tu cherche LA meilleure, il faut continuer jusqu'au bout.

Citation:

---

Envoyé par Rumpel

En fait je ne comprends pas vraiment pourquoi on utilise un tas pour chercher le noeud de cout miminum, ça revient à faire une opération en 0(log n) alors qu'on peut vraissemblablement la faire en O(1)

---

Quelque soit la structure triée, l'insertion se fera en O(log n) et l'accès au meilleur élément en O(1).

Citation:

---

Envoyé par Rumpel

J'ai lu cet article :
http://www.gamasutra.com/features/20...pinter_pfv.htm
Je ne comprends pas trop le paragraphe A faster implementation of A*
Quelle utilité de placer le point central [30,30] ?
Quelle structure de données utilise t'il pour coder l'Open List ?

---

Je ne suis pas sûr d'avoir compris non plus, j'ai l'impression que leur structure ressemble à une table de hachage.

Citation:

---

Envoyé par Rumpel

Et je recherche aussi cet article
"Real-Time Pathfinding for Multiple Objects" by Swen Vincke (June 1997).
Plein d'articles qui le citent, mais impossible de le trouver...

---

En effet, il n'a pas l'air d'être disponible sur le web.

Citation:

---

Envoyé par Sylvain Togni

Ca dépend si tu t'arrêtes à la première solution ou pas. A* est fait pour trouver rapidement une bonne solution, si tu cherche LA meilleure, il faut continuer jusqu'au bout.

---

C'est ce que je pensais au début, mais si tu le codes normalement, avec la distance de Manhattan, et si tu finis quand le but est dans la Closed List (Attention si on finit quand le but est dans l'Open List, ça ne marche pas tout le temps...), et bien A* devrait toujours te donner LA meilleure solution et pas seulement une bonne. Si tu n'es pas convaincu essaye de chercher un contre exemple...

Citation:

---

Envoyé par Sylvain Togni

Quelque soit la structure triée, l'insertion se fera en O(log n) et l'accès au meilleur élément en O(1).

---

Et bien et si on procède avec une structure de donnée de mon invention :
Un tableau de vector (Et pas un vector de vector)
Chacun devant être au moins égal à au moins 10 fois la longueur du chemin entre les 2 points.
Bon d'accord ça consomme plein de mémoire et il faut prendre large parce qu'on ne connait pas la longueur du chemin à priori...

Alors si on reprend l'exemple http://www.policyalmanac.org/games/aStarTutorial.htm
A la 1ère itération, l'algo normal met dans l'Open List les sommets qui correspondent aux F suivants : 40 54 60 74 60 74 60 54
Et la on choisit le F le plus faible : 40.
Bon si l'Open List est un arbre binaire ou une autre structure du genre, alors la recherche se fait en O(log n). (C'est ça ?)

Moi ce que je proposerais c'est dans le tableau de vector TAB, on fait
TAB[40].push(la case)
TAB[54].push(...)
TAB[60].push(...)
etc ... Tout en O(1)

Bon après
Soit il faut gérer la liste chainée : 40 -> 54 -> 60 -> 74 et effectivement faire des insertions en O(log n)
Ou alors ne pas la gérer et ça revient à scaner toutes les cases de TAB. Effectivement c'est un O(n) qui risque de revenir plus cher que le O(n log n) pour n petit...

Sinon en ce qui concerne mon implémentation de Dijkstra, j'avais utilisé un quadrillage hexagonale. Bon, il y a de gros avantages avec le quadrillage hexagonale, la structure de données est bien plus facile à coder et plus rapide (pas besoin de tout multiplier par 10). Pas besoin non plus de "lisser" le chemin trouvé par Dijkstra. Mais bon après pour placer des structures sur le quadrillage hexagonale, c'est peut être un peu moins pratique...

Bien le bonjour,

Citation:

---

Envoyé par Rumpel

Ah bon, A* ne donne pas la meilleure solution ? Il me semble que malgré que ce soit une heuristique elle donne toujours la meilleure solution, exactement comme Dijkstra (Contre exemple si vous pensez que j'ai tort...). Je pense que l'intérêt de Dijkstra est ailleurs (buts multiples...)

---

A* donnera la solution optimale dans le cas de l'utilisation d'une heuristique minorant la distance réelle. Sinon A* sortira une solution pas trop mauvaise. Exemple : dans le tuto, le contournement du cercle n'est pas optimal (j'avais sûrement utilisé la distance de Manhattan) : avant le cercle et après le cercle, on peut aller en ligne droite (je ne parle pas de la résolution de l'image, on voit bien que le chemin proposé n'est pas la ligne droite même à cette faible résolution).

Citation:

---

J'aurais aimé en savoir plus sur cette structure de liste triée.

---

En fait, une simple liste où le meilleur élément serait en tête histoire d'avoir un accès en O(1)