Springen naar inhoud

Variant op korste route algoritme


  • Log in om te kunnen reageren

#1

Brandts

    Brandts


  • 0 - 25 berichten
  • 10 berichten
  • Gebruiker

Geplaatst op 23 maart 2012 - 15:05

Hallo iedereen,

Ik zit met het volgende probleem wat erg lijkt op het "kortste route"-probleem.
Ik heb een set xy-coŲrdinaten (bijvoorbeeld punten A, B, C en D) en begin op 1 gedefinieerde punt (A). Ik wil vervolgens vanuit A naar iedere andere punt stappen en daarbij een zo kort mogelijke afstand afleggen tussen de punten in. Dit hoeft dus niet de kortste route te zijn als alle afstanden bij elkaar worden opgeteld!

Neem bijvoorbeeld de volgende coordinaten:
x	y
A	3	5
B	2	4
C	5	4.5
D	3	2

Als steeds gezocht wordt naar de kortste afstand dan zou de route als volgt zijn:
A>B>D>C (1.4+2.2+3.2=6.8) maar ik heb liever de volgende route A>C>B>D (2.1+3.0+2.2=8.3). Deze route is in totaal wel langer maar de maximale afstand van punt tot punt is kleiner (3.0 t.o.v. 3.2).

In werkelijkheid gaat het om enkele honderden punten. Ik ben op zoek naar een slim algoritme dat voor mij de optimale route kan berekenen.

Ik hoop dat ik het probleem zo goed heb uitgelegd :)
Kan iemand me hierbij helpen?

Alvast bedankt,
Brandts

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 02 april 2012 - 21:14

Mag je meerdere keren naar hetzelfde punt gaan?

#3

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 03 april 2012 - 11:34

Heb je grafen gezien? Om dit op te lossen moet je steeds de 2 punten met de kortste afstand ertussen samen nemen in 1 punt. De afstand tot ieder ander punt is de kortste afstand om tot 1 van die 2 punten te komen. Ga zo verder tot je maar 1 punt overhoudt. Alle paden die je dan samen genomen hebben vormen je pad.

Let wel, in dit geval kan het zijn dat je moet terugkeren op een vorig punt.

Als je niet mag terugkeren tot een vorig punt test je eerst de graaf met alleen de kortste pad of er een cycle langs alle punten in zit, dan voeg je de 2e kortste toe, dan de derde kortste, enzovoort. De eerste cycle die je vindt is automatisch de goede.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#4

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 03 april 2012 - 14:25

Kijk eens naar Dijkstra of A*.

#5

Brandts

    Brandts


  • 0 - 25 berichten
  • 10 berichten
  • Gebruiker

Geplaatst op 06 april 2012 - 12:57

@ kee en 317070
Ik mag niet terug keren naar een vorig punt.

Misschien heb ik het verkeerd uitgelegd maar ik ben ook niet op zoek naar de kortste route langs alle punten. Ik ben op zoek naar een route langs alle punten waarbij de maximale afstand tussen 2 opeenvolgende punten minimaal is.

@ Xenion
Deze algoritmes heb ik al eens gevonden maar het zijn beide algoritmes om een kortste route te bepalen. De route die ik zoek mag vele malen langer zijn dan deze kortste route (zie hierboven)

Ik ben er intussen achter dat mijn probleem het "Bottleneck Traveling Salesman Problem" heet en aangezien het hier om XY-coordinaten gaat wordt het specifiek het "Euclidian Bottleneck Traveling Salesman Problem" genoemd.

Dit vereenvoudigt de zoektocht maar helaas heb ik nog geen algoritme (dat ik snap, ik moet het algoritme namelijk programmeren voor een praktische situatie) voor de probleem gevonden.

Veranderd door Brandts, 06 april 2012 - 13:00


#6

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 06 april 2012 - 13:39

@ Xenion
Deze algoritmes heb ik al eens gevonden maar het zijn beide algoritmes om een kortste route te bepalen. De route die ik zoek mag vele malen langer zijn dan deze kortste route (zie hierboven)


Die algoritmes bepalen de kortste route aan de hand van een kostfunctie. Als deze kostfunctie het aantal bezochte punten niet meetelt, dan doet het toch wat je wil?

#7

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 06 april 2012 - 14:19

Depth-first search lijkt me.... waarbij je in de gaten houdt wat de grootste afstand tot dan toe is.

#8

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 08 april 2012 - 10:55

Die algoritmes bepalen de kortste route aan de hand van een kostfunctie. Als deze kostfunctie het aantal bezochte punten niet meetelt, dan doet het toch wat je wil?

Nee, er zijn nog een heel veel problemen en ditto algoritmes waarbij in de kostfunctie het aantal bezochte punten niet meetelt. Bijvoorbeeld hetgeen blijkbaar het bottleneck probleem noemt.

Aan Brandts: het tweede algoritme dat ik eerder beschreef zou daar toch voor moeten werken?
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#9

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 10 april 2012 - 13:05

