handelsreizigersprobleem

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

handelsreizigersprobleem

Berichtdoor johan bosmans » 18 jun 2011, 17:07

Tijd voor wat leven in de brouwerij.
http://www.bloggen.be/excrementen/archi ... ID=1181315
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 19 jun 2011, 09:53

Ik snap het probleem van die blogger niet. 'Passeren' wordt gebruikt in de betekenis van aankomen en meteen weer weggaan. Eerst weggaan en na een lange reis weer aankomen is niet hetzelfde. De blogger laat zijn stuk ontaarden in wat flauwekul op basis van zijn onvermogen om goed te lezen.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 19 jun 2011, 10:01

Ik kijk uit naar uw nieuwe formulering van het probleem.
Ik schrap het u storende "passeren" door het "bezoeken" of "aan bod komen" zoals in wikipedia of kennislink gebruikt wordt.
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor zuurSTOF » 19 jun 2011, 13:09

Welk probleem ???
zuurSTOF
 
Berichten: 1157
Geregistreerd: 21 okt 2006, 11:54
Woonplaats: Gent

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 19 jun 2011, 14:14

zuurSTOF schreef:Welk probleem ???



Wat is een probleem?
Een probleem is een vraag.
Een zin zonder vraagteken is geen probleem maar een stelling.

P = NP?
Dat is de vraag.
Hoe formuleert u dit wiskundig probleem in de Nederlandse taal?
Dat is mijn vraag.

Analogie:
1+1 = ?
Hoeveel is één plus één?

Duidelijk?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 19 jun 2011, 14:48

http://en.wikipedia.org/wiki/NP_%28complexity%29

Problemen worden ingedeeld naar moeilijkheid, en dat gebeurt door na te gaan hoeveel stappen het neemt om de oplossing te vinden, gegeven de hoeveelheid basisgegeven.
Als het oplossen niet meer dan een vast aantal keren een kwadraat, derdemacht enzovoorts aan stappen kost vergeleken met de hoeveelheid invoer, dan spreken we van een polynomiaal probleem.

Voorbeeld: vermenigvuldigen. Als je twee getallen van N cijfers met elkaar vermenigvuldigt, heb je ongeveer N-kwadraat stappen
nodig.
Voorbeeld: factoren zoeken van een getal van N cijfers. Erg veel efficiënter dan 10 tot de macht N (nl. alle mogelijkheden proberen) kan niet voorzover we weten.

In sommige gevallen is het zoeken van een antwoord (in erge gevallen) veel werk, maar kan het gevonden antwoord toch in een polynomiaal aantal stappen worden gecontroleerd.

Het handelsreizigersprobleem bijvoorbeeld. Als bij een bepaald aantal steden vraagt: is er een route die korter is dan een gegeven getal X, is het veel werk om daar antwoord op te geven, maar een gegeven oplossing kan toch in polynomiale tijd gecontroleerd worden.

Zulke problemen heten NP. Er is een bepaalde grote groep NP-problemen die onderling equivalent zijn. Als je de ene in polynomiale tijd zou kunnen oplossen, dan kun je ze allemaal in polynomiale tijd oplossen, omdat je de problemen in elkaar kunt transformeren. Die groep heet NP-compleet. Er zijn ook NP-problemen daarbuiten.

Het is natuurlijk frustrerend dat je wel 'vlot' kunt nagaan dat een voorgestelde oplossing klopt, maar dat die oplossing in het algemeen niet zonder een tijdrovend zoekwerk gevonden kan worden. Het vermoeden is dat NP-problemen (bijvoorbeeld de NP-compleet klasse) geen P-problemen zijn. Daar is echter nog geen bewijs voor gevonden.

Het is eigenmlijk nog iets subtieler want NP wil zeggen 'non-deterministisch polynomiaal', maar het voert me te ver om dat non-determinstisch toe te lichten.

Ik zie niet wat dit met het sommetje 1+1=2 te maken heeft.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 19 jun 2011, 15:05

Voor zover ik het kan nagaan bent u al iets aan het uitleggen waar ik nog niet helemaal geraakt ben.
Ik ben niet zo verstandig als u.
Ik begin bij het begin en daar val ik al stil.
Ik slaag er maar niet in dat stapje over te slagen.

Het begin van het handelsreizigersprobleem:
Een graaf is niets anders dan een verzameling punten (of knopen) en lijnen (of wegen, of takken) die de punten met elkaar verbinden. Een voorbeeld van een graaf zie je hiernaast. Kun je het plaatje natekenen zonder je potlood van het papier te halen, zonder lijnen meer dan één keer te tekenen en te eindigen in het punt waar je begon? Iets formeler geformuleerd: is het mogelijk om een wandeling in deze graaf te vinden waarbij elke lijn precies eenmaal doorlopen wordt en waarbij begin- en eindpunt hetzelfde zijn?

