Tri des données et liaisons entre elles - Page 1

Bonjour à tous. Ça faisait bien longtemps que je n'étais pas venu poster un message sur un des forums.
En tous cas je vois qu'il y a toujours autant d'activité et que les "anciens" sont toujours présents!

Je vous expose mon problème. J'ai repris mon projet d'implémentation de l'algorithme A* (recherche de chemins) et je cherche à l'optimiser.
Le bilan fourni par l'outil Callgrind après une recherche me précise que la majorité du temps utilisé pour le calcul d'un chemin consiste en la recherche du meilleur nœud. Cette fonction est appelée tant que le chemin n'est pas trouvé et tant qu'il reste des nœuds à explorer ; autrement dit c'est une des fonctions les plus sollicitées.

Mes nœuds sont une structure :

typedef struct
{
	size_t parent;
	size_t object;
	long double F;
	long double G;
	long double H;
	bool isClosed;
} NODE;

Ces nœuds sont enregistrés dans une liste dynamique : NODE** nodesList
* parent correspond au parent du nœud consulté. Seul le premier nœud n'a pas de parent. Cette information permet de récupérer le chemin complet (en remontant les parents du dernier nœud jusqu'au le premier). Par exemple, pour connaître le parent du nœud X, il faut simplement faire nodesList[X]->parent
* object est la référence du nœud sur la carte où est effectuée la recherche de chemin.
* F, G et H sont les valeurs de l'heuristique. F = G + H (où G est la distance entre le nœud courant et son parent; H est la distance entre le nœud courant et l'arrivée).
* si isClosed vaut false alors ce nœud a déjà été consulté lors de la recherche.


Cette façon de stocker les nœuds n'est pas géniale :
* je ne peux pas trier sinon les valeurs de parent n'ont plus de sens
* les nœuds consultées sont dans la même liste que ceux qui ne le sont pas

Comment faire pour
* stocker efficacement les NODE?
* les trier tout en gardant les références vers le parent de chacun d'entre eux?
* trouver le meilleur nœud de la liste rapidement (celui ayant le F le plus petit)?

Merci pour votre aide.
Je tiens le code source à dispo pour ceux que ça intéresse (sous licence Gnu/GPLv3)

pour la sélection du meilleur noeud, tu peux peut être utiliser une file de priorité (tas binaire, tas binomial, tas de Fibonacci, ...)
pour stocker tes noeuds lors du parcours

si je ne me trompe pas, le code de A* ressemble beaucoup à celui de Dijkstra,
tu peux peut être aller jeter un coup d'oeil au bouquin Introduction à l'algorithmique de Cormen, Leiserson, Rivest

A* et Dijkstra sont quasiment identiques. La différence vient de l'heuristique : F = G + H
Pour A*, G est la distance entre le point courant et l'arrivée, H la distance entre le point courant et son parent.
Pour Dijkstra, G vaut toujours 0.

Les essais que j'ai fait montrent que Dijkstra trouve toujours le chemin le plus court contrairement à A*.
Par contre A* est plus rapide dans la majorité des cas puisque que son heuristique l'oriente vers l'arrivée tandis qu'avec Dijkstra chaque nœud est étudié.

J'ai finalement opté pour la fonction de tri de la STL. J'ai fais un "pseudo" tri par insertion mais ça n'était pas concluant.
Ça me convient pour le moment ; ça règle mais deux problèmes :
- je ne garde pas un pointeur comme référence, ni un size_t mais un iterator qui ne change pas après les tris successifs.
- le meilleur nœud est toujours situé en début de liste, ça évite une recherche coûteuse en temps.

Spomky (./3) :
Les essais que j'ai fait montrent que Dijkstra trouve toujours le chemin le plus court contrairement à A*

indépendamment de tes tests, c'est aussi :
- ce que ma prof d'algo de l'époque m'avait appris (différence entre algo de théorie des graphes, et algo d'intelligence artificielle)
- ce que j'ai toujours entendu dire
- ce que j'ai constaté (à l'époque, j'avais codé une sorte de jeu de stratégie militaire comme projet d'année, avec un collègue, et j'avais implémenté les deux algos pour comparer)

Au niveau de la rapidité (à remettre dans le contexte) :
- A* était toujours plus rapide pour des cours chemins (ie, simples)
- Dijkstra était souvent plus rapide pour des longs chemins (ie, complexes)
Après, moins l'heuristique était bon, plus A* était rapide... mais plus les chemins étaient mauvais ^^

Bah euh, c'est normal, Dijkstra c'est un algorithme qui calcule exactement les plus courts chemins dans un graphe sans poids négatif.
Alors que A* n'est qu'une méthode approchée pour résoudre ce problème

Je me permets d'apporter une précision 2 ans après, pour ceux qui tomberaient sur ce topic et seraient mis dans l'erreur. A la base, tel qu'il a été conçu, A* n'est pas une méthode approchée.

Si l'heuristique est optimiste (elle ne surestime jamais la somme du poids des arcs menant aux sommets finaux) et exacte pour les arcs finaux (sur les prédécesseurs des sommets finaux, elle renvoie le poids de l'arc prédécesseur-final), alors A* est exact (optimal). Il élague la recherche d'autant plus que l'heuristique est de qualité (proche de la vérité). Bien sûr, il y a un compromis à trouver entre l'intensité de l'élagage (gain de temps) et la qualité de l'estimation de l'heuristique (qui prend du temps).

Si l'heuristique n'est pas optimiste (il lui arrive de surestimer la somme du poids des arcs menant aux sommets finaux) ou inexacte pour les arcs finaux, A* est lui-même une heuristique. C'est souvent le cas