[quote]Bonjour à tous,
Je me suis posé cette question récemment :
étant donné un graphe connexe G et deux de ses noeuds (disons A et B avec A différent de B), peut-on trouver un algo (non naïf...) qui détermine le "meilleur" chemin entre A et B ?
Je m'explique : on suppose que tous les noeuds du graphe sont "notés" (de 1 à 10 par exemple) et que l'on définit la "qualité" d'un chemin comme étant la moyenne arithmétique des "notes" des noeuds de G qui composent ce chemin.
Le meilleur chemin entre deux noeuds est celui de "moyenne" maximale.
Des recommandations ? Des Pistes ? Des idées de problèmes/thèmes liés à celui-ci ?
Merci bcp pour votre aide
[/quote]
Bonjour,
Sauf erreur, ce problème est NP-difficile (et donc, il n'y a guère d'espoir de trouver un algorithme polynomial). En effet, si il y avait un algorithme polynomial pour ton problème, il y en aurait aussi un pour trouver un chemin Hamiltonien (qui visite tous les sommets) dans un graphe, ce qui est faux (https://fr.wikipedia.org/wiki/Graphe_hamiltonien).
Preuve: soit G un graphe à n sommets dans lequel on veut savoir si il y a un chemin Hamiltonien entre A et B. On peut mettre une note de 0 sur A et 1 à tous les autres sommets. Ainsi, plus un chemin entre A et B est long, plus sa note moyenne sera grande. Ainsi G a un chemin Hamiltonien ssi le meilleur chemin entre A et B est de moyenne (n-1)/n (un chemin avec un 0 et (n-1) 1).
Si c'est cette idée de "poids moyen min/max" qui t'intéresse, Il y a un algorithme polynomial pour calculer un cycle de poids moyen minimum dans un graphe orienté (http://www.sciencedirect.com/science/article/pii/0012365X78900110 - c'est un peu compliqué), qui est utilisé dans l'algorithme min cost max flot.
