Hjælp til algoritme

Prøv denne søgning:
http://www.google.com/search?hl=en&lr=&ie=UTF-8&oe=UTF-8&safe=off&q=%22salesman+problem%22

Vil du finde den samlet set korteste rute hvis en bil skal besøge alle firmaerne og så vende tilbage til udgangspunktet? Man kan bevise, at der ikke findes nogen effektiv algoritme for dette, da det er et såkaldt NP-komplet problem som omtales som den meget kendte trading salesman problemstilling.

Men til at finde den korteste afstand mellem to punkter kan du f.eks. bruge A*-algoritmen. Jeg går dog ikke ud fra at det denne du søger.

http://en.wikipedia.org/wiki/A_Star_Search_Algorithm

Hvis du bare skal fra et sted til et andet, så kan du opstille problemet som en retningsbestemt graf og bruge Dijkstra's shortest path algoritme.

Ja det er "den samlet set korteste rute hvis en bil skal besøge alle firmaerne og så vende tilbage til udgangspunktet" jeg vil finde.
Hvis der ikke findes nogen effektiv algoritme for det, vil det så sige, at så kan man ligeså godt selv lave en algoritme, der gennemgår samtlige mulige kombinationer?

Du bevæger dig ind på grafteoriens enorme og komplicerede område. Der er masser af effektive algortimer til at løse TSP bare ikke nogen der er så effektive som det forventes at de kan blive (polynomial tid). Du kan derfor sagtens finde gode algoritmer til løsning af TSP. Held og lykke :)

Dit problem hedder "salesmans problem" (som allerede retry siger) det er et klassiskt problem i datalogi fordi det er lykkedes at bevise at der ikke findes nogen klar algoritmisk metode at finde den korteste rute.

For at være sikker på at finde den korteste må man beregne alle ruter og sammenligne. Med 4-10 kunder der skal besøges er det nemt nok, men med 2000-5000 bliver testeriet så omfattende at det er helt uantageligt (programmet vil tage flere år at køre).

Men der er forsket en del i det, og selv og man ikke kan finde DEN korteste, er der mange måder at finde en af de korter. så jeg vil også anbefale den der søgning.

mvh JakobA

Tak for hjælpen - jeg må vist til at læse lidt om forskellige algoritmer.
Kan jeg ikke få jer til at smide et svar, så må jeg dele pointene i mellem jer.

jakoba du siger at 4-10 kunder ikke er noget problem, men hvor langt skal man før det bliver for meget? Det er måske et vidt spørgsmål, men jeg tror aldrig jeg vil komme til at lave beregninger for mere end i hvert fald maksimalt 40 kunder.

svar

Med N kunder antallet af mulige ruter N! (N fakultet, dvs N *(N-1) *(N-2) ... *2 *1)  når der er N kunder. Og køretiden på 'prøv dem alle' bliver proportional med det tal.
md 40 kunder bliver det i størrelsesordenen 100000000000000000000000000000000000 ruter der skal udregnes og sammenlignes. ( et meget groft gæt, men vi kan nok være enige om at det er mange :-))

mvh JakobA

et meget lille svar

Ups sorry - det er vist ved at være på tide at jeg accepterer jeres svar!

Tak for hjælpen :)

Mvh
Torben