Handelsreizigersprobleem

[Th.B]

Ik moet zeggen dat ik nu toch wel sta te springen om dat PDF-je. Hoeveel voorkennis over dat handelsreizigersprobleem heb ik nodig om je oplossing te kunnen bevatten? Ik wil me er best even in verdiepen, als dat mijn mate van begrip voor jouw voorgestelde bewijs bevordert.

[Esthetisch]

Geloof me ik sta zelf ook te springen om misschien wel 100 dingen te zeggen die allemaal door m'n hoofd spelen. Maar het is zaak nu niet te vroeg te juichen.

Voorkennis heb je denk ik niet nodig, die had ik zelf ook niet echt, maar het document beperkt zich wel puur tot het handelsreizigersprobleem en gaat dus niet dieper in op P = NP. Ik weet ook zeker dat er anderen zijn die dat veel beter kunnen dan ik.

[Esthetisch]

Aangezien ik met een mobiel geen PDF kan plaatsen:

Morgenochtend 09:00 staat het er op.

Enige uitzondering is als ik voor die tijd al reactie krijg van 2 hoogleraren van de TU waar ik het zojuist naar ge-emaild heb. Maar reken daar maar niet op.

[Esthetisch]

Voila.

[Th.B]

Dat 'foutje' is dat je 108 moest kiezen

Dit is even een snelle reactie op die opmerking en ik vind wel dat je uiteindelijke uitkomst bij het voorbeeld er veelbelovend uitziet... ik heb nog niet heel het document aandachtig doorgenomen.

[Math-E-Mad-X]

Ik zal er naar kijken zodra ik tijd heb.

[Esthetisch]

Ik zal er naar kijken zodra ik tijd heb.

Dat zou erg fijn zijn, ik ben erg benieuwd naar wat u (en anderen) van het algoritme denken.

[Math-E-Mad-X]

Ik heb em even heel vluchtig doorgekeken en heb 'de manier' nog niet helemaal begrepen. Maar goed, het lijkt er op dat je bij stap 3 van je algoritme, waar je losse routes aan elkaar koppelt, een soort van nearest neighbor approach toepast op de losse routes. Dit levert helaas niet de kortste route op:

http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm

Weliswaar heeft deze wiki-pagina het over steden die aan elkaar gekoppeld worden, terwijl jij het hebt over routes die aan elkaar gekoppeld worden, maar dat is bijna hetzelfde.

Je kunt je bijvoorbeeld voorstellen dat je een aantal clusters van steden hebt, waarbij de steden binnen elke cluster heel dicht bij elkaar liggen, terwijl de clusters zelf heel ver uit elkaar liggen. De routes die jij in je eerste twee stappen vindt zullen dan elk binnen zo'n cluster liggen, en stap 3 probeert dan de kortste route tussen deze clusters te vinden. In feite pas je dan bovenstaande 'nearest neighbor algorithm' toe, alleen op de clusters in plaats van op individuele steden.

[Math-E-Mad-X]

Overigens bedenk ik me nu ineens dat er sowieso iets geks aan jouw algoritme is: volgens mij kun je stappen 1 en 2 namelijk gewoon overslaan. Of, beter gezegd: ALS jouw algoritme de kortste route oplevert, dan zal het toepassen van enkel Stap 3 dat ook doen.

Stel we hebben een handelsreizigersprobleem A dat bestaat uit n steden die elk, laten we zeggen, enkele centimeters uit elkaar liggen. Nu kunnen we een nieuw probleem A' creeren door iedere stad te vervangen door twee steden die heel erg dicht bij elkaar liggen (laten we zeggen een micrometer). We hebben dan dus n clusters van elk twee steden. Nu passen we jouw algoritme toe op A'. Na de eerste twee stappen zullen we dan n routes hebben: elke route verbindt de twee steden binnen één cluster. Stap 3 zal dan deze n clusters op de kortst mogelijke manier aan elkaar proberen te koppelen. Maar omdat de afstanden binnen één cluster extreem klein zijn, komt dat feitelijk op precies hetzelfde neer als het vinden van de oplossing voor probleem A.

