handelsreizigersprobleem

Menswetenschappen, natuurwetenschappen, cultuurwetenschappen, formele wetenschappen, toegepaste wetenschappen, interdisciplinair, ...

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 26 jun 2011, 19:56

Jan Willem Nienhuys schreef:Het komt wel vaker voor dat wiskundigen lichtelijk verschillende definities geven.


Beste Jan Willem,

Ik kan er helemaal mee leven dat u een "lichtelijk verschillende definitie" geeft van de algemeen gangbare definitie.
Mijn visie op de werkelijkheid is immers ook "lichtelijk verschillend" van de algemeen gangbare. Dus wie ben ik om u dat kwalijk te nemen.

Vriendelijke groeten,
Johan.
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 27 jun 2011, 00:29

Dit begon allemaal met

De vraag van één miljoen: hoeveel is 1 + 1.


Die vraag ontsproot uit de gedachte dat een pad waarvan het begin- en eindpunt identiek zijn geen pad kan zijn waarbij elk punt maar een (1) keer gepasserd wordt. Maar afgezien van het feit dat dat eenmaal passeren niet zo wezenlijk is (dat het pad zo kort mogelijk is, daar gaat het om) betekent passeren: eenmaal aankomen én eenmaal weggaan. Dat is bij het 'eindpunt' ook zo. In feite kun je van een cykel elk punt als 'begin- en eindpunt' nemen. Het is een flauwe puzzel om het zo te formuleren (met een afbeelding van een cirkel in plaats van een rechte lijn naar het pad) dat dit ondergeschikte detail vermeden wordt. De formulering wordt dan omslachtiger, terwijl het voor het begrip van waar het om gaat nergens toe dient.

De million dollar question was ook niet om zo'n pad te vinden, maar om aan te tonen dat het algemene procédé om zulke paden te vinden vreselijk veel (in een bepaalde precieze zin) aan rekentijd vergt.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 27 jun 2011, 06:13

Jan Willem Nienhuys schreef:betekent passeren: eenmaal aankomen én eenmaal weggaan.


Hoe kom ik aan in het vertrekpunt?
"ergens aankomen" impliceert toch dat je ergens vertrokken bent?
Denk goed na voor we weer vertrokken zijn (!) voor een lange rit.
Ken je dat spelletje(!) nog van toen we klein waren en we iets moesten zoeken. En de omstaanders maar voortdurend "warm" en "koud" roepen?
"Warm, warm, warm Jan Willem!"
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor axxyanus » 27 jun 2011, 09:17

johan bosmans schreef:
Jan Willem Nienhuys schreef:betekent passeren: eenmaal aankomen én eenmaal weggaan.


Hoe kom ik aan in het vertrekpunt?"

Dat hoort niet tot het probleem. Het probleem begint pas vanaf je in het vertrekpunt bent. Of je daar al was omdat je daar woont of dat je daar naartoe bent gegaan omdat je daar werkt en dan pas aan je ronde moet beginnen is wat de probleem stelling betreft van geen enkel belang.
Al mijn hier geuite meningen zijn voor herziening vatbaar.
Avatar gebruiker
axxyanus
 
Berichten: 3006
Geregistreerd: 10 dec 2006, 15:51
Woonplaats: Sint-Pieters-Leeuw

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 27 jun 2011, 10:49

Een 'kring met startpunt' in een graaf ter lengte n is een afbeelding f van de getallen 1,...,n naar de punten verzameling van de graaf, zodanig dat voor elke i groter of gelijk 1 en kleiner dan n er een kant is van f(i) naar f(i+1), en bovendien zodanig dat er ook een kant is van f(n) naar f(1). f(1) noemen we het startpunt.

We noemen twee kringen f en g ter lengte n equivalent als er een niet-negatieve gehele k < n is, zodanig dat voor alle i en j in de verzameling {1,...,n} met de eigenschap dat i+k-j deelbaar is door n, geldt f(i)=g(j). Evident is g(k+1) het startpunt van f. Dit si een equivalentierelatie, het bewijs laat ik achterwege. Met kring bedoelen we een equivalentieklasse van kringen met startpunt.

Elk lid van zo'n equivalentieklasse kan dus dienen om aan te geven welke kring we bedoelen. Notabene: in deze terminologie is de lengte van de kring het aantal stappen.

In een volledige graaf is er tussen elk tweetal punten een kant, en kan de conditie "zodanig dat voor elke i groter of gelijk 1 en kleiner dan n er een kant is van f(i) naar f(i+1)" gemist worden.

