Variant op korste route algoritme

[Brandts]

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:

Code: Selecteer alles

	 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

[kee]

Mag je meerdere keren naar hetzelfde punt gaan?

[317070]

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.

[Xenion]

Kijk eens naar Dijkstra of A*.

[Brandts]

@ 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.

[Xenion]

@ 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?

[EvilBro]

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

[317070]

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?

[EvilBro]

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

[Brandts]

@ 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.

[EvilBro]

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).

[317070]

@ 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...

[EvilBro]

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.

[Xenion]

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.

[EvilBro]

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.