Solution to the travelling salesman problem with space-filling curves.
Ladda ner
Typ
Examensarbete för kandidatexamen
Bachelor Thesis
Bachelor Thesis
Program
Publicerad
2012
Författare
Hall, Simon
Henriksson, Andreas
Khalafi, Hakim
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Grundläggande vetenskaper , Annan matematik , Basic Sciences , Other Mathematics