Het gewicht van een kring wordt berekend door voor een representant f de som van de gewichten van de kanten van f(i) naar f(i+1) (voor i=1,...n-1) te berekenen plus het gewicht van de kant van f(n) naar f(1). Uiteraard is deze som dezelfde voor elke representant, dus we kunnen dit het gewicht van de kring noemen.

Laat G een samenhangende graaf met n punten zijn en positieve gewichten op alle kanten. Dan is er een kring die alle punten bevat. Als G volledig is en bovendien voldoet aan de driehoeksongelijkheid, dan is het evident dat er een kring van minimale gewicht is ter lengte n die dus elk punt precies eenmaal bevat. Immers, voor elke kring die een punt meerdere keren bevat is er een kring die niet langer is en die bij de tweede passage dat punt gewoon overslaat.

Laat G de volledige graaf zijn op n punten met positieve gewichten op alle kanten. Het probleem om een kring ter lengte n van minimaal gewicht te vinden noemen we het handelsreizigersprobleem.

In geval we een niet-volledige maar wel samenhangende graaf G hebben met n punten en gewichten op de kanten, die niet aan de driehoeksongelijkheid voldoet en waarin we een kring van minimaal gewicht willen vinden, dan kunnen we dit probleem reduceren tot het vorige probleem, en wel als volgt. We definiëren een nieuwe graaf, namelijk een volledige graaf G' met dezelfde punten als G, maar met de volgende gewichten op de kanten: het gewicht (in G') van de kant tussen x en y is het minimale gewicht van de paden in G van x naar y. (Oefening voor de lezer: geef de formele definitie van een pad van x naar y in een graaf).

In G' lost men het handelsreizigersprobleem op. De gevonden oplossing kan dan gebruikt worden om een kring van laagste gewicht in G te vinden: vervang elke kant in G' in de oplossing door het corresponderende kortste pad in G. Het probleem wint door deze methode niet aan complexiteit, want het vinden van een kortste pad tussen twee gegeven punten in een samenhangende graaf is een tamelijk eenvoudig probleem dat in een polynomiaal aantal stappen kan worden opgelost, in wezen door stapje voor stapje een lijst met kortste afstanden vanuit x tot alle punten te maken.

Zo, nu zijn we klaar met wat op pagina 1 van een boek over het handelsreizigersprobleem zou kunnen staan. Ik neem aan dat iedereen die een beetje thuis is in het probleem dit allemaal wel weet en aanneemt dat iedereen die hier serieus over meepraat het ook wel weet, zodat gezeur over aankomen en vertrekken en de eis 'maar een keer' maar afleidt. Dus de 'handelsreiziger' die Groningen, Sappemeer, Hoogezand, Stadskanaal, Musselkanaal, Nieuw Buinen en Ter Apel moet bezoeken, hoeft zich niet druk te maken over het feit dat in handboeken over het handelsreizigersprobleem alleen gesproken wordt over een kring in een volledige graaf. Als hij de oplossingsmethode volgt krijgt hij er uiteindelijk toch uit dat hij over de rechte weg van Groningen naar Ter Apel rijdt, onderweg overal stopt, en van Ter Apel terug naar Groningen in een ruk zonder te stoppen.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 27 jun 2011, 11:38

Voorsmaakje:

Kan ik hier op reageren?
Ja.

(Zo heb ik mijn kinderen ook opgevoed. Als ik ze vraag "kan jij de afwas doen?". Dan antwoorden ze steevast "ja" waarop ze languit in de zetel gaan liggen. Ik heb het me al beklaagd, maar ik ben ook wel een beetje fier op ze)
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 27 jun 2011, 20:59