Heb je toevallig een lijst met punten? Ik ben namelijk wel benieuwd of wat ik bedacht heb werkt...

#10

Brandts

    Brandts


  • 0 - 25 berichten
  • 10 berichten
  • Gebruiker

Geplaatst op 10 april 2012 - 13:36

@ EvilBro
Deze functie zoekt een pad dat terug keert naar bepaalde punten. Daarnaast heb ik niet een aantal gedefineerde paden. Ik kan direct van een punt naar een ander punt stappen zonder een omweg te moeten maken via een andere punt. Simpel gezegd; bij 100 punten heeft ieder punt 99 mogelijke paden naar een ander punt.
Ik wil je best een voorbeeldje geven maar om mijn "probeersels" te testen gebruik ik gewoon 100 random coördinaten.

@ 317070
Als dat zo is begrijp ik je waarschijnlijk verkeerd. Ik heb het idee dat je op deze manier de kortste route langs alle punten vindt, maar dit hoeft niet de route te zijn waarbij de maximale afstand tussen 2 opeenvolgende punten minimaal is.

#11

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 25 april 2012 - 11:31

Heb je hiervoor nog een leuk algoritme gevonden?

Wat ik bedacht had:
Maak een boom van alle mogelijke paden. Doorloop de boom. Daal af in de boom totdat je een pad gevonden hebt. Als je een pad gevonden hebt dan zoek je de langste stap in dat pad. De lengte van die stap bewaar je als maximum. Als je een beter pad wilt, moet deze stap dus anders. Doe vanaf deze stap een kortere stap en daal weer af in de boom. Er zijn dan twee opties: je moet ooit een stap doen die groter is dan je huidige maximum (ga dan terug de boom in en probeer een andere tak). Of je vindt een nieuw pad met een lager maximum. In dat geval bewaar je het nieuwe maximum en ga je weer naar de plek waar dit maximum optreedt om vanaf daar verder de boom te doorlopen. Doe dit totdat je de hele boom hebt doorlopen (sommige delen van de boom bekijk je dus nooit want daar kan toch geen betere oplossing zitten).

#12

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 25 april 2012 - 11:46

@ 317070
Als dat zo is begrijp ik je waarschijnlijk verkeerd. Ik heb het idee dat je op deze manier de kortste route langs alle punten vindt, maar dit hoeft niet de route te zijn waarbij de maximale afstand tussen 2 opeenvolgende punten minimaal is.

Gegeven graaf G1=(V1,E1), zoek daarin het gevraagde. [E1 = verzameling van edges = takken, V1=verzameling van vertices = knopen]


1) maak een lege graaf G2
2) voeg de kortste tak uit E1 die nog niet in G2 zit toe aan G2
3) bevat G2 een cycle: die cycle voldoet aan het gevraagde
4) indien niet, ga terug naar 2)

Maak een boom van alle mogelijke paden.

Deze stap ontploft volledig...
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#13

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 25 april 2012 - 12:35

3) bevat G2 een cycle: die cycle voldoet aan het gevraagde

Waarom zou je dan voldoen aan het gevraagde? Een cycle kan per definitie niet omdat de gestelde vraag uitsluit dat je terugkomt bij een eerder bezocht punt.

Deze stap ontploft volledig...

Alleen als je die boom daadwerkelijk gaat bouwen. Dat doe je natuurlijk niet (dat leek me nogal duidelijk aangezien het binnen de kortste keren uit de klauwen loopt). Je gebruikt gewoon een array om aan te geven waar je je in de boom bevindt en wat je al gehad hebt.

#14

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 25 april 2012 - 15:55

Als ik het originele probleem nog eens lees zie ik dat er eigenlijk geen wegen tussen de punten zijn. Er wordt gewoon gezocht naar de lijn die alle punten kan verbinden met de maximale afstand tussen 2 punten op de lijn minimaal. Je moet dan niet echt met grafen gaan werken.

Backtracking kan hier nuttig zijn:

Vanuit het startpunt, kies het punt dat er het dichtst bij ligt.
Beschouw dat punt als nieuw startpunt en loop.

Bij het voorlaatste punt heb je maar 1 keuze meer (het laatste).
Als de afstand die je dan moet afleggen kleiner is dan de maximale afstand in het pad tot daar, dan heb je de oplossing.
Indien dat niet zo is, maak dan de laatste keuze ongedaan en kies daar de 2e dichtste.

#15

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 25 april 2012 - 16:51

Je moet dan niet echt met grafen gaan werken.

De dataset leent zich uitstekend om door een graaf weergegeven te worden.

Als de afstand die je dan moet afleggen kleiner is dan de maximale afstand in het pad tot daar, dan heb je de oplossing.

Dit zou betekenen dat de laatste stap van het optimale pad nooit de grootste stap kan zijn, Dat is onzin.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures