24. maj 2002 - 13:34Der er
22 kommentarer og 1 løsning
Excel-Problemløser
Jeg er ved at lave et projekt, hvor vi bruger binær lineær programmering, til at løse et ruteplanlægningsproblem (TSP), hvor ruten skal minimeres. Jeg har dog et problem med bibetingelserne! Jeg kan ikke få ruten til at være sammenhængende, der skaber "subture", dvs. den eksempelvis laver en rute der hedder Odense-Middelfart-Bogense-Odense + en rute Nyborg-Svendborg. Det jeg gerne vil ha' er, at den laver en sammehængende rute, som starter i odense og slutter i Odense, uden subture.
Hvis det skal laves i Excel, hvilket nok ikke er umuligt, vil jeg nok lave det som "brute force" beregning. Dvs. 1. Den skal beregne samtlige ruter 2. Den skal beregne totalafstand for alle ruter 3. Den skal finde den korteste rute
Men der er jo mange måder at gribe det an på, der er jo skrevet tykke bøger om ruteoptimeringsalgoritmer :-)
Jeg kunne godt tænke mig at se svaret til dette spørgsmål, da jeg højst sandsynligt sidder med den samme opgave!!! ;-) Er det ikke obligatorisk opgave fra "Modellering og Algoritmer" med Niels Christian?
Pernille
Synes godt om
Slettet bruger
26. maj 2002 - 21:56#10
Jeg har tidligere lavet noget tilsvarende i C++, også i forbindelse med en skoleopgave :-)
1. Find samtlige (!) mulige kombinationer af ruter dvs. ABCDE, ABCED, ACBDE osv. For x noder er der x! (fakultet) antal permutationer.
2. Hver rute opdeles i under-ruter. F.eks: ABCDE opdeles i A-B, B-C, C-D, D-E
3. Afstanden imellem hver under-rute slås op i en afstandstabel. Alle underafstandene adderes og totalafstanden for ruten findes.
4. Til sidst, find den rute med korteste afstand. ----------------------------
Fordele: Du finder med garanti den korteste rute Ulempe: Du skal undersøge samtlige ruter, det kan tage langt tid med mange noder. Ved x = 10, skal du undersøge 3628800 ruter !
Der ligger ikke nogen snedig algoritme bag, men det er (vistnok) den mest simple måde at gøre det på.
Så vidt jeg husker er dit problem NP hard. Hvilket betyder at der ikke er nogen nem algoritme til at finde en løsning. Jeg vil tro at hvis du skal løse problemet i excel med en problem løser skal du løse det som et form for sorterings problem. Godt du opstiller dine noder i en liste A B C D Du laver et lille “VBA” program som udregner længden mellem hver linie. Indtil nu ikke noget vanskeligt. (Denne længde skal minimeres) Det du skal nu er at finde en metode til at ”bytte om” på dine noder. Igen laver du en tabel med alle dine noder. Søjle A Søjle B A 4 B 3 C 2 D 4 Tallet I søjlen viser ikke I hvilken række følge noderne kommer I men hvor de skal flyttes hen. F.eks. der står ud for A 4 hvilket betyder at du skal bytte A fra din rute liste ud med D. B skal byttes ud med C, og C skal byttes ud med hvad der nu står på plads 2 i din rute liste. Det der er interessant er at du starter med en sorteret liste og ved hjælp af Søjle B sortere du dine noder. Du kan nu anvende excels solver til at optimere problemet.
Hov en shortes path i en graf er vist ikke NP hard. Hvis du ønsker en beskrivelse af en algoritme til løsning af problemet skal du bare sige til. Men du kan ikke anvende solveren
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.