Is het mogelijk een wandeling te maken waarbij elk punt precies eenmaal gepasseerd wordt en waarbij begin- en eindpunt hetzelfde zijn?
Dat is de vraag die in het artikel in kennislink werd gesteld en waar ik een antwoord op geformuleerd heb.
Ik ben bereid op alle vragen te antwoorden.
Ik heb wel bepaalde rechten als ik ondervraagd wordt.
Jan Willem is er misschien niet zo mee vertrouwd, maar als men in België verhoord wordt is de eerste vraag altijd: in welke taal wil u verhoord worden?
Wel, ik ben geen wiskundige bolleboos. Ik heb geen probleem om dat toe te geven. Ik zal geen uitspraken beginnen doen over iets wat ik niet begrijp. Als het probleem in wiskundige taal gesteld wordt zal ik mij daar niet aan wagen.
Zoals de vraag gesteld wordt meen ik ze echter te begrijpen en wil ik er een antwoord op formuleren. Ik ben in de veronderstelling dat wiskunde een taal is (vandaar ook dat ik de eerste ben om te zeggen dat wiskunde een kunst is), een strikt logische taal die veel sneller en efficiënter is om bepaalde problemen te benaderen, maar niet een taal die totaal op zichzelf staat, niet een taal die geen enkele link meer heeft met de talige taal. Indien deze veronderstelling fout is stop ik er mee. Ik hoop alvast dat hierop met een eenvoudig “ja, deze veronderstelling is juist” of met een eenvoudig “nee, deze veronderstelling is fout” kan geantwoord worden.
Ik moet “passeren” dus begrijpen als “in elk punt éénmaal aankomen en éénmaal weggaan”.
Niets zo duidelijk als een duidelijke definitie.
Op mijn opmerking “hoe kom ik aan in het vertrekpunt” komt de reactie “dat hoort niet tot het probleem. Het probleem begint pas vanaf je in het vertrekpunt bent”.
Ik heb er lang over nagedacht en een paar graafjes getekend. Ik moet in dat geval toegeven: bingo voor Axxyanus (en Jan Willem), de jackpot van één miljoen dollar.
Het antwoord is in dat geval “ja, het is mogelijk”.
Ik zie bij God geen enkel argument om daar tegen in te gaan. Maar als ik iets over het hoofd zie had ik dat graag van u gehoord.
Ik ben er zeer door gefascineerd.
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 27 jun 2011, 21:16

jackpot van één miljoen dollar.

Helaas niet, want daarvoor moet je een waterdicht bewijs produceren dat voor elke positieve a en elk algoritme om een TSP op te lossen de verhouding ('aantal stappen' : n in de macht a) naar oneindig gaat, waarbij 'aantal stappen' staat voor: het maximum aantal stappen dat nodig is om met dat algoritme het kortste pad te vinden voor een TSP met n punten (of eigenlijk, als ik het goed begrijp, de vraag of er een pad is korter dan een gegeven getal met ja of nee beantwoorden). Niet lang geleden was het groot nieuws dat iermand meende dat hij de oplossing had, maar dat was te vroeg gejuicht.

Ik weet niet eens hoe die algoritmen werken en ik mheb grote bewondering voor degene die het wel weten. Het probleem is wat moeilijkheidsgraad vergelijkbaar met een heleboel andere problemen
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 27 jun 2011, 21:51

Jan Willem Nienhuys schreef: want daarvoor moet je een waterdicht bewijs produceren


Mag ik even een analogie suggereren waar u het niet eens mee zal zijn maar waarvan ik hoop dat ze u toch even doet nadenken.

Als ik mijn kinderen vraag of ze de afwas kunnen doen is daar de verzwegen aanname van mijn kant of ze een zeer specifieke afwas op een zeer specifiek moment kunnen doen.
Als ze daar “ja” op antwoorden zal ik daar op mijn beurt weer op antwoorden dat ze daar eerst maar eens het waterdichte bewijs van moeten leveren. Dat heb ik ondertussen ook wel geleerd!
Voorlopig zijn ze er alleen nog maar in geslaagd dat te bewijzen door die specifieke afwas ook op dat specifieke moment te doen!
Wat denkt u Jan Willem? Denkt u dat ik mij op korte termijn een afwasmachine moet aanschaffen?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Digit » 27 jun 2011, 22:17

Ik denk dat je moet stoppen met je kinderen te pesten !

Digit
Wat is, IS !
Avatar gebruiker
Digit
 
Berichten: 8724
Geregistreerd: 09 nov 2006, 09:03

Re: handelsreizigersprobleem

Berichtdoor Blueflame » 29 jun 2011, 11:12

Een praktische toepassing van dit probleem in de natuur:
http://www.physorg.com/news/2011-06-bum ... oblem.html .
Niet alleen de kortste weg is belangrijk om het rendement van een route te bepalen.
Dit in de marge, ik kwam het artikel toevallig tegen.

Mvg.
Nonsense is our core business
Avatar gebruiker
Blueflame
Site Admin
 
Berichten: 4139
Geregistreerd: 20 okt 2006, 12:43

Vorige

Keer terug naar Wetenschap

Wie is er online

Gebruikers op dit forum: Geen geregistreerde gebruikers. en 1 gast