Algoritme: lijnenstukken op kortste manier verbinden

[Rekcor]

Ik ben op zoek naar een algoritme om een aantal lijnstukken op de kortst mogelijke manier te verbinden. De lijnstukken zelf hoeven - in tegenstelling tot bijv. wegen - elkaar niet te raken: het zijn dus in theorie een verzameling losse vectoren in een 2d-vlak. Ze kunnen elkaar overigens wel raken. Bijv.



Tot nu toe vind ik alleen algoritmen die punten met elkaar verbinden (Wikipedia: Shortest path problem) of algoritmen voor routeplanning. Het probleem met eerstgenoemde algoritmen is dat de oplossingen niet perse over de lijnen lopen, het probleem met de tweede algoritmen is dat ze vereisen dat de lijnen elkaar raken - net als wegen dat doen.

[.oisyn]

Even voor de beeldvorming, zou dit een oplossing kunnen zijn?


Of moet je een route krijgen die ook over de lijnstukken loopt oid?

.edit: en moet je ze per se verbinden met de eindpunten zoals ik hier deed, of mag je ze ook verbinden op een willekeurig punt op een lijnstuk?

Misschien helpt het als je beschrijft waarom je dit wil doen, ofwel, welk probleem je hiermee wenst op te lossen.

[ Voor 31% gewijzigd door .oisyn op 22-11-2020 14:31 ]

[MOmax]

En wat is “verbinden” volgens jou? De onderste twee lijnen - de “T” - zijn in zekere zin al in verbinding met elkaar, of moeten we dit zien als drie lijn stukken met een gemeenschappelijk punt?

[Philip Ross]

Je kan in principe dit probleem vereenvoudigen door de onderlinge afstanden tussen alle lijnen (kortste pad) te noteren en vervolgens te doen alsof het punten zijn ipv lijnen. Dat is natuurlijk alleen een oplossing als je niet 1 continue lijn hoeft te tekenen.

De constraints van de opdracht maken dus erg uit voor wat de oplossing gaat zijn

[MedionAkoya]

* Dit voegt dus helemaal niets toe aan het topic *

[ Voor 69% gewijzigd door .oisyn op 22-11-2020 17:38 ]

[Rekcor]

Of moet je een route krijgen die ook over de lijnstukken loopt oid?

.edit: en moet je ze per se verbinden met de eindpunten zoals ik hier deed, of mag je ze ook verbinden op een willekeurig punt op een lijnstuk?

Ja inderdaad. Het is dus een variant op het 'traveling sales person' probleem, met het verschil dat de verkopert verplicht over de lijnstukken moet 'lopen'.

Een oplossing zou bijv. kunnen zijn:



Ik verwacht niet per se een complete oplossing hoor (zou wel leuk zijn), een paar pointers naar artikelen/boeken zou al tof zijn :-). Het is voor mij een redelijk nieuw terrein, dus ik weet nog niet goed welke zoektermen ik moet gebruiken.

P.S. het géén huiswerkopdracht, die tijd heb ik 20 jaar geleden (gelukkig) afgerond ;-).

[ Voor 14% gewijzigd door Rekcor op 23-11-2020 08:49 ]

[.oisyn]

Moet je een lijnstuk helemaal aflopen als je 'm begonnen bent, of mag je ook halverwege even een andere weg inslaan?

Het is idd precies TSP. Je kunt jouw probleem volgens mij vrij gemakkelijk omzetten in een graph die je regelrecht aan een TSP implementatie zou kunnen voeren.

[ Voor 41% gewijzigd door .oisyn op 23-11-2020 08:56 ]

[armageddon_2k1]

Is een algoritme voor een Minimum Spanning Tree hier niet op z'n plaats?
Wikipedia: Minimum spanning tree
en dan met name Prim's algorithm:
Wikipedia: Prim's algorithm

[Rekcor]

.oisyn schreef op maandag 23 november 2020 @ 08:52:
Moet je een lijnstuk helemaal aflopen als je 'm begonnen bent, of mag je ook halverwege even een andere weg inslaan?

Nee lijnen moeten worden afgemaakt.

Het is idd precies TSP. Je kunt jouw probleem volgens mij vrij gemakkelijk omzetten in een graph die je regelrecht aan een TSP implementatie zou kunnen voeren.

Ok, hier moet ik even over nadenken, omdat TSP uit lijkt te gaan van punten. Je krijgt dan oplossingen die weliswaar de begin- en eindpunten van de lijnen met elkaar verbinden, maar niet per se over die lijnen lopen.

[TheTjeerd]

Ok, hier moet ik even over nadenken, omdat TSP uit lijkt te gaan van punten. Je krijgt dan oplossingen die weliswaar de begin- en eindpunten van de lijnen met elkaar verbinden, maar niet per se over die lijnen lopen.

Je kan de graaf die je in TSP voert zo transformeren dat als je een uiteinde van een lijn bereikt je hem altijd moet aflopen.

