Algoritme voor "beste permutatie"

[robbert]

Bij het schrijven van een programma kom ik het volgende probleem tegen: gegeven een lijstje l = x[1], x[2], ..., x[n] met elementen van type A en een afstandsfunctie f : A * A -> Int, zoek een permutatie p1, p2, ..., pn zodat f(x[p1], x[p2]) + f(x[p2], x[p3]) + ... + f(x[pn-1], x[pn]) minimaal is.

De kortzichtige manier is: probeer alle permutatie van l en zoek de gene met het minimale resultaat. Maar een lijst van lengte n, heeft n! permutaties, dus dit blaast ontzettend op. Nu zat ik te denken of ik beters kan bedenken, bijvoorbeeld het beste resultaat bijhouden en op het moment de prefix van de te proberen permutatie al een slechter resultaat oplevert, stoppen.

Echter, bij nader inzien, lijkt dit een daarmate standaard probleem dat iemand hier wel een algoritme voor moet hebben bedacht, en het idioot zou zijn het wiel opnieuw uit te vinden? Iemand een idee wat de naam van dit probleem is?

[ Voor 5% gewijzigd door robbert op 22-01-2011 18:11 ]

[doskabouter]

Volgens mij kan je dit ook zien als het plannen van de kortste route, en daarvoor is een standaard dijkstra algoritme wel geschikt.

[RayNbow]

Dit is een variant op TSP waarbij je niet hoeft terug te keren naar het startpunt.

Addendum:
Hier staat uitgelegd hoe je er een instantie van TSP kunt maken.

[ Voor 39% gewijzigd door RayNbow op 22-01-2011 18:34 ]

[robbert]

doskabouter schreef op zaterdag 22 januari 2011 @ 18:20:
Volgens mij kan je dit ook zien als het plannen van de kortste route, en daarvoor is een standaard dijkstra algoritme wel geschikt.

Bij het shortest path probleem hoeft je niet langs alle locaties.

RayNbow schreef op zaterdag 22 januari 2011 @ 18:32:
Dit is een variant op TSP waarbij je niet hoeft terug te keren naar het startpunt.

Addendum:
Hier staat uitgelegd hoe je er een instantie van TSP kunt maken.

Mijn dank is groot!