Handelsreizigersprobleem

[Esthetisch]

Ik ben er al achter. Mocht het iemand wat boeien het antwoord op alle 3 de vragen is 'ja'.

[Esthetisch]

Een iets aangepaste versie van het probleem. Stel nu dat je een verzameling punten hebt, en je wil voor ieder punt weten wat de snelste route is naar ieder ander punt. Je hoeft ze dus niet allemaal af te leggen, maar het mag wel, als je maar zo min mogelijk 'kilometers maakt' om van A naar B (of C of D of E) te komen.

Is er iemand bekend met dit probleem? Hoeveel berekeningen moet je uitvoeren om voor ieder punt alle kortste wegen naar alle andere punten te bepalen?

[Esthetisch]

Laatste vraag:

Ik heb (geloof ik) een algoritme dat werkt met een snelheid n^8. Alleen vind je hiermee niet zozeer de aller kortste route, maar wel altijd de kortste route waarmee je weer bij het startpunt uitkomt.

Kan men hier iets mee of is dit niets nieuws onder de zon?

[EvilBro]

Ik denk dat het vinden van de kortste route langs alle punten waarbij jouw begin- en eindpunt gelijk is een NP-complete probleem is. Als jouw algoritme inderdaad n^8 is dan zou je het P-NP probleem hebben opgelost. Dit acht ik niet heel waarschijnlijk. Ik vermoed dus dat of jouw algoritme niet doet wat jij denkt dat het doet of de snelheid niet n^8 is.

[Esthetisch]

Die kritiek / twijfels zijn terecht, die heb ik ook, maar niet bij de geldigheid en werkzaamheid van het algoritme, dat kan ik denk ik zelfs nog wel bewijzen (maar de vraag is natuurlijk of anderen dat bewijs accepteren). Wel bij de vraag of dit probleem nu net zo moeilijk is als het originele handelsreizigersprobleem, want het algoritme dat ik valt niet zo 123 daarnaar om te bouwen (wat ik uiteraard wel getracht heb te doen).

[Marko]

Laten we eerst maar eens bij het begin beginnen: Hoe steekt dat algoritme in elkaar?

[Esthetisch]

Zodra ik zeker weet dat je hiermee p=np aan kunt tonen, is het eerst wat ik doe m'n werk verlaten en het clay math institute opbellen. Ik kan het dan ook wel hier droppen maar daar gaat ook wel wat tijd in zitten dus liever zou ik eerst met zekerheid zien dat het probleem in dezelfde moeilijkheidsgraad zit.

[Esthetisch]

Is dit niet het Hamilton-Path tegenover het Hamilton cycle probleem? Op de Engelse wiki staat daarover namelijk dat een pad berekenen niet significant langer kan duren dan de volle cirkel.

[Marko]

Om met de woorden van Jan-Peter Balkenende te spreken: "U draait en u bent niet eerlijk".

[Esthetisch]

En waarom dan wel?

[Marko]

Je komt met een vraag over een bepaalde casus. Je vraagt anderen om een uitspraak over die casus, maar laat daarbij verder niets los over de feitelijkheden.

Vervolgens wordt gevraagd of je meer duidelijkheid kunt verschaffen, en dan geef je niet thuis. Dat vind ik niet helemaal eerlijk in de richting van diegenen die gevraagd worden om een uitspraak te doen.

Je beweert dat je een algoritme hebt dat iets doet, maar laat niet zien dat het dat doet. Sterker nog, je wil niet eens schetsen hoe het er in grote lijnen uitziet. Daarmee lijkt het alsof je eerst iets beweert en daar later op terugkomt, "draaien" dus.

Je stelt dat een ander geen twijfel mag hebben over de juiste werking ervan, maar wetenschap is juist gefundeerd op twijfel en vooral: op het toetsen van de juistheid van zaken.

[317070]

Bij deze dus. Als je je wil bewijzen: http://www.math.uwaterloo.ca/tsp/data/

Of deze: http://www.math.uwaterloo.ca/tsp/data/usa/img/usa115475_large.jpg

http://www.math.uwaterloo.ca/tsp/data/usa/usa115475.tsp

Het wereldrecord bij die laatste staat op 6204999

[Esthetisch]

Bij deze dus. Als je je wil bewijzen: http://www.math.uwaterloo.ca/tsp/data/

Of deze: http://www.math.uwaterloo.ca/tsp/data/usa/img/usa115475_large.jpg

http://www.math.uwaterloo.ca/tsp/data/usa/usa115475.tsp

Het wereldrecord bij die laatste staat op 6204999

Helaas kan ik niet programmeren dus dat wordt lastig.

Overigens moet ik zeggen dat ik echt schijtziek wordt van deze wereld. Dit is niet het eerste wiskundige probleem wat ik op heb gelost, maar wederom: met dat clay math institute krijg ik totaal geen contact als ik mail of bel en dat was bij dat vorige bewijs ook al het geval met zo'n andere instantie. Zitten we hier nou echt met z'n allen in 1 grote façade en willen ze de antwoorden helemaal niet weten of hoe zit dat????

[EvilBro]

Wat staat je dan in de weg om hier het algoritme en het bewijs te posten?

[317070]

Overigens moet ik zeggen dat ik echt schijtziek wordt van deze wereld. Dit is niet het eerste wiskundige probleem wat ik op heb gelost, maar wederom: met dat clay math institute krijg ik totaal geen contact als ik mail of bel en dat was bij dat vorige bewijs ook al het geval met zo'n andere instantie. Zitten we hier nou echt met z'n allen in 1 grote façade en willen ze de antwoorden helemaal niet weten of hoe zit dat????

Omdat dat nu eenmaal niet de manier is waarop de wetenschappelijke wereld werkt...

Je publiceert je resultaten, en komt door de fase van peer-review en kritisch onderzoek van de andere wetenschappers naargelang je meer en meer interesse opwekt omdat het moeilijker en moeilijker blijkt te zijn om je theorie te weerleggen. Uiteindelijk ontstaat gaandeweg (na een jaar of twee) de consensus in de wetenschappelijke wereld dat je het toch maar eens bij het rechte eind zou kunnen hebben, wat helemaal niemand verwacht had. Dan nemen de mannen van die instanties uiteindelijk wel contact met je op als ze vinden dat je het verdiend hebt.

Dat is niet enkel voor jou zo, maar ook voor de minder begaafde zielen van deze wereld.

Ook, ze hebben waarschijnlijk op die instanties ook een crackpot-index liggen. http://primes.utm.edu/notes/crackpot.html

Je kunt daar maar beter niet te hoog op scoren.