Handelsreizigersprobleem

[Esthetisch]

Neem nu de versie van het handelsreizigersprobleem waarin de afstanden tussen steden de rechte lijnen hiertussen zijn, en dus de situatie in 2d op schaal getekend kan worden. Er wordt geen rekening gehouden met bergen en omwegen.

Stel nu dat de volgende handelswijze altijd de kortste route geeft:

*********

- verbindt de 3 punten waarmee je de driehoek krijgt met de grootst mogelijke omtrek.

- verbindt de punten binnen de driehoek met de driehoek. Neem steeds het punt dat het dichtst bij een lijn licht, en verbindt het met de lijn die het dichtste bij ligt

- verbindt de punten buiten de driehoek. Neem steeds het punt dat het verste weg ligt bij een lijn, en verbindt het met de lijn die het dichtste bij ligt.

- als je alle punten gehad hebt: schrap de langste afstand

na het schrappen moet voor allebei de laatste 3 punten van de lijn een driehoek worden getekend, waarvan vervolgens de langste zijde moet worden geschrapt.

De dichtstbijzijnde punt bij een lijn wordt bepaald door de loodrechte afstand. De dichtstbijzijnde lijn van een punt wordt bepaald door: de loodrechte afstand / de lengte van de lijn waartoe de loodrechte afstand genomen wordt. De kleinste uitkomst van deze som is de lijn waarmee het punt moet worden verbonden.

****************

Dat zou betekenen dat voor elk extra punt de handelswijze maar 1 keer extra hoeft te worden uitgevoerd. Wat zou dit voor gevolgen hebben voor de oplosbaarheid van het P vs. NP probleem?

[EvilBro]

Stel nu dat de volgende handelswijze altijd de kortste route geeft:

Dat kunnen we best stellen, maar het is volgens mij niet waar.

Dat zou betekenen dat voor elk extra punt de handelswijze maar 1 keer extra hoeft te worden uitgevoerd. Wat zou dit voor gevolgen hebben voor de oplosbaarheid van het P vs. NP probleem?

Het handelsreizigerprobleem is, volgens mij, NP-volledig. Als dit algoritme zou werken dan heb je bewezen dat NP=P. Het probleem is echter de 'als'. Je zal dus moeten bewijzen dat het algoritme altijd de korste route geeft. De kans dat dit gaat lukken lijkt mij zeer laag.

[mathfreak]

Het handelsreizigerprobleem is, volgens mij, NP-volledig.

Volgens Wikipedia: "Van het probleem is aangetoond dat het NP-moeilijk is en de formulering in beslisbaarheidsvorm ("Gegeven de afstanden en een totale afstand x, beslis of er een oplossing mogelijk die korter is dan x") is NP-volledig."

[Math-E-Mad-X]

Stel nu dat de volgende handelswijze altijd de kortste route geeft:

....

Ik vind je uitleg erg onduidelijk, dus ik zou niet kunnen zeggen of dit inderdaad de kortste route oplevert.

[Esthetisch]

Dat kunnen we best stellen, maar het is volgens niet waar.

Het zou mij eveneens verbazen, maar voor de gevallen waarop ik het geprobeerd heb klopt het steeds, voor zolang in het uiteindelijke pad geen wegen meer heeft die bij de begindriehoek zaten. Als dit wel het geval is moet je een andere begindriehoek nemen.

Maar waarom denk jij dat het niet waar is?

Ik vind je uitleg erg onduidelijk, dus ik zou niet kunnen zeggen of dit inderdaad de kortste route oplevert.

Welk deel begrijp je niet?

UPDATE: het klopt inderdaad niet.

[Esthetisch]

UPDATE 2: Hij klopt toch wel, althans voor de versie waarvan ik dacht dat die niet klopte.

[Drieske]

Hij klopt toch wel, ...

Toon dan eens dat hij klopt?

[Math-E-Mad-X]

- als je alle punten gehad hebt: schrap de langste afstand

Ik neem aan dat je hier bedoelt: 'schrap de langste lijn'

Maar hoe weet je dan nog zeker dat je inderdaad alle punten met elkaar verbonden hebt? Doordat je één van de lijnen schrapt zou het toch kunnen dat je één van de punten losgekoppeld hebt van de rest?

na het schrappen moet voor allebei de laatste 3 punten van de lijn een driehoek worden getekend, waarvan vervolgens de langste zijde moet worden geschrapt.

En van deze zin begrijp ik al helemaal niets. Je hebt het over "de laatste 3 punten van de lijn". Welke lijn bedoel je hier, en wat zijn in godsnaam de laatste 3 punten van een lijn? En vervolgens zeg je dat voor alle drie de punten een driehoek moet worden getekend. Bedoel je dat je dus 3 driehoeken tekent? Of bedoel je dat je 1 driehoek tekent die precies door die 3 punten heen gaat? In het eerste geval: waar teken je die 3 driehoeken dan?

[Marko]

Ik weet niet of het algoritme goed begrepen heb, maar denk niet dat deze altijd de kortste route zal geven. Stel dat je 5 punten hebt (A, B, C, D en E), en dat de grootste driehoek (ABC) die je kunt vormen een is met 2 lange zijden AC en BC en 1 (zeer) korte AB. De andere 2 punten D en E liggen in de nabijheid van deze korte zijde, een een stuk buiten de driehoek, een een stukje erbinnen (zie bijgevoegde figuur).

