Discussion :

[khayyam90]

Bien le bonjour,

Mon interrogation du jour concerne ces 2 domaines : la résolution du problème du voyageur de commerce et la triangulation de Delaunay.

Peut-on dire de manière systématique que la solution optimale d'un problème du voyageur de commerce n'empreinte exclusivement que des arrêtes de la triangulation de Delaunay du graphe complet sous-jacent ?

Quelqu'un a-t-il un contre-exemple ?
Quelqu'un a-t-il des idées sur ce sujet ?

Une réponse positive à cette question aurait déjà l'avantage de fortement réduire la complexité de la recherche exhaustive.

[Nemerle]

L'arbre couvrant minimal peut en effet être utilisé pour obtenir en O(n^3) une approximation ... mais malheureusement le problème reste NP-complet

[khayyam90]

Quelle est l'approximation en O(n^3) dont tu parles ? tu as un lien ?

[Nemerle]

nan, j'ai plus, j'ai fait çà y a X années. Suis débordé ce mois-ci, mais tu devrais pouvoir trouver ça sur google...

[khayyam90]

Ok, cette approximation consiste à définir la solution approchée du TSP comme étant un parcours de l'arbre couvrant minimal, lui-même inclus dans la triangulation de Delaunay.

Mais ceci ne répond pas à la question de savoir si la solution optimale est nécessairement inclue dans la triangulation de Delaunay ou pas.

[pseudocode]

Mais ceci ne répond pas à la question de savoir si la solution optimale est nécessairement inclue dans la triangulation de Delaunay ou pas.

Non. Typiquement dans le cas où des points du "contour" sont alignés, ca peut facilement poser problème. Mais ce ne sont pas les seuls cas.

Par exemple avec des angles très fermés:

[Nemerle]

Mais ceci ne répond pas à la question de savoir si la solution optimale est nécessairement inclue dans la triangulation de Delaunay ou pas.

oui-oui, j'ai mis "une approximation" dans mon post!

Et l'exemple de Pseudocode est excellent...