Den handelsrejsendes problem og de rumopfyldende kurver
Foredrag, HCØ dage, 18.10.1999
Søren Eilers
Matematisk Afdeling
Institut for Matematiske Fag
Københavns Universitet

Optimeret til læsning med stor skrift, fx 24" Helvetica


Et af de allermest udfordrende problemer i teorien bag effektive computerprogrammer er den handelsrejsendes problem: Hvis man skal besøge et vist antal steder på en rundrejse, hvordan tilrettelægger man så sin rute så rejsen bliver så kort som muligt?

Teoretisk set kunne man lade en computer prøve alle mulighederne, men det kræver et så astronomisk antal beregninger, at denne løsning ikke - selv med de allerhurtigste computere - kan benyttes i praksis. Dette gør sig allerede gældende for mere fundamentale problemer som sortering, og den store matematisk/datalogiske teori om at skrive effektive programmer har for længe siden resulteret i gode sorteringsprogammer, der i dag findes på alle verdens harddiske et sted. Men på trods af årtiers arbejde har forsøgene på at finde effektive programmer til at løse den handelsrejsendes problem kun i begrænset omfang båret frugt.

Man tyr derfor ofte til at bestemme "ganske gode" ruter i stedet for at insistere på at få den bedst mulige. En interessant metode er at forsøge at reducere den handelsrejsendes problem til et sorteringsproblem ved at følge en passende valgt matematisk kurve. For at metoden giver gode resultater skal kurven imidlertid vælges med omhu, og på forbløffende vis kommer en 100 år gammel matematisk teori om rumopfyldende kurver til assistance her.

Der lægges i foredraget vægt på at illustrere de omtalte problemer og kurver grafisk ved hjælp af computeranimationer.