Fabien LE LEZ wrote:

Bonjour,

J'ai quelques milliers d'éléments, numérotés de 1 à N, et, pour chaque
couple d'éléments, la distance entre les deux éléments. (En fait, il s'agit de points dans un espace vectoriel à 63
dimensions, et de la distance euclidienne associée.)

J'aimerais ordonner ces éléments, de telle sorte que les éléments
proches dans l'espace de départ, se retrouvent proches dans la liste
d'arrivée.

Existe-t-il un algorithme permettant d'obtenir, sinon la meilleure
solution, du moins une solution proche de l'optimal ?

Demander a un voyageur de commerce de les visiter, et noter
son itineraire ?

Plus serieusement, il me semble que les structures de donnees
utilisees dans les algorithmes de plus proches voisins remplissent
justement ce genre de conditions, mais je crois qu'elles se
generalisent mal aux grandes dimensions.

Et quid de l'algorithme naif :
Je prends la distance minimale, je groupe les deux points,
puis j'itere en prenant le point le plus eloigne du dernier
point traite, et en lui ajoutant (ou a son groupe) son plus
proche voisin non encore dans le groupe.