[ Voor 7% gewijzigd door TheTjeerd op 23-11-2020 10:54 ]

[Rekcor]

Dank! Deze post heeft me ook erg geholpen: https://stackoverflow.com...r-line-routes-snowplowing

[KabouterSuper]

.oisyn schreef op maandag 23 november 2020 @ 08:52:

Het is idd precies TSP.

Is dat echt zo? Zoals TS het probleem beschrijft, wil hij/zij de lengte van de te trekken lijnen minimaliseren. De travelling salesman wil de af te leggen afstand minimaliseren. Het kan toch voorkomen dat de salesman een weg twee keer gebruikt?

Ik zou gokken dat een minimal spanning tree optimalisatie beter werkt.

[.oisyn]

KabouterSuper schreef op maandag 23 november 2020 @ 13:53:
[...]

Is dat echt zo?

Wel als ik Rekcor in "Algoritme: lijnenstukken op kortste manier verbinden" lees.

[Philip Ross]

Zitten er kosten verbonden aan het bewegen over de lijnstukken zelf? Of mogen we die buiten de optimalisatie houden? Als daar geen kosten aan zitten dan is het een stuk makkelijker om het om te zetten in een graaf van punten.

Vervolg vraag is of de lijnen van en naar een linnstuk alleen naar de uiteindes mogen lopen of ook vanaf het midden mogen vertrekken/aankomen.

[KabouterSuper]

.oisyn schreef op maandag 23 november 2020 @ 14:09:
[...]

Wel als ik Rekcor in "Algoritme: lijnenstukken op kortste manier verbinden" lees.

Ik zat even te denken of ik een situatie kon vinden waarin de salesman een andere route zou kiezen dan wat een wegenbouwer zou doen. Voor de duidelijkheid: de salesman wil zo snel mogelijk klaar zijn, de wegenbouwer wil zo min mogelijk nieuwe wegen aanleggen (of in het geval van de sneeuwschuivers: vrij maken van sneeuw).
Als je nu een cocktailglas-vorm hebt (de steel van het glas is alleen om ervoor te zorgen dat je via het middenpunt naar beneden gaat):

De wegenbouwer zal de rode wegen erbij bouwen. De salesman zal de groene route willen nemen. In getallen, als de schuine zijde 1 is, dan kost de groene weg 1+sqrt(2)=2.4 voor zowel de wegenbouwer als de salesman. De twee rode wegen kosten samen 2 (voor de wegenbouwer), maar 3 voor de salesman. Dat laatste is zo, omdat de salesman heen en weer moet op een van de rode wegen.

[R4gnax]

armageddon_2k1 schreef op maandag 23 november 2020 @ 09:08:
Is een algoritme voor een Minimum Spanning Tree hier niet op z'n plaats?
Wikipedia: Minimum spanning tree
en dan met name Prim's algorithm:
Wikipedia: Prim's algorithm

Het TSP probleem is NP-complete of NP-hard afhankelijk van welke exacte definitie je naar kijkt.
Een MST kun je vziw in polynomiale tijd bouwen, dus tenzij je P = NP hebt bewezen ga je met een MST niet het TSP probleem oplossen.

Je kunt een MST wel gebruiken als approximatie voor een oplossing voor een TSP probleem. (Meestal vrij goed, zelfs.) En je kunt het gebruiken als heuristic binnen het oplossen van een TSP probleem.

[armageddon_2k1]

@R4gnax Je hebt helemaal gelijk

[GlowMouse]

Je kunt het probleem formuleren als TSP door een extra punt toe te voegen met afstand 0 tot alle andere punten (zodat je een toer krijgt ipv een pad), en door elk lijnsegment te vervangen door de twee eindpunten met afstand 0 tussen elkaar (zodat je elk lijnsegment afloopt).

[KabouterSuper]

Het lijkt op het Steiner tree probleem (wat weer veel weg heeft van het tsp).

[pedorus]

Ik denk dat het probleem nogal af hangt van de kostenfunctie. Als zeg maar de lengte van de rode lijnen de kosten geeft, dan is het een MST (waarbij je de onderlinge afstanden tussen lijngroepjes moet ingeven). Als de lengte van de groene pijlen de kosten geeft, dan is het meer een aangepast TSP. Het lijkt meer op dat laatste. Wat ik dan niet snap aan de groene pijlen is waarom er terug wordt gegaan over de zwarte lijn weer bij rode lijn te komen, een directe lijn is daar korter. Ook is er geen pijl van begin naar eindpunt, is het een TSP waarbij de langste lijn weg mag?

Op zich klopt de oplossing van GlowMouse voor de TSP, maar je zal ook een extra restrictie moeten inbouwen waardoor je zorgt dat oplossingen die niet het pad nemen met afstand 0 worden afgewezen al mocht dit toch gebeuren. Dat is minder waarschijnlijk, maar het kan wel, bijvoorbeeld bij ≡.