TSP 1354 keer bekeken

Het algoritme volgend wordt dan de korte zijde "opgeofferd" voor de vorming van verbindingen AD en DB, en daarna wordt DB "opgeofferd" voor de vorming van DE en EB. De route wordt dan A-D-E-B-C (links) waarbij 1 van de lange zijdes dus gehandhaafd blijft.

Is deze route daadwerkelijk korter dan het alternatief B-D-A-E-C (rechts) ?

[Esthetisch]

Is deze route daadwerkelijk korter dan het alternatief B-D-A-E-C (rechts) ?

Ik begrijp het punt. Echter voer je het vrijwel helemaal, maar net niet perfect uit. Waarschijnlijk is namelijk "de lijn AB / (loodrechte afstand E-AB)" groter dan "de lijn AC / (loodrechte afstand E-AC)", dus zul je de tweede optie ervan moeten kiezen.

Maar het algoritme klopt inderdaad niet. Ik heb er zelf ook een aantal gevonden waarvoor het niet klopt.

Helaas pindakaas.

Telkens loop ik tegen hetzelfde probleem aan, namelijk dat je ergens moet beginnen met definiëren. Ik dacht dit op te lossen met de grootste driehoek, omdat die lijnen vrijwel zeker niet in de eindroute komen, maar naar nu blijkt is dat dus toch niet voldoende. Het kan nog steeds voor komen dat de lijn na 1 of 2 keer breken nog steeds over een pad loopt dat niet bij de eindronde zit, maar dus ook niet meer bewerkt wordt.

Overigens is voor de niet kloppende voorbeelden met de op-1-of-2-na-grootste begindriehoek de route alsnog te vinden, maar dat is natuurlijk te vaag en onbevredigend, dus ik denk dat ik me hier nu op zal moeten concentreren.

[Esthetisch]

@Marko: je moet trouwens ook eerst de punten binnen de driehoek verbinden, en daarna pas die erbuiten.

[Esthetisch]

Ik neem aan dat je hier bedoelt: 'schrap de langste lijn'

Maar hoe weet je dan nog zeker dat je inderdaad alle punten met elkaar verbonden hebt? Doordat je één van de lijnen schrapt zou het toch kunnen dat je één van de punten losgekoppeld hebt van de rest?

Je begint met een driehoek, dus een rondlopend ononderbroken pad. Je eindigt met een pad dat langs alle punten gaat, en waarmee je weer op het beginpunt uitkomt. Echter is het niet nodig om helemaal rond te lopen, dus kan je de rondlopende lijn op 1 plek onderbreken, dit doe je daar waar je het meeste afstand kan verliezen.

En van deze zin begrijp ik al helemaal niets. Je hebt het over "de laatste 3 punten van de lijn". Welke lijn bedoel je hier, en wat zijn in godsnaam de laatste 3 punten van een lijn? En vervolgens zeg je dat voor alle drie de punten een driehoek moet worden getekend. Bedoel je dat je dus 3 driehoeken tekent? Of bedoel je dat je 1 driehoek tekent die precies door die 3 punten heen gaat? In het eerste geval: waar teken je die 3 driehoeken dan?

Nadat het pad dus onderbroken is, heb je 2 eindpunten van het pad. Namelijk de voor en achter kant. Je controleert daar of de drie laatste punten van het pad wel de kortste zijde van hun driehoek gebruiken, zo niet, dan is er een kortere verbinding mogelijk tussen die 3 punten. Die vrijheid ontstaat dankzij het onderbreken van de lijn.

[Marko]

Ik begrijp het punt. Echter voer je het vrijwel helemaal, maar net niet perfect uit. Waarschijnlijk is namelijk "de lijn AB / (loodrechte afstand E-AB)" groter dan "de lijn AC / (loodrechte afstand E-AC)",

Nee, ik heb bewust punt E zo gezet dat hij dichter bij BD ligt dan bij AC.

@Marko: je moet trouwens ook eerst de punten binnen de driehoek verbinden, en daarna pas die erbuiten.

Klopt, dat was niet goed; maar dat maakt voor het resultaat uiteindelijk niet uit.

Je algoritme is op zich slim bedacht; zoals je aangeeft: door te beginnen met de langste lijnstukken en die te vervangen, zul je je kans vergroten om op een korte route uit te komen. Ik meen dat je niet de eerste bent om met een dergelijk algortime te komen, en heb in een ver verleden iets dergelijks voorbij zien komen, maar ik zou niet weten welke naam daarbij hoort.

[Esthetisch]

Als het aantal bewerkingen om tot de kortste route te komen gelijk is aan de som van n, geldt dan P = NP?

[Esthetisch]

Als het aantal bewerkingen om tot de kortste route te komen gelijk is aan de som van n, geldt dan P = NP?

En bij n in het kwardraat?

En maakt het nog uit of je de symmetrische of asymmetrische neemt?

Dan ga ik nog eens een keertje ff lekker puzzelen.