Oftewel: het toepassen van stappen 1 2 en 3 op A' geeft hetzelfde resultaat als het toepassen van alleen stap 3 op A. En omdat de kortste route van A' praktisch hetzelfde is als de kortste route van A heb je dus feitelijk A opgelost met alleen maar stap 3.

[Esthetisch]

Ik heb em even heel vluchtig doorgekeken en heb 'de manier' nog niet helemaal begrepen. Maar goed, het lijkt er op dat je bij stap 3 van je algoritme, waar je losse routes aan elkaar koppelt, een soort van nearest neighbor approach toepast op de losse routes. Dit levert helaas niet de kortste route op:

http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm

Weliswaar heeft deze wiki-pagina het over steden die aan elkaar gekoppeld worden, terwijl jij het hebt over routes die aan elkaar gekoppeld worden, maar dat is bijna hetzelfde.

Je kunt je bijvoorbeeld voorstellen dat je een aantal clusters van steden hebt, waarbij de steden binnen elke cluster heel dicht bij elkaar liggen, terwijl de clusters zelf heel ver uit elkaar liggen. De routes die jij in je eerste twee stappen vindt zullen dan elk binnen zo'n cluster liggen, en stap 3 probeert dan de kortste route tussen deze clusters te vinden. In feite pas je dan bovenstaande 'nearest neighbor algorithm' toe, alleen op de clusters in plaats van op individuele steden.

Ik beperk me in mijn uitspraken even puur tot het algoritme uit stap 3:

Het is logisch dat het nearest-neighbor-algortime niet altijd de beste oplossing geeft. Er is daar sowieso al sprake van een verschil tussen een route en een weg, oftewel tussen punten en clusters. Je past je route aan door een weg toe te voegen. En bij wijze van spreke een punt met een cluster te verbinden. Dan wordt het ronduit gokken in welke volgorde je de wegen moet nemen. En waar je moet beginnen.

Wat je dan nog wel zou kunnen proberen is de bestaande route telkens in z’n volledigheid aan passen aan het volgende punt, maar dan krijg je dus bij de laatste stap n^n mogelijkheden. (Behalve dan wanneer dit weet te beperken, door bijvoorbeeld gebruik te maken van Dijkstra, maar ik zou nu zo 123 niet weten hoe dan, want je voegt steeds nieuwe wegen toe in plaats van dat je ze slechts aan past. Je zou dus onnodig voor een omweg kunnen kiezen.)

Overigens: door dat toevoegen van nieuwe wegen aan de bestaande route heb je ook eigenlijk pas bij je allerlaatste stap je allereerste informatie over de ‘totale afstand’. Das vrij laat. Bij het algoritme zoals hier gepost is die totale afstand juist hetgeen waar het echte rekenwerk feitelijk mee van start gaat. Eigenlijk houdt dat nearest-neigbor-algoritme zo’n beetje op waar dit algoritme begint.

Wat betreft je bericht:

Bij het algoritme zoals hier gepost verbindt je twee bestaande routes. Maar daar houdt het niet mee op. Het kan (in theorie) best zo zijn dat beide routes bij hun onderlinge verbinding vrijwel in z’n geheel opnieuw worden opgebouwd tot een totaal andere route. Je voegt niets toe, en je verbindt dus eigenlijk niet eens twee routes, maar je maakt van 2 kortste gesloten routes 1 kortste gesloten route. En dat is het belangrijke verschil.

Bovendien verbindt je dus niet, zoals bij het nearest neigbor-algoritme, een route met een punt, en dan met het volgende punt, en dan met het volgende punt. Je verbindt een route met een route. En de route die daaruit volgt (of een andere), verbindt je opnieuw met een route. Van punten is nergens sprake. Nu zou je hier normaal geproken net zo goed nog 1/3n^n opties voor nodig hebben, zij het niet dat je nu door het gebruik van Dijkstra dit aantal wel kan beperken. De conclusie lijkt me dan duidelijk.