Ik kan dat plaatje namelijk niet tekenen.
Is het punt een onderdeel van de lijn?
Indien nee, hoe geraak ik dan ooit van mijn beginpunt weg?
Indien ja, hoe geraak ik dan in mijn eindpunt zonder de eerste lijn een tweede keer aan te raken?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 19 jun 2011, 23:07

Met dat plaatje kun je drie problemen associëren:

1. het plaatje in een keer tekenen zonder een kant tweemaal te bewandelen (maar je mag wel de punten meerdere keren passeren). Dat is probleem van de constructie van een Euler-pad.

2. een zo kort mogelijk pad (totale lengte zo klein mogelijk, maar misschien geef je alle takken gelijke lengte 1) bedenken dat alle punten ten minste éénmaal passeert (je mag ook vaker langs komen). Dat is het handelsreizigersprobleem. De punten hebben geen lengte.

3. een pad bedenken dat alle punten precies eenmaal passeert. Dat is het probleem van een Hamilton-pad vinden.

Het eerste probleem is oplosbaar, want het is een samenhangende graaf waarin alle punten even graad hebben
(het aantal kanten dat in elk punt samenkomt is even). Bij andere grafen kun je ook makkjelijk zien of het 'kan' of niet.

Het tweede probleem heeft een oplossing, je kunt makkelijk een pad vinden (bijv. een oplossing van 1), maar van alle mogelijke
paden het kortste vinden, dat is nogal een toer.

Het derde probleem heeft niet noodzakelijk een oplossing in het algemeen en een handige manier is er ook niet (die is er wel
voor het eerste probleem). Maar als alle kanten lengte 1 hebben, heb je met een oplossing van probleem 3 ook een oplossing van
probleem 2. Immers, als je 12 punten moet passeren in een circuit, heb je ook minstens 12 kanten nodig. Als je een circuit met
precies 12 kanten hebt is dat meteen een circuit met zo weinig mogelijk kanten. In het voorbeeldje kun je met enig puzzelen wel een hamiltoncircuit vinden.

Het trucje voor 1 is als volgt. Begin over de graaf te lopen tot je weer terug bij je uitgangspunt bent. Bij elk punt kun je altijd weer door vanwege de even graad, behalve mogelijk bij het beginpunt. Als je bij het beginpunt terug bent heb je misschien nog niet alle kanten gehad. Geen nood. Begin ergens op het pad dat je al hebt met een nieuw pad. Als dat klaar is, heb je dus twee circuits zonder gemeenschappelijke kanten. Die plak je aan elkaar (hoe, dat is een puzzeltje) tot je één enkel groot circuit hebt.. Ben je nog niet klaar, herhaal.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 20 jun 2011, 10:29

Jan Willem Nienhuys schreef:
1. maar je mag wel de punten meerdere keren passeren

2. bedenken dat alle punten ten minste éénmaal passeert (je mag ook vaker langs komen).

3. een pad bedenken dat alle punten precies eenmaal passeert.



Ik lees hierin een tegenstrijdigheid.
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Dwarsdenker » 20 jun 2011, 10:38

johan bosmans schreef:Ik lees hierin een tegenstrijdigheid.

Hoezo? Ik vond dat het juist een heldere uitleg. Kun je je nader verklaren?
Wetenschap is gericht op het zoeken naar de best mogelijke verklaring.
Avatar gebruiker
Dwarsdenker
 
Berichten: 470
Geregistreerd: 01 jul 2009, 12:09

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 20 jun 2011, 10:43

Dwarsdenker schreef:
johan bosmans schreef:Ik lees hierin een tegenstrijdigheid.

Hoezo? Ik vond dat het juist een heldere uitleg. Kun je je nader verklaren?



Is het "precies één keer" of is het "tenminste één keer" of is dat voor jou hetzelfde?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor TheSurvivor » 20 jun 2011, 10:54

@Johan Bosmans - Misschien de post die je becommentarieert eens volledig lezen voor je kritiek geeft.
De poster deelt jou probleem op in 3 mogelijke interpretaties en voorziet deze van een antwoord.
TheSurvivor
 
Berichten: 145
Geregistreerd: 17 jun 2011, 12:39

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 20 jun 2011, 11:01

@ the survivor
Ik vermoed dat de poster anders gaat reageren.
Maar om op jou reactie te antwoorden:
Blijkbaar is het handelaarsprobleem niet één probleem, maar zijn het drie verschillende problemen waar geen verband tussen zit (ander uitgangspunt, namelijk "precies één" en "tenminste één").
Correct volgens jou?

