Solution to the travelling salesman problem with space-filling curves.
Ladda ner
Publicerad
Författare
Typ
Examensarbete för kandidatexamen
Bachelor Thesis
Bachelor Thesis
Program
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