Vanaf nu weer over het algoritme in z’n totaliteit.

Overigens bedenk ik me nu ineens dat er sowieso iets geks aan jouw algoritme is: volgens mij kun je stappen 1 en 2 namelijk gewoon overslaan. Of, beter gezegd: ALS jouw algoritme de kortste route oplevert, dan zal het toepassen van enkel Stap 3 dat ook doen.

Stel we hebben een handelsreizigersprobleem A dat bestaat uit n steden die elk, laten we zeggen, enkele centimeters uit elkaar liggen. Nu kunnen we een nieuw probleem A' creeren door iedere stad te vervangen door twee steden die heel erg dicht bij elkaar liggen (laten we zeggen een micrometer). We hebben dan dus n clusters van elk twee steden. Nu passen we jouw algoritme toe op A'. Na de eerste twee stappen zullen we dan n routes hebben: elke route verbindt de twee steden binnen één cluster. Stap 3 zal dan deze n clusters op de kortst mogelijke manier aan elkaar proberen te koppelen. Maar omdat de afstanden binnen één cluster extreem klein zijn, komt dat feitelijk op precies hetzelfde neer als het vinden van de oplossing voor probleem A.

Oftewel: het toepassen van stappen 1 2 en 3 op A' geeft hetzelfde resultaat als het toepassen van alleen stap 3 op A. En omdat de kortste route van A' praktisch hetzelfde is als de kortste route van A heb je dus feitelijk A opgelost met alleen maar stap 3.

je redenatie kan ik eerlijk gezegd niet helemaal volgen, behalve dat ik wel weet dat je 3 punten met een micrometer zult moeten kiezen anders geldt het sowieso al niet, maar okay. Over je conclusie kan ik alleen maar zeggen dat je dat heel goed gezien hebt. Ongeveer het hele algoritme komt ook in stap 3 terug, met de handelingen die in stap 3 aan bod komen kun je heel het algoritme uitvoeren.

Toch is het de vraag of je de rest dan ook gelijk weg kunt laten. Stap 1 heb je op 1 of andere manier natuurlijk altijd wel nodig, anders heb je geen (laagste) beginsituatie. Stap 2 zou je dan kunnen zien als een ‘omwerking’ kunnen zien om stap 3 te kunnen uitvoeren.

Maar Wat je dus eigenlijk zegt is:

- je kunt beginnen met lukraak een situatie te kiezen, zolang er maar geldt dat er in elke kolom en elke rij 2 vakjes gevuld zijn.

- vervolgens hoef je dan alleen nog stap 3 uit te voeren.

Sowieso ben ik je erg dankbaar, want door hierover na te denken heb ik nog een ‘schoonheidsfoutje’ in het algoritme ontdekt*. Maar daarnaast is het de moeite waard om dit beter te bekijken. Misschien is dit wel een hele bruikbare optimalisatie om het maar zo te zeggen. Waar ik dan alleen een beetje tegenaan hik (en eigenlijk ook al eens tegenaan gehikt heb):

Hoe weet je dan wanneer je moet stoppen met stap 3, en dat je echt de allerlaagste optie hebt? Je kiest immers lukraak een beginsituatie, en vervolgens ga je dan een foutje aanbrengen. Wat als bij je begin situatie alle punten al in 1 route liggen? Dan moet je zomaar lukraak een foutje kiezen. Dat kan best, maar wanneer weet je dan dat je hiermee moet ophouden en de kortste route hebt gevonden? En is dat snel genoeg? Stof tot nadenken dus. Het zou goed kunnen dat er een manier is waarop je gelijk hebt.

* Het Dijkstra-algoritme werkt niet met negatieve getallen. Alle afstanden moeten groter zijn dan 0.

TOEVOEGEN:

