opgave hjælp!

Uden at sige for meget, så handler det vel om at bruge en Graph

Ligner da en simpel O(n^2) heuristik for TSP?

Du har en permutation P af byer, der repræsenterer en rute og en mængde V af ikke besøgte byer?

Udvælg en startby f.eks. by 1.
Lav en while løkke til punkt 2. Slut kriteriet er når V er tom. Ellers skal du bare for hver iteration vælge den by i V som minimerer c(i;j;k)...

Du skal selvfølgelig nok også opdatere startbyen, med den nyligt valgte by fra V i hver iteration :?

Eller nej .. .det er vist ikke nødvendigt. Mon ikke jeg bare skulle gå i seng :s

Efter at have sovet på det er jeg kommet til at tænke på at algoritmen jo nok kører i tid O(n^3) i stedet. Så for at gøre det kort:

Input V - mængde af byer som ikke er besøgt
Output P - en permutation af byerne V

1) Flyt n fra V til P. Dette er start byen.
2) Hvis V er tom returner P.
3) For hver kant (i, k) fra P og for hver knude j fra V vælg det sæt der minimerer c(i; j; k).
4) Fjern det valgte j fra V og indsæt det mellem i og k, i P
5) Gentag fra punkt 2

I hvert gennemløb flyttes én by. Der tager tid O(n). Derudover ses på alle kanter i P og byer i V. Hvis der er x kanter i P er der n-x byer i V hvorfor dette skridt tager tid x*(n-x) = O(n^2). Hele algoritmen tager så tid O(n^3).