In English

Solution to the travelling salesman problem with space-filling curves.

Simon Hall ; Andreas Henriksson ; Hakim Khalafi
Göteborg : Chalmers tekniska högskola, 2012.
[Examensarbete för kandidatexamen]

I denna rapport har vi utforskat olika metoder som löser handelsresandeproblemet med hjälp av rumsfyllande kurvor. Vi har utgått från en klassisk algoritm av Bartholdi och Platzman och förbättrat den med avseende på lösningslängd med två egna algoritmer. Vi har under arbetets gång utvecklat programvara som använder dessa algoritmer. Vi har undersökt körningstid, lösningslängd och stabilitet för de olika algoritmerna och analyserat resultaten. Rapporten innehåller även en inledande teoretisk beskrivning av planfyllande kurvor och NP-komplexitet.



Publikationen registrerades 2012-06-05. Den ändrades senast 2012-06-13

CPL ID: 158566

Detta är en tjänst från Chalmers bibliotek