Wat je dus moet doen voordat je met 'de tabel voor Dijkstra' daadwerkelijk het algoritme van Dijkstra gaat uitvoeren, is de laagste waarde, dus de grootste negatieve waarde uit de ‘tabel voor Dijkstra’ bepalen, en vervolgens bij alle waarden uit die tabel die ‘negatieve waarde + 1’ optellen.

Achteraf moet je dan het aantal hokjes dat bij de bewerking binnen de tabel van dijkstra betrokken is, oftewel het aantal wegen dat je bij wijze van spreken moet nemen, vermenigvuldigen met die ‘negatieve waarde + 1’ en de uitkomst aftrekken van de verkregen kortste route uit de tabel van Dijkstra, voordat je hem bij een losse afstand uit de normale tabel gaat optellen of aftrekken bij bijvoorbeeld ‘de manier 3a, 3b of bij de directe weg bij ‘verbinden van de losse routes’).

[Esthetisch]

* Het Dijkstra-algoritme werkt niet met negatieve getallen. Alle afstanden moeten groter zijn dan 0.

TOEVOEGEN:

Wat je dus moet.....

Dit was iets te kort door de bocht. Je vindt op deze manier namelijk niet altijd de juiste kortste weg.

Hoe het denk ik wel zou kunnen is m.b.v. het Bellman Ford algoritme.

Dit het een uitgebreidere versie van het algoritme van Dijkstra. Op wiki staat:

Bellman–Ford runs in O(|V|·|E|) time, where |V| and |E| are the number of vertices and edges respectively.

Wat me vrijwel hetzelfde lijkt als v in kwadraat. Dus dan zou deze manier ook niet noemenswaardig meer tijd in beslag hoeven nemen. Gelukkig maar.

[Math-E-Mad-X]

Ik probeer je pdf nogmaals door te lezen, maar vind het er lastig te lezen (en ik ben wiskundige, dus ik ben het gewend om wiskundige teksten te lezen).

Ten eerste omdat je het hebt over 'de afstand van een rij tot een kolom'. Wat je in feite bedoeld is de afstand van een stad tot een andere, wat een stuk duidelijker voor te stellen is. Ik denk dat je verhaal sowieso een stuk duidelijker zou zijn als het zou uitleggen in termen van steden en wegen tussen steden in plaats van over rijen en kolommen. Het zal voor geen enkele wiskundige of programmeur moeilijk zijn om te begrijpen dat dit dan vervolgens kunt implementeren met behulp van rijen en kolommen.

Eventueel kun je zelfs iedere stap op beide manieren uitleggen. En het zou helemaal geweldig zijn als je er ook nog plaatjes bij kunt zetten waarbij je tekent hoe het algoritme stap voor stap een pad creeert tussen een stel steden. Dan kan een heel simpel voorbeeld zijn om het principe duidelijk te maken, en kun gewoon met bijvoorbeeld windows paint doen.

[Math-E-Mad-X]

Verder heb ik een hele belangrijke tip voor je: probeer bij het schrijven van wiskundige teksten zo min mogelijk verwijswoorden te gebruiken ('deze', 'die' etc..) en in plaats daarvan namen te geven aan de objecten waar je naar verwijst. Zeker als je vier verwijswoorden in één zin gebruikt zoals hieronder wordt het al gauw onduidelijk. De namen mogen gewoon letters zijn, zoals rij X, kolom Y etcetera. Dus in plaats van 'deze rij' is het beter om te zeggen 'rij X'.

Zie bijvoorbeeld deze (voor mij onbegrijpelijke) zin:

bepaal voor een rij binnen de groep zijn kortste weg naar een rij buiten de groep. Controleer

hiervoor dus de twee gevulde vakjes in de betreffende rij, en trek deze af van de vakjes in dezelfde

kolom van de desbetreffende andere rij buiten de groep.

Zo is het bijvoorbeeld onduidelijk naar welke rij je verwijst wanneer je zegt 'de betreffende rij'. Dit komt omdat je in de voorgaande zin twee rijen noemt.

