WisFaq!

Afstandmatrix - Korste afstand tussen de vectoren

Hallo,

Ik heb een 5x5 afstandsmatrix.. Deze matrix geeft de afstanden weer tussen de 5 punten, die drie dimensionaal zijn (x,y,z-coordinaten).. Nu wil ik graag berekenen wat de korste route is die ik kan nemen als ik alle punten wil bezoeken en weer terug wil keren bij het begin!

Bedankt voor de aandacht, mvg

JMP
30-6-2004

Antwoord

dag JMP

Dit probleem is ook bekend als het handelsreizigersprobleem.
Het heeft te maken met het vinden van een Hamiltoncykel in een graaf, als dat je wat zegt.
Een lastig probleem!
Voor een 5 bij 5 matrix is het nog wel te doen.
Ken je het begrip permutatiematrix?
Dat is een matrix met alleen nullen en enen, en wel precies één 1 in elke rij èn precies één 1 in elke kolom.
Voorbeeld:

Deze permutatiematrix hoort bij een cykel:
van A naar B naar E naar D naar C naar A.
Let op: niet elke permutatiematrix hoort automatisch bij een cykel! Je kunt ook twee of meer 'deelcykels' krijgen.
Je kunt nu alle 5 bij 5 permutatiematrices opstellen die wel corresponderen met een cykel. Deze permutatiematrices leg je als het ware over de oorspronkelijke matrix heen, en je telt de getallen onder de enen bij elkaar op.
De permutatiematrix waarbij deze som de kleinste waarde heeft, geeft de gezochte cykel.
Een heel gedoe, maar het is niet moeilijk te programmeren.
Ik hoop dat dit je verder helpt.
groet,

Anneke
1-7-2004