(Zie het als een spelletje schaak survivor. Als jij dit zegt zal hij dat zeggen. De zet die jij maakt zou de poster misschien wel overwegen, ALLES moet overwogen worden, maar ik maak me sterk dat hij die zet niet zou uitgevoerd hebben. De reactie lag iets voor de hand)
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Dwarsdenker » 20 jun 2011, 11:17

[quote="johan bosmans"*Zie het als een spelletje schaak survivor. [/quote]
Sorry, ik dacht dat ik dit de rubriek "wetenschap" was.
Wetenschap is gericht op het zoeken naar de best mogelijke verklaring.
Avatar gebruiker
Dwarsdenker
 
Berichten: 470
Geregistreerd: 01 jul 2009, 12:09

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 20 jun 2011, 11:23

Dwarsdenker schreef:Sorry, ik dacht dat ik dit de rubriek "wetenschap" was.


In dat geval moet je antwoorden op de vraag.
Is het "precies één keer" of is het "tenminste één keer" of is dat voor jou hetzelfde?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor TheSurvivor » 20 jun 2011, 11:24

U dwingt me bijna om af te wijken, maar waarom in 's hemelsnaam (excuseer de term) zou je een discussie gaan vergelijken met een spelletje schaak?
Je implicatie hierin is dat een discussie gewoon een reeks strategische zetten is om te komen tot de gewenste uitkomst: winnen. Inhoudelijke argumenten (hoe voor de hand liggend ook) doen niet meer ter zake en hebben minder belang dan de strategisch juiste zet?
In dit opzicht is elke discussie bij definitie reeds waardeloos (om in de terminologie te blijven: een patstelling) aangezien in tegendeel tot schaak dit *altijd* zal leiden tot een halsstarrig weigeren van beide partijen om af te wijken van het uiteindelijk einddoel, nl. gelijk halen.
TheSurvivor
 
Berichten: 145
Geregistreerd: 17 jun 2011, 12:39

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 20 jun 2011, 11:59

johan bosmans schreef:@ the survivor
Ik vermoed dat de poster anders gaat reageren.
Maar om op jou reactie te antwoorden:
Blijkbaar is het handelaarsprobleem niet één probleem, maar zijn het drie verschillende problemen waar geen verband tussen zit (ander uitgangspunt, namelijk "precies één" en "tenminste één").
Correct volgens jou?



Forumregel 2:
Een partij die een standpunt naar voren brengt is verplicht dit standpunt te verdedigen als de andere partij hem daarom verzoekt
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor TheSurvivor » 20 jun 2011, 12:07

U vraagt me echter een standpunt in te nemen over het probleem ten gronde, terwijl mijn opmerking zich echter zuiver op het meta-niveau bevindt. Ik heb geen nood om me te mengen (zoals ondertussen elders aangegeven) in een cirkelredenering (al was het in eerste mate blijkbaar een semantisch debat) en ik heb dan ook geen enkel standpunt over het handelsreizigersprobleem ingenomen dat ik dien te verduidelijken.
TheSurvivor
 
Berichten: 145
Geregistreerd: 17 jun 2011, 12:39

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 20 jun 2011, 12:37

@ survivor:
vanop meta-niveau: sans rancune
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 22 jun 2011, 19:01

johan bosmans schreef:
Jan Willem Nienhuys schreef:
1. maar je mag wel de punten meerdere keren passeren

2. bedenken dat alle punten ten minste éénmaal passeert (je mag ook vaker langs komen).

3. een pad bedenken dat alle punten precies eenmaal passeert.



Ik lees hierin een tegenstrijdigheid.



http://nl.wikipedia.org/wiki/Schaakklok
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 22 jun 2011, 22:51

Ik noemde drie verschillende problemen die enigszins op elkaar lijken die je met een samenhangende graaf zou kunnen associëren:

1 vind een Euler-pad;
2. los het handelsreizeigersprobleem op (in dit geval is er met elke kant ook nog een lengte geassocieerd);
3. vind een Hamilton-pad.

Je kunt natuurlijk nog wel meer problemen met een graaf associëren. Bijvoorbeeld:

4. gegevens de gerichte graaf van alle wegen in een land (of in heel Europa), en twee punten op die graaf. Zoek de kortste (in tijd of kilometers) weg van het ene naar het andere punt. Dat is het probleem dat een navigator oplost, nadat je hem hebt ingesteld (en ook als je van de geplande route afwijkt).

5. Een ander voorbeeld, ook weer met een gerichte graaf van 'wegen' elk met een getal, dat nu niet de lengte voorstelt, maar de transportcapaciteit (in ton per minuut of zoiets) van elke weg. Weer zijn twee punten gegeven en de vraag is wat de capaciteit van het totale netwerk is, en hoe die te realiseren.

Dit zijn allemaal verschillende problemen met elk eigen oplossingstechnieken.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 23 jun 2011, 16:43

Beste Jan Willem,
Staat u me toe dat ik een verhaal aan u opdraag.

Heel lang geleden (jawel!) was ik op vakantie in Kroatië, toen nog het voormalige Joegoslavië.
Op de camping was ik al snel bevriend geraakt met Zoran, de tentbuur. Zoran was een fervent schaker en na een paar partijtjes nam hij me mee naar andere tenten, stenen, klapstoeltjes, matrassen of waar dan ook, als er maar een schaakbord stond.
Schaken was immens populair toen, veel meer dan nu. Overal op de camping werd er geschaakt. Het was ook een bij uitstek sociaal gebeuren. Wie niet schaakte stond wel naast één of ander tafeltje toe te kijken hoe er geschaakt werd.
De ongekroonde koning van de schaakcamping was Samson, een wat overjaars zigeunertype met lange haren die op een gitaar tokkelde als hij niet aan het schaken was. Hij speelde alle mogelijke deuntjes, maar hij had een voorliefde voor flamenco. Vooral ‘s avonds als het te donker was om te schaken, was de aanwezigheid van Samson duidelijk hoorbaar.
Één keer had ik het genoegen om een partijtje schaak tegen Samson te spelen. Het was een ietwat hallucinante ervaring.
Vooral de nonchalance waarmee hij speelde maakte indruk.
Eigenlijk speelde hij niet, hij las zijn krant.
Hij las zijn krant, rookte als een Turk en lurkte van zijn Turkse koffie, maar het was dus een Kroaat.
Telkens ik na een minuut of tien een zet deed, keek hij even over de rand van zijn krant, verplaatste een stuk en verdiepte zich prompt weer in zijn literatuur.
Op een bepaald moment ontspon er zich onder de toeschouwers, ik kan me niet herinneren dat ik ooit een groter publiek als toen heb gehad, een vinnige discussie. De woordenwisseling ging gepaard met uitgebreide hand- en armgebaren. Als Kroaten verbaal de degens kruisen lijkt het wel of ze ruzie hebben.
Één voor één verstomden de stemmen tot uiteindelijk ook de laatste hardnekkige volhouder weifelend naar Samson knikte.
“What was that all about”, vroeg ik wrevelig, want het twistgesprek had danig op mijn concentratie gewogen. (Het kan ook wel zijn dat ik wrevelig was omdat mijn positie op het bord er niet al te rooskleurig uit zag, dat wil ik nu even in het midden laten).
Behoedzaam nam Samson mijn koning tussen twee vingers en legde hem neer.
“Why do you want to play?”, vroeg hij, “you are dead.”
Hij stond recht en reikte me vriendelijk de hand.
Die dag ben ik gestopt met schaken en ben ik beginnen wiezen.

Beste Jan Willem,
Ik weet niet of u als wiskundige ook de meer filosofische discussie over de vrije wil volgt.
Zelf vind ik het jammer dat er hoe langer hoe meer een echte splitsing is tussen wiskunde en filosofie.
Vroeger hadden alle wiskundigen een filosofische opleiding en waren alle filosofen wiskundigen. Waar is het ideaal van de homo universalis gebleven?
Of om het met onze vriend Beeckman te zeggen:

Miranda est subtilitas rerum in rebus. [ Verwonderlijk is de fijnheid van dingen in de dingen.]
Want een dinck in een man, dat maer een aesken en weecht, en weecht qualick het 2413de deel van een aesken in een puero primum conformato. [... voor het eerst gevormd kind.]
Denckt hoe kleyn dat moet syn, ende denckt, hoe kleyn dat is datter alle ure aenwast totdattet so groot is als in een volwassen man.
Ita ut Anaxagorae sententia: "Omnia sunt in omnibus" mirabilior non esse videatur. [ Zo dat de mening van Anaxagoras: "Alle dingen zijn in alle dingen" niet zo zonderling meer lijkt.]

Het handelreizigersprobleem is hetzelfde als het probleem van de vrije wil Jan Willem (alle dingen zijn in alle dingen).
U mag van mij zelf het probleem formuleren en een definitie naar voor schuiven van alle woorden die u gebruikt.
Maar van zodra dat gebeurd is, dan is het weer aan mij.
Het is niet gebruikelijk dat de betekenis van een woord (passeren, bezoeken, of wat u ook moge verkiezen) binnen één en dezelfde redenering verandert.
De vraag die u wil stellen is een vraag waarin het antwoord besloten ligt.
Is de vrije wil vrij?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 23 jun 2011, 18:14

Het handelreizigersprobleem is hetzelfde als het probleem van de vrije wil ...
...
De vraag die u wil stellen is een vraag waarin het antwoord besloten ligt.
Is de vrije wil vrij?


Ik volg de discussie over de vrije wil helemaal niet, want daarover discussiëren lijkt me onzin. Ik kan wel uitleggen waarom ik dat vind, maar dat doe ik niet, want ook zo'n toelichting lijkt me op dovemansoren te zullen vallen.

Ik weet wel dat het handelsreizigersprobleem een tamelijk nauwkeurig omschreven wiskundig probleem of misschien groep van problemen is. Het heeft helemaal niets met de vrije wil te maken. (Of je je gaat inspannen om 'het handelsreizigersprobleem' op te lossen op de een of andere manier in plaats van buiten op een terrasje een biertje te gaan drinken is natuurlijk wel een kwestie van vrije wil, whatever that may be, maar daardoor verandert er niets aan wat wiskundigen in het algemeen bedoelen met het handelsreizigersprobleem).

Ik heb weinig vertrouwen in de filosofische kwaliteiten van iemand die mijn uitleg over drie soorten problemen die met een graaf geassocieerd kunnen worden niet kan volgen.

Ik wil helemaal geen vraag stellen, ik wil duidelijk maken wat wij wiskundigen onder een graaf verstaan (wil je een formele definitie
hebben, dat kan maar daar wordt het voor een leek niet helderder van), en wat wij wiskundigen onder 'het handelsreizigersprobleem' verstaan.

Of datgene wat doorgaans wordt aangeduid met de woorden 'vrije wil' een consistent begrip is of alleen maar de term voor een bepaald vaag gevoel, daar ga ik me niet verder over uitlaten. Het is net zo'n vraag, lijkt me, als 'is een ondoorzichtig spook ondoorzichtig'?
Laatst bijgewerkt door Jan Willem Nienhuys op 24 jun 2011, 00:11, in totaal 2 keer bewerkt.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 23 jun 2011, 19:00

Beste Jan Willem,

Laten we er een rechtszaak van maken!
Dat is niet mijn ding, maar het is helemaal het uwe.
Ofwel is iets juist ofwel is iets fout.
"Please answer the question with yes or no".
Ik neem aan dat u hier moeilijk principiële bezwaren kan tegen inbrengen.

Is het handelsreizigersprobleem één probleem of zijn het er drie?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 23 jun 2011, 19:03

oei, het is echt mijn ding niet !

Is het handelreizigersprobleem één probleem?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Dwarsdenker » 23 jun 2011, 22:22

johan bosmans schreef:Ofwel is iets juist ofwel is iets fout.

Leve het simplisme ?????
Wetenschap is gericht op het zoeken naar de best mogelijke verklaring.
Avatar gebruiker
Dwarsdenker
 
Berichten: 470
Geregistreerd: 01 jul 2009, 12:09

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 23 jun 2011, 23:05

Dwarsdenker schreef:
johan bosmans schreef:Ofwel is iets juist ofwel is iets fout.

Leve het simplisme ?????


Is de ene mening beter dan de andere mening????
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 24 jun 2011, 00:10

Is het handelsreizigersprobleem één probleem of zijn het er drie?


Zucht. Als de mensen die zich filosoof wanen, toch eerst eens leerden lezen. Ik heb drie verschillende probleemgroepen geschetst, ze voor de overzichtelijkheid genummerd 1, 2, 3 en nummer twee daarvan was het handelsreizigersprobleem, en de nummers 1 en 3 niet, die hadden dan ook andere namen. Ik heb daarna nog eens uitgelegd dat het om 3 (drie, 1+1+1) verschillende problemen ging.

Je zou probleemgroep 2 weer kunnen onderverdelen in diverse opgaven
a. zoek voor een gegeven graaf de allerkortste route.
b. bewijs dat er geen kortere route is.
c. ontwikkel een algoritme om voor een willekeurige graaf de kortste route te vinden
Voor dit probleem zijn uiteraard meerdere oplossingen, speciaal wanneer men gebruik kan
maken van extra gegevens, bijvoorbeeld dat de afstanden waar het om gaat allemaal euclidische afstanden in het platte vlak zijn.
d. ontwikkel een algoritme om voor een willekeurige graaf tamelijk vlug een route te vinden die dicht bij het theoretische minimum
zit.
e. Analyseer dit soort algoritmen in termen van gemiddelde rekentijd en rekentijd in het meest ongunstige geval.
...
Er zijn heel veel publicaties over dit theoretisch en praktisch belangrijke probleem, die uiteraard allemaal andere aspecten behandelen.

Nou niet meer van die domme vragen stellen asjeblieft, en niet gaan zitten trollen.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 24 jun 2011, 06:15

Zucht.
"Please answer the question with yes or no"

u schrijft dat het om drie verschillende problemen gaat.
en even verderop:
Er zijn heel veel publicaties over dit theoretisch en praktisch belangrijke probleem
Make up your mind.
Of misschien was de vraag iets te moeilijk.

Ik zal het iets gemakkelijker maken.
ik lees: "handelsreizigersprobleem"

Is "probleem" enkelvoud?

(laten we even voortmaken, het moet vooruit, want ik wil mijn krant lezen.
uitspraak over Geert Wilders!

Het handelsreizigersprobleem = probleem 2
je mag 2 keer in elk punt komen.
check dat maar eens goed na voor je weer antwoordt.)
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 24 jun 2011, 09:41

ik geef het toe, ik was een beetje korzelig vanochtend.
Ik zou mijn vorig post kunnen wijzigen, maar dat ga ik niet doen.
ik had het slecht gelezen omdat ik moest vertrekken en gehaast was.
Wie overkomt dat niet? Ik ben er alvast niet verlegen voor.

De kern van de zaak blijft overeind:
handelaarsprobleem = probleem 2.
je mag in dat geval twee keer in hetzelfde punt komen.

Mag je twee keer in hetzelfde punt komen?
(Als u nou even gewoon met ja of nee zou antwoorden zou het voor mij ook iets gemakkelijker zijn)

P.S. Why do you want to play? You are dead.
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 24 jun 2011, 21:02

je mag in dat geval twee keer in hetzelfde punt komen.

Mag je twee keer in hetzelfde punt komen?


Ja natuurlijk. Het gaat er alleen maar om dat de totale weg zo kort mogelijk is. Als je graaf bijvoorbeeld bestaat uit 100 punten op een cirkel plus het middelpunt, en 100 kanten heeft, allemaal verbindingen van dat middelpunt met een der andere punten (een ster dus) heb je weinig keus voor je pad: je moet heel vaak in het midden terugkomen.

Het probleem heet trouwens niet het handelsprobleem maar het handelreizigersprobleem.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 24 jun 2011, 21:12

Jan Willem Nienhuys schreef:
je mag in dat geval twee keer in hetzelfde punt komen.

Mag je twee keer in hetzelfde punt komen?


Ja natuurlijk. Het gaat er alleen maar om dat de totale weg zo kort mogelijk is. Als je graaf bijvoorbeeld bestaat uit 100 punten op een cirkel plus het middelpunt, en 100 kanten heeft, allemaal verbindingen van dat middelpunt met een der andere punten (een ster dus) heb je weinig keus voor je pad: je moet heel vaak in het midden terugkomen.

Het probleem heet trouwens niet het handelsprobleem maar het handelreizigersprobleem.


We spelen duidelijk niet hetzelfde spelletje.
http://www.tsp.gatech.edu//games/index.html
Kan je in dit spel twee keer naar hetzelfde punt?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 24 jun 2011, 23:45

Kan je in dit spel twee keer naar hetzelfde punt?


dat weet ik niet, dat moet je de maker van het spelletje maar vragen. Ik zie trouwens dat daar geen sprake is van een gegeven graaf. Waarschijnlijk is het idee dat het om de volledige graaf gaat met euclidische afstanden. Ik speel helemaal geen spelletje, ik beschrijf wat onder wiskundige de gangbare opvatting is van wat het met 'het handelsreizigersprobleem' bedoeld wordt, niet wat een spelletjesmaker daar van belieft te brouwen.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 24 jun 2011, 23:55

Jan Willem Nienhuys schreef: de maker van het spelletje


The work described here is supported by Office of Naval Research (N00014-09-1-0048) and National Science Foundation (CMMI-0726370) grants, and by the School of Industrial and Systems Engineering at Georgia Tech. Graduate students are directed to Operations Research at Georgia Tech. A good source for computational work on the traveling salesman problem and general optimization is the journal Mathematical Programming Computation.

Contact: William Cook (bico@isye.gatech.edu)

Mag ik in uw naam om verduidelijking vragen?
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 25 jun 2011, 11:21

Cook doet kennelijk onderzoek naar het TSP (Travelling Salesman Problem) , schrijft daar boeken over enzovoorts. De pagina

http://www.tsp.gatech.edu/

waar het citaat vandaan komt geeft een indruk. Maar het zou een misvatting zijn te denken dat 'hét TSP' uitsluitend bestaat uit dat didactisch bedoelde spel. In dat spel zijn de toegestane verbindingen waarschijnlijk alle rechte lijnen die er tussen punten te trekken zijn.

Onder zulke omstandigheden zal een kortste weg waarschijnlijk hetzelfde punt niet nog eens bezoeken omdat je door het punt over te slaan waarschijnlijk een nog kortere weg krijgt. Het is mogelijk dat er punten A, B, C op een rechte lijn liggen en dat er een kort pad is dat (nadat B al gepasseerd is en A en C niet) toch van A naar C gaat, zeg X -> B -> Y ->...(P)... -> A -> B -> C . Dan zijn er twee nog kortere paden namelijk X -> A -> ...(P')... -> Y -> B -> C en X -> B -> A-> ...(P')... -> Y -> C. Hier betekent P' hetzelfde deelpad als P maar in omgekeerde richting doorlopen. In beide gevallen wordt B een van de twee passges gewoon overgeslagen. Welk van deze twee alternatieven het kortste is, hangt van de precieze ligging van de punten af. Maar ze zijn allebei korter want in het platte vlak is nu eenmaal XB + BA meer dan XA tenzij XBA een rechte lijn is, en evenzo is YB + YC meer dan YC, tenzij YBC een rechte lijn is. Het geval dat A, B, X, Y, C in dit verhaal allemaal op één rechte lijn liggen laat ik verder als een extra puzzeltje, maar ik vermoed dat je kunt bewijzen dat in een zo kort mogelijk pad onder deze omstandigheden punten niet meer dan eenmaal aangedaan worden, tenzij er teveel punten op een rechte lijn liggen.

Een bijzonder geval is natuurlijk dat de eis luidt dat je een pad moet maken dat op het beginpunt uitkomt in combinatie met de situatie dat alle punten op een rechte lijn liggen (of, in het geval van een graaf, dat er punten zijn met graad 1, dus als je die wilt passeren moet je noodzakelijkerwijs weer terug langs de kant waarover je gekomen bent, zodat je het andere uiteinde van die kant nogmaals passeert; dat zal zich aan de westzijde van Zweden waarschijnlijk vaak voordoen, steden met maar één toegangsweg).

Een voorbeeld van een graaf zonder punten met graad 1 waarin toch een punt tweemaal gepasserd moet worden (voor een cyclisch pad) is ook eenvoudig: een figuur acht.

Het is niet eens uit te sluiten dat er paden zijn zonder dubbele passage, maar dat het kortste pad wel een dubbele passage heeft. Stel je maar een figuur acht voor, met een extra heel lange weg toegevoegd, die je kunt volgen om een dubbele passage te vermijden.

Ik vermoed dat de auteur van het spelletje ervoor zorgt dat de speler altijd punten in algemene ligging neerlegt, en netjes bewijst in het leerboek hoe het precies zit met de situatie van collineaire punten. Ik ben hierboven al begonnen met het bewijs, en ik heb al een idee over hoe je het ongeveer zou moeten afmaken, maar het is hier geen wiskundeles.

Samenvattend: in het TSP is er geen verbod op tweemaal passeren van hetzelfde punt. (Net zo min als er in het schaakspel een regel is dat zwart altijd met een pion moet spelen als hij kan; dat mag wel, maar als zwart dat doet is de partij vlug afgelopen.) In tal van praktische situaties kun je ofwel bewijzen dat bij het kortste pad hetzelfde punt niet tweemaal gepasseerd wordt, ofwel bewijzen dat er bij elk pad dat alle punten passeert er punten zijn die wel tweemaal gepasseerd moeten worden.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 25 jun 2011, 11:47

Jan Willem Nienhuys schreef:Samenvattend: in het TSP is er geen verbod op tweemaal passeren van hetzelfde punt.


Kan u mij een referentie geven van wat u beweert?

Behalve kennislink, wikipedia, cook geef ik u hier een vierde referentie die u formeel tegenspreekt:
http://iris.gmu.edu/~khoffman/papers/trav_salesman.html

"The traveling salesman problem (TSP) is one which has commanded much attention of mathematicians and computer scientists specifically because it is so easy to describe and so difficult to solve. The problem can simply be stated as: if a traveling salesman wishes to visit exactly once each of a list of m cities"
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 25 jun 2011, 15:21

Beste Jan Willem,

Ik hou het voor bekeken.
Ik heb niet gewonnen, ik kan niet winnen.
Maar ik kan niet verliezen.
Als u dat nu niet begrijpt zal u dat ook niet begrijpen als we hiermee doorgaan.
Het was me een genoegen, ik heb geleerd van mijn conversaties met u en met Heeck.

http://www.bloggen.be/excrementen/archi ... ID=1235689
Johan.
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 25 jun 2011, 18:25

Kan u mij een referentie geven van wat u beweert?


Is Wikipedia ( http://en.wikipedia.org/wiki/Travelling ... an_problem ) niet goed genoeg? Kijk naar de oorspronkelijke versie van Menger, die opmerkt dat het een probleem is dat elke postbode moet oplossen. Denk je dat een postbode niet aan zijn ronde begint als het wegenpatroon zo is dat hij tweemaal langs hetzelfde huis of dezelfde straathoek moet komen? In dezelfde Wikipedia nog veel meer versies van het probleem.

Een wiskundig probleem is niet zoiets als een spel met voorgeschreven regels (zoals vastgelegd door de internationale bridge- of dambond). Ik heb ook diverse malen gezegd dat het TSP eigenlijk een groep van op elkaar lijkende problemen is. Gemeenschappelijk aan al die problemen is: (1) langs alle punten komen (2) zo kort mogelijk.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Re: handelsreizigersprobleem

Berichtdoor johan bosmans » 26 jun 2011, 17:19

Jan Willem Nienhuys schreef:Is Wikipedia ( http://en.wikipedia.org/wiki/Travelling ... an_problem ) niet goed genoeg?


De eerste regel van de referentie die u mij bezorgt:
The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

Sorry Jan Willem, u hebt het verhaal niet goed begrepen.
Samson is de ongekroonde koning van de schaakcamping omdat hij geen enkele partij verliest, niet omdat hij ze allemaal zou winnen.
Als ik u remise aanbied is het de bedoeling dat u die aanvaardt.
Om de eenvoudige reden dat ik geen verlies aanvaard.
Als remise niet goed genoeg is voor u, dan is dat eerder uw probleem dan het mijne.
johan bosmans
 
Berichten: 236
Geregistreerd: 12 mei 2010, 22:06

Re: handelsreizigersprobleem

Berichtdoor Jan Willem Nienhuys » 26 jun 2011, 18:37

Het komt wel vaker voor dat wiskundigen lichtelijk verschillende definities geven. Zo vindt men in tal van leerboeken ergens op pagina 1 staan dat de natuurlijke getallen beginnen bij 0 (0, 1, 2, 3, ... ) en in tal van andere leerboeken dat de natuurlijke getallen beginnen bij 1 (1, 2, 3, ...)

In die referentie wordt vervolgd met:

The problem was first formulated as a mathematical problem in 1930

en dat is een verwijzing naar Mengers formulering: 'We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points....'

Daar staat niets in over ten hoogste 1 maal per punt.

In veel formuleringen zie je inderdaad staan dat het er om gaat een Hamilton-pad van kortste lengte te maken, en vaak ook dat het om een complete graaf gaat (waarin desnoods sommige kanten zo lang zijn dat ze onmogelijk in het kortste pad kunnen voorkomen). In een complete graaf heeft het zin om aan te nemen dat er een driehoeksongelijkheid geldt: bij elk drietal punten A B C is direct van A naar B gaan altijd korter dan via C.

Als die driehoeksongelijkheid niet geldt dan kun je rare situaties krijgen. Stel je even een rechthoek ABCD met diagonalen voor die elkaar in het centrum E snijden. We nemen aan dat de weglengtes AE, BE, CE, DE allemaal 1 zijn, evenals de korte rechthoekszijden AB en CD.

Dan is een kort circuit: A->B->E->D->C->E->A, lengte 6. Als de driehoeksongelijkheid geldt, bestaat er een nog korter circuit namelijk door van C direct naar A te gaan in plaats van via E.

Maar als alle niet genoemde verbindingen allemaal lengte 10 hebben, dan heeft het kortste Hamilton-pad lengte 14. De ene practicus zal zeggen: 'Hamiltonpad kan me niets schelen, ik wil de kortste weg vinden'. De andere practicus zal zeggen: 'In de praktijk geldt de driehoeksongelijkheid altijd, dus dit voorbeeld is slechts theoretisch'. De eerste practicus zal zeggen dat de driehoeksongelijkheid lang niet altijd geldt in de praktijk. De derde practicus zal wellicht zeggen dat het voor machinale algoritmen en de theorie handiger is om de conditie 'Hamilton-pad' toch maar te handhaven. Dan kun je bijvoorbeeld exact aangeven hoeveel mogelijke paden er zijn (namelijk (n-1)-faculteit) waarvan je de kortste moet uitzoeken. De vierde practicus zal opperen dat als alle punten op een rechte lijn liggen, je er niet aan ontkomt dat je voor een rondreis langs alle plaatsen de plaatsen meerdere malen worden aangedaan. De vijfde practicus zal opperen dat een echte handelsreiziger een stad waar hij gewoon doorheen kan rijden zonder te stoppen niet meetelt als een stad waar hij geweest is (dat is dus een forcering van de diehoeksongelijkheid in een complete graaf).

Van mij mogen ze allemaal. Iedereen moet maar definiëren wat-ie onder het probleem verstaat; de meesten eisen inderdaad de Hamilton-conditie en wel in een volledige graaf. De essentie is echter dat het om het kortste pad gaat. De rest is franje volgens de persoonlijke smaak van de onderzoeker.
Jan Willem Nienhuys
 
Berichten: 787
Geregistreerd: 09 dec 2007, 11:09
Woonplaats: Waalre, Nederland

Volgende

Keer terug naar Wetenschap

Wie is er online

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