Verder heb je het over 'dezelfde kolom' terwijl je helemaal nergens anders een kolom noemt.

Bovendien zeg je dat je twee vakjes van twee andere vakjes aftrekt. Wat bedoel je met een vakje van een ander vakje aftrekken?

[Esthetisch]

Ik probeer je pdf nogmaals door te lezen, maar vind het er lastig te lezen (en ik ben wiskundige, dus ik ben het gewend om wiskundige teksten te lezen).

Ten eerste omdat je het hebt over 'de afstand van een rij tot een kolom'. Wat je in feite bedoeld is de afstand van een stad tot een andere, wat een stuk duidelijker voor te stellen is. Ik denk dat je verhaal sowieso een stuk duidelijker zou zijn als het zou uitleggen in termen van steden en wegen tussen steden in plaats van over rijen en kolommen. Het zal voor geen enkele wiskundige of programmeur moeilijk zijn om te begrijpen dat dit dan vervolgens kunt implementeren met behulp van rijen en kolommen.

Eventueel kun je zelfs iedere stap op beide manieren uitleggen. En het zou helemaal geweldig zijn als je er ook nog plaatjes bij kunt zetten waarbij je tekent hoe het algoritme stap voor stap een pad creeert tussen een stel steden. Dan kan een heel simpel voorbeeld zijn om het principe duidelijk te maken, en kun gewoon met bijvoorbeeld windows paint doen.

Ik snap wat je bedoelt. Autocad prefereer ik omdat je dan gelijk ziet wat de afstand is.

Misschien dat ik in het document de termen steden en kolommen/rijen door elkaar heb gehaald, maar er is dus wel een belangrijk verschil tussen die 2 termen:

- een weg van stad naar stad is 1 vakje in de tabel. Dus 1 weg die bij 2 steden hoort.

- een weg van rij naar rij is het verschil tussen twee vakjes in de tabel. Dit zijn dus eigenlijk 2 wegen bij 1 punt. (En het verschil tussen de vakjes is het verschil tussen die 2 wegen)

Zie ook daarvoor de opmerking in het rood bij de samenvatting. Het is extreem belangrijk dat goed in de gaten te houden, anders werk het algoritme natuurlijk voor geen meter. Maar ik zal je opmerking bij de verbeterde versie zeker nog een keer goed nakijken.

De afgelopen dagen ben ik vooral begonnen aan een vertaling en een (uitgebreid) voorbeeld van stap 3. Daaruit kwam uiteindelijk ook naar boven dat je het Dijkstra algoritme moet vervangen voor het bellman ford algoritme. Toen ging ik me daar weer op concentreren, nu moet ik dat bellman algoritme weer even onder controle krijgen, en moet het voorbeeld van stap 3 dus weer worden aangepast/opnieuw gemaakt. Op die manier maak ik dus zeker stappen om nog (nodige) verbeteringen door te voeren, maarja... dat kost tijd.

Omdat de essentie in waarom je via dit algoritme het verschil kan maken wel zo'n beetje moet kloppen besloot ik het, ook door de vragen van forumgebruikers, toch maar gewoon te delen, het ECHTE werk is al geschied. Nu is het nog een kwestie van bijschaven.

Ik hoopte dan eigenlijk ook nog wel op wat meer reacties en meningen of bijdragen, want sowieso kan ik die input goed gebruiken. Zeker van mensen die veel meer thuis zijn in de wetenschap dan ik. Als je denkt te kunnen helpen, schroom dan niet. Nee heb je en ja kun je krijgen.

[Esthetisch]

...

Ik begrijp de boodschap ja, het vergt nu soms erg veel aandacht om de zin goed te kunnen lezen. Het voorbeeld van stap 3 zal daar wel bij helpen, maar daar heb je nu natuurlijk niets aan.

Als er echt een stukje is dat je niet begrijpt, kun je dat dan nogmaals aangeven? Want ik neem aan dat het deel waar je naar verwees slechts als voorbeeld was bedoeld?