Avatar billede flatron Nybegynder
03. juni 2009 - 11:00 Der er 3 kommentarer

Travelling saelsman problem

Hej Experter!

Jeg har ledt på internettet efter et lille program der kan give mig den korteste rute mellem nogle koordinater, uden held.

Jeg har en liste af koordinater med en attribut:

x120 y275 n-200
x204 y508 n-200
x304 y124 n-100
x520 y575 n-200
x304 y308 n-100
.
.
.
Det jeg søger er ud fra et givet START-punkt og et givet SLUT-punkt at få den korteste vej.

Der kan være mere end 1500 punkter der skal besøges. Er der nogen forslag eller er der nogen der har et bedre bud på i hvilken kategori dette spm høre hjemme?

Hilsen Arneen
Avatar billede mcb2001 Nybegynder
03. juni 2009 - 13:23 #1
travelling salesman er et datalogisk mareridt...

Men så vidt jeg kan se, skal du ud og lede efter algoritmer der løser travelling salesman problematikken, og så selv skrive dig et program :-)
Avatar billede flatron Nybegynder
03. juni 2009 - 15:20 #2
Jeg har ikke kunne finde nogle gode algoritmer. :-(

Arneen
Avatar billede mcb2001 Nybegynder
03. juni 2009 - 15:29 #3
har du læst eksempelvis:
http://en.wikipedia.org/wiki/Travelling_salesman_problem
?????

Der er masser af henvisninger til algoritmer og endnu flere forklaringer på hvorfor dette ikke kan løses nemt. Der er sågar en henvisning til et program der kan finde ruter...
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester