Mr_Moot ( 3 janv. 2012) disait:
east bear disait:Le "problème du voyageur de commerce" ainsi que celui "du sac à dos" sont NP-complets !Ensuite ne t'occupe pas de Viamichelin, Mappy ou du GPS, c'est tout sauf optimisé.
pour le voyageur de commerce, la NP-complétude est liée au nombre ville à visiter. Ici, avec deux villes, on est sur un plus court chemin dont le compléxité est n² (plus précisément n*m ou m le nombre maximum de voisins d'un noeud). Et je vois pas vraiment le rapport avec le problème du sac à dos.
inscrit le 02/12/03
2499 messages