Den handelsrejsendes problem

Tags: Bog Computere Mine tekster

Fornylig kom Påklistrede grene til salg. Og inden den var der Libellus. Men min første bog, på over 100 sider, var mit speciale. Og en moderne scanner har nu gjort det muligt, at gøre det tilgængelig for flere mennesker, som pdf. God læselyst.

(Specialet indeholder lidt blyant-skriblerier. Den trykte tekst er den samme, som det trykte speciale indeholdt, mens tilføjelserne i blyant blev gjort, da jeg opdagede, der stadig var stavefejl i den færdige tekst.)

Den handelsrejsendes problem: Teori og heuristikker.

Lise Møller, 11. august 1994.
Institut for Matematik og Datalogi.
Odense Universitet.

Et af de mest fascinerende graf-teori problemer er Den Handelsrejsendes Problem (Traveling Salesman Problem / TSP). Fascinerende for teoretiskere fordi en polynomiel algoritme til løsning af det generelle problem ville medføre polynomielle algoritmer for mange andre problemer. Og fascinerende fordi en sådan polynomiel algoritme efter over 50 år ikke er blevet fundet endnu, så man i praksi må give afkald på enten hurtighed (ved at anvende algoritmer med exponentiel køretid) eller på kvalitet (ved at anvende heuristikker, der giver sub-optimale løsninger). Så både i teori og praksis er der blevet foretaget megen forskning på området.

I dette speciale belyser jeg både teori og praksis med eksempler. Mit udgangspunkt er de specielle polynomielle algoritmer. Specielt har jeg taget mange algoritmer med, der kan finde gode eller optimale løsninger til specialtilfælde af TSP. To af de nyere heuristikker (simuleret udglødning og den genetiske algoritme) har jeg implementeret og testet, og sammenlignet med andre algoritmer (bl.a. MST-algoritmen).

Kapitel 1 ser først på TSP's historie og dets relation til andre nærtbeslægtede problemer, både praktiske og grafteoretiske. Da det er vigtigt at kunne vurdere en algoritme, der giver sub-optimale løsninger, gennemgås og demonstreres analysemetoder, bl.a. på algoritmer for specialtilfælde.

Kapitel 2 gennemgår en del algoritmer, der giver gode resultater, men enten ikke kan garantere optimalitet, eller kræver ret specielle forhold for problemet.

Kapitel 3 gennemgår kort historien for og teorien bag simuleret udglødning [simulated annealing], og viser så resultater af forskellige forsøg med algoritmen. Simuleret udglødning bygger på en teori, der i starten udelukkende blev brugt på størknende metaller og lignende. Først senere blev algoritmen også brugt på helt andre ting, og jeg viser både den generelle simulerede udglødning, og dens tilpasning til TSP.

I kapitel 4 ses den genetiske algoritme for TSP. Den genetiske algoritme bygger på, at hvis befolkninger kan producere bedre individer for hver generation, ved tilfældig avling, kan man måske også opbygge befolkninger af løsninger og så lade dem "avle" indbyrdes, forhåbentlig med gode løsninger til følge. Jeg viser kort den generelle genetiske algoritme, og så dens tilpasning til TSP. Herefter følger forsøg med algoritmen.

Skabt: 1. oktober, 2008 - Sidst ændret: 14. oktober, 2008 - Kommentarer (0)