Overleg:Handelsreizigersprobleem

Een

Ik heb accenten op "precies één keer" gezet, maar ik ben niet voor 100% zeker of dat hier wel moet. Madyno (overleg)

Ik heb die woorden helemaal weggehaald. Stel dat de steden aan een rechte lijn liggen. Dan zou het onmogelijk zijn om van A naar C te reizen zonder langs B te komen, een rondreis A-B-C-A is dan onmogelijk. Maar er zijn genoeg wegen op deze aarde, je kunt een omweggetje maken om B op de terugreis te vermijden en daar wordt het probleem niet anders van. Het probleem van de handelsreiziger is dan ook elke stad te bezoeken, maar hij mag best een tweede keer door dezelfde stad komen (tenzij hij iemand in die stad zo boos heeft gemaakt dat de reiziger zijn leven daar niet meer zeker is).

Je kunt natuurlijk een graaf tekenen met een beperkt aantal verbindingslijnen en eisen dat elk knooppunt precies één keer wordt bezocht. Maar dat is een ander probleem. Daar zit de handelsreiziger niet mee. Handige Harrie (overleg) 10 dec 2017 12:39 (CET)

Je kunt je ook voorstellen dat de reiziger een piloot is die een aantal vliegvelden moet bezoeken. In dat geval maakt hij de reisroute altijd langer als hij twee keer op hetzelfde vliegveld landt. Zelfs als het mag, zal hij het niet doen. Handige Harrie (overleg) 10 dec 2017 12:47 (CET)

Het handelsreizigersprobleem komt uit de theoretische informatica. Het wordt vaak voorgesteld aan de hand van een landkaart ofzo om het begrijpelijk te maken, maar de invoer van het probleem is eigenlijk een volledige, gewogen graaf. Volledig betekent: tussen elk tweetal punten bestaat een afstand. Het is dus helemaal niet nodig om via een andere stad te gaan, je kan altijd direct naar iedere stad reizen.

Aan de andere kant is wel heel nuttig te eisen dat elke stad precies een keer bezocht wordt, want dat zorgt er voor dat elke mogelijke oplossing even lang is, en er dus eindig veel mogelijkheden bestaan, die je in theorie allemaal uit kunt proberen. Als elke stad vaker bezocht kan worden, zijn er oneindig veel mogelijke rondritten en dan moet je plotseling redeneren waarom het probleem in principe door een computerprogramma opgelost kan worden. Hoopje (overleg) 10 dec 2017 17:31 (CET)

Ik heb je bijdrage even in tweeën geknipt.

Het eerste, daar ben ik het helemaal mee eens.

Het tweede snap ik niet. Natuurlijk, als je gecompliceerde rondritten gaat maken, zijn er oneindig veel reisroutes. EN als je al die reisroutes gaat onderzoeken, ben je oneindig lang bezig. Maar die reisroutes, twee keer via dezelfde stad, zijn altijd langer. Je kunt ze dus meteen uitsluiten.

Als je werkt met een volledige graaf en je komt door een stad waar je al eerder bent geweest, dan weet je meteen dat je verkeerd bezig bent (met een reëel wegenstelsel is dat niet helemaal het geval).

Een mogelijk algoritme. Je hebt al een reis van 100 km gevonden. Nu ga je op zoek naar een andere reis en je bent al 101 km onderweg. Dan kun je alle reizen die met die 101 km beginnen uitsluiten. Zo krijg je toch een eindig algoritme.

Conclusie: de opgave dat elke stad precies een keer bezocht wordt, is geen vereiste, maar wel een conclusie.

Met een reëel wegenstelsel kan het wél voorkomen dat je twee keer door dezelfde stad komt. Denk een een treinreis Roosendaal-Goes-Middelburg-Roosendaal. Je hoeft in Goes echter niet uit te stappen. En ook dan geldt: als een gedeeltelijke reis al langer is dan een eerder gevonden volledige reis, dan zoek je niet verder.Handige Harrie (overleg) 10 dec 2017 20:58 (CET)

Ik beweer ook niet dat het probleem zonder de eis dat elke stad precies één keer bezocht wordt geen praktische toepassingen heeft, of dat het niet triviaal naar het TSP gereduceerd kan worden. Ik beweer dat het TSP meestal mét die eis gedefinieerd is. Ik heb net nog even in mijn boekenkast nagekeken, en ja, in alle werken die ik nog in de boekenkast heb staan is dit geval. En als mijn talenkennis me niet in de steek laat, definieren ook alle Wikipedia's (behalve de Engelse, waar jij het zelf vandaag hebt weggehaald) het TSP zo. Waarom dat zo is? Misschien vanwege de reden die ik hierboven al noemende. Misschien omdat je het Hamiltoncykel-probleem dan triviaal polynomiaal naar TSP kunt reduceren (en zo bewijst dat TSP NP-moeilijk is). Ik weet het niet, en dat is in deze discussie eigenlijk ook niet zo interessant. Wat wél interessant is, is hoe de gezaghebbende bronnen het probleem definiëren, en die geven mij gelijk. Hoopje (overleg) 10 dec 2017 22:34 (CET)