Variant op korste route algoritme

[Xenion]

De dataset leent zich uitstekend om door een graaf weergegeven te worden.

Er zijn geen paden opgelegd tussen de punten. Je kan van elk punt naar elk punt. Lijkt me niet nodig om dat nog expliciet te gaan definiëren in edges. Uiteindelijk is de oplossing slechts een lijst van punten.

Dit zou betekenen dat de laatste stap van het optimale pad nooit de grootste stap kan zijn, Dat is onzin.

Dat klopt, dat had ik over het hoofd gezien.

Ik denk dat er inderdaad niks anders opzit dan alle mogelijke paden effectief te genereren en controleren, ik probeerde dat gewoon op een systematische manier te doen.

Misschien:

1) genereer een random oplossing (permutatie van de punten) en houd de maximale afstand tussen 2 punten bij, noem die M

2) herhaal stap 1 een paar keer en kies daar de beste M uit

3) begin alle mogelijke paden te genereren, maar breek een tak af als die de maximale afstand daar M overschrijdt.

4) zoek in alle paden die je gegenereerd hebt het beste

[EvilBro]

Er zijn geen paden opgelegd tussen de punten.

Dat neemt niet weg dat de data wel gewoon als graaf gezien kan worden.