Handelsreizigersprobleem

[Math-E-Mad-X]

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?

Nou, dat stukje wat ik citeerde snap ik dus echt niet. Het zou handig zijn als je het kon uitleggen in termen van steden en wegen.

Overigens: sorry als ik moeilijk doe, maar zo gaat dat nou eenmaal met wiskundige teksten. Ik moet als PhD-student ook vaak wiskundige artikelen schrijven, en het komt er op neer dat je eindeloos dingen moet herschrijven en herhalen, om je tekst begrijpelijk te maken voor anderen. Je krijgt het gevoel dat anderen je tekst niet goed lezen, of hun best niet doen, maar dat komt omdat jij zelf gewoon veel meer tijd aan het probleem hebt besteed en het dus veel beter begrijpt wat je zelf bedoeld. Dat is vervelend, maar dat hoort er nou eenmaal bij

Bovendien dwingt het je om zelf beter over je eigen werk na te denken wat ook tot een beter inzicht bij jezelf kan leiden.

[Esthetisch]

Nou, dat stukje wat ik citeerde snap ik dus echt niet. Het zou handig zijn als je het kon uitleggen in termen van steden en wegen.

Nogmaals: als je je beperkt tot steden en wegen komt je er niet. Er moet een verschil zijn tussen de afstanden(wegen) tussen steden, en de afstanden tussen rijen in de tabel dus, dus de verschil tussen de verschillende wegen van 1 stad. Ik hoop dat je dat begrijpt.

Wat betreft de verduidelijking:

Ik noem een vakje (Z, 0) wat betekent dat het het vakje is op de kruising van rij Z en kolom 0. Dat vakje representeert een bepaalde afstand.

Komt die:

Bepaal voor een rij A (die zich binnen een bepaalde groep bevindt) de weg naar rij B (die zich buiten de groep bevindt)

neem hiervoor de gevulde vakjes in rij A, dat zijn bijvoorbeeld de vakjes (A, 1) en (A, 3)

En neem hiervoor de lege vakjes in rij B die zich in dezelfde kolommen bevinden als de gevulde vakjes in rij A., dat zijn dus de vakjes (B, 1) en (B, 3)

doe vervolgens (B, 1) min (A, 1) & (B, 3) min (A, 3). dat geeft twee waarden. neem de laagste.

[Math-E-Mad-X]

Wat betreft de verduidelijking:

Ik noem een vakje (Z, 0) wat betekent dat het het vakje is op de kruising van rij Z en kolom 0. Dat vakje representeert een bepaalde afstand.

Komt die:

Bepaal voor een rij A (die zich binnen een bepaalde groep bevindt) de weg naar rij B (die zich buiten de groep bevindt)

neem hiervoor de gevulde vakjes in rij A, dat zijn bijvoorbeeld de vakjes (A, 1) en (A, 3)

En neem hiervoor de lege vakjes in rij B die zich in dezelfde kolommen bevinden als de gevulde vakjes in rij A., dat zijn dus de vakjes (B, 1) en (B, 3)

doe vervolgens (B, 1) min (A, 1) & (B, 3) min (A, 3). dat geeft twee waarden. neem de laagste.

Ha kijk! Als je het op zo'n manier uitlegt wordt het gelijk 100 keer duidelijker!

Ik zou zeggen: ga zo door en probeer het hele stuk op die manier te schrijven.

[Esthetisch]

Is er iemand die een beetje kan programmeren en wellicht een steentje bij wil dragen? Er is nog 1 mogelijk *** waar ik tegenaan loop, en dan misschien wel een oplossing voor heb, maar helemaal zeker weten doe ik dat niet. Als iemand er een paar kan na rekenen of dat desnoods door mijzelf laat doen, is dat snel genoeg duidelijk, de situatie waar het probleem op zal treden is vrij makkelijk na te bootsen. Hopelijk is de uitslag dan positief, dan is die echt definitief rond. Dat zou toch wel erg leuk zijn.

[317070]

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.

Ik wil dat wel even programmeren en je dan zeggen waar je de mist in gaat, maar ik heb je document proberen te lezen, en zoals Math-E-mad-X al zei, begrijp ik er helaas nog te weinig van. Het is niet duidelijk genoeg geschreven om overal te snappen wat je wil zeggen.

[Esthetisch]

Ik wil dat wel even programmeren en je dan zeggen waar je de mist in gaat, maar ik heb je document proberen te lezen, en zoals Math-E-mad-X al zei, begrijp ik er helaas nog te weinig van. Het is niet duidelijk genoeg geschreven om overal te snappen wat je wil zeggen.

Dat is erg fijn om te horen. Mij persoonlijk lijkt het me het beste zsm ergens een keer een dag af te spreken, direct contact werk toch vaak het snelste. Als u hier niet voor open staat kan het ook prima via dit forum, maar dan gaat het wel waarschijnlijk nogal wat tijd kosten.

Het eventuele(!) foutje zit pas in stap 3 dus stap 1 en 2 moeten dan al voltooid zijn.

Nu zijn stap 1 en 2 tezamen volgens mij ook al een nieuw algoritme wat je zo op je naam kan zetten, bovendien weet ik zeker dat dat gedeelte klopt. Dus iets bereikt is er sowieso al. Misschien is dan het goed om eerst die stap 1 en 2 in een vat te gieten. Dat is dan dus een algoritme om de kortst mogelijke situatie te bepalen waarbij elk punt met 2 anderen is verbonden.

Zodra we daar zijn kan het eventuele foute in stap 3 worden gezocht.

Maargoed laten we maar gewoon beginnen: begrijp je stap 1? Gaat het lukken zo'n tabel te generenen als aan het eind van stap 1 gewenst is? Zo nee, waar gaat het dan fout?

[Esthetisch]

Zie hier de manier. Ik ben erg benieuwd of het zo wel lukt.

[Math-E-Mad-X]

Ok, ik geloof dat ik stap 2 door heb (althans, scenario 1, de andere twee scenario's heb ik nog niet bekeken). Maar het komt er dus op neer dat je na afloop van deze stap voor iedere stad twee uitgaande pijlen hebt en twee inkomende pijlen (oftewel: iedere kolom heeft twee gevulde vakjes en iedere rij heeft twee gevulde vakjes). Maar de inkomende pijlen hoeven niet samen te vallen met de uitgaande pijlen (de matrix is niet symmetrisch t.o.v. de diagonaal). Iedere stad kan dus in principe met 4 verschillende andere steden direct verbonden zijn.

Dat is anders dan wat ik eerst had begrepen. Ik dacht namelijk dat iedere stad met slechts 2 andere steden direct verbonden zou zijn (diagonaal-symmetrische matrix) en dat zal uiteindelijk ook het geval moeten zijn natuurlijk.

Of heb ik ergens overheen gelezen?

Overigens snap ik ook niet helemaal waarom je het Bellman-ford algoritme nodig hebt. In principe zijn alle afstanden altijd positief, dus zou je met Dijkstra moeten kunnen werken.

[Math-E-Mad-X]

Overigens snap ik sowieso niet waarom je Dijkstra of Bellman/Ford tijdens je algoritme uitvoert. Je kunt namelijk ook gewoon voorafgaand aan je algoritme m.b.v. Dijkstra de kortste routes tussen elke twee steden berekenen.

Vervolgens mag je dan bij het toepassen van jouw algoritme er verder vanuit gaan dat de afstand tussen elke twee steden X en Y altijd gelijk is aan de lengte van de kortste route tussen X en Y die je met Dijkstra heb uitgerekend.

Dat is misschien niet de meest efficiënte methode, maar dat maakt niet uit want het gaat er alleen maar om dat alles binnen polynomiale tijd uitgerekend kan worden. Bovendien maakt het het probleem een stuk eenvoudiger.

[Esthetisch]

Ok, ik geloof dat ik stap 2 door heb (althans, scenario 1, de andere twee scenario's heb ik nog niet bekeken). Maar het komt er dus op neer dat je na afloop van deze stap voor iedere stad twee uitgaande pijlen hebt en twee inkomende pijlen (oftewel: iedere kolom heeft twee gevulde vakjes en iedere rij heeft twee gevulde vakjes). Maar de inkomende pijlen hoeven niet samen te vallen met de uitgaande pijlen (de matrix is niet symmetrisch t.o.v. de diagonaal). Iedere stad kan dus in principe met 4 verschillende andere steden direct verbonden zijn.

Als je het mij vraagt moeten die inkomende pijlen uiteindelijk ‘automatisch’ samenvallen met de uitgaande pijlen. Dit komt misschien wat verwonderlijk over, maar toch is het ergens ook wel logisch.

Zolang er overal geld A->B=B->A weet je dat na stap 1 een assymetrie ook direct tot gevolg heeft dat niet alle rijen en kollommen 2 kunnen zijn.* De efficiëntste combinatie is voor de rijen tov de kolommen dan hetzelfde als voor de kolommen t.o.v. de rijen. Het maakt voor het algoritme dan ook geen verschil of je eerst de rijen goedzet, en daarmee de kolommen gaat bewerken, of dat je kolommen goed zet en dan de rijen gaat bewerken. Je zult op precies dezelfde eindsituatie terecht komen, omdat er immers ook geen wezenlijk verschil is tussen de x en y as.

In feite zou voor 1 situatie alleen hoeven te gelden dat in elke kolom 2 vakjes staan. MAAR, je ontkomt er dan niet aan dat je de rijen moet gaan labellen, anders hebben de vakjes in een kolom geen harde betekenis, alleen dat er 2 lijnen aan het punt verbonden zijn. Door dat labellen zie je vervolgens dat de situatie (pure afstanden, zonder gevulde vakjes) gespiegeld is tov de diagonaal. Bovendien moet je elke rij nu ook 2 vakjes geven. Het maakt dan daarna dus eigenlijk ook niet meer uit of je alle kolommen 2 geeft en de rijen gaat goedzetten, of juist dat je alle rijen 2 vakjes geeft, en dan de kolommen goed gaat zetten. Voor beide situaties zal stap 2 uiteindelijk precies evenveel extra afstand genereren, voor beide situatie zal stap 2 precies hetzelfde verlopen, maar bovendien leiden ze ook tot 1 en dezelfde ‘laagste’ eindsituatie. Om tot die specifieke eindsituatie te komen maakt het dus niet uit of je hem vanaf de X-as of Y-as berekent. Hij ziet er bij beiden PRECIES hetzelfde uit, je komt letterlijk bij precies hetzelfde plaatje. Bovendien zijn de laagste waarden gespiegeld t.o.v. de diagonaal. Deze feiten samen maken het (lijkt me) toch wel zeker dat dat gevulde plaatje eveneens gespiegeld zal zijn langs de diagonaal.

Dit moet nog simpeler of beter te omschrijven zijn ,maar dit is het beste wat ik er nu op dit moment van kan maken.

Of heb je soms een tegenvoorbeeld? Nee toch zeker?.

Dat is anders dan wat ik eerst had begrepen. Ik dacht namelijk dat iedere stad met slechts 2 andere steden direct verbonden zou zijn (diagonaal-symmetrische matrix) en dat zal uiteindelijk ook het geval moeten zijn natuurlijk.

En als het goed is loopt het daar dus automatisch ook op uit. Wat je in eerste instantie dacht klopt ook.

Overigens snap ik ook niet helemaal waarom je het Bellman-ford algoritme nodig hebt. In principe zijn alle afstanden altijd positief, dus zou je met Dijkstra moeten kunnen werken.

Daarvoor is het goed naar het hoofdstuk Dijkstra te kijken. Daar staat namelijk in beschreven dat uit de tabel waar je dus heel de tijd mee bezig bent een andere tabel moet ‘destilleren’. Met die nieuw verkregen tabel kan Dijkstra/BellmanFord (klopt ook misschien niet helemaal->negativ cycles, maar de juiste algoritmen zijn hiervoor wel beschikbaar, je moet in elk geval het ‘shortest simple path’ vinden) worden uitgevoerd. En die nieuwe tabel kan dus wel negatieve afstanden bevatten. Zeker wanneer je al 1 of meer bewerkingen binnen stap 2 hebt uitgevoerd.

Overigens snap ik sowieso niet…..Dijkstra heb uitgerekend.

dit klopt dus niet, ik hoop dat bovenstaande daarbij verhelderend werkt. Daarnaast staat het sowieso vast dat het algoritme zoals beschreven eveneens niet het meest efficiënt is, Dijkstra (en meer) kan met wat ‘husselen’ vrijwel zeker makkelijker. Maar, de dijkstra-tabel zal er wel bij elke nieuwe bewerking (gedeeltelijk) anders uit zien. Dan nog zul je die wijziging waarschijnlijk ook direct door kunnen voeren en niet het hele algoritme opnieuw hoeven uit te voeren, maar dan zul je een omrekening moeten toevoegen.

Er is voor deze ‘omslachtige’ manier gekozen om zeker te weten dat het klopt, en het en de ‘inhoudelijke uitgebreidheid zo minimaal mogelijk te houden. Op de manier zoals je voorstelt werkt het opzich ook wel enigszins voor scenario 1 (waar dijkstra nog niet voorkomt, maar je maar 1 keer alle (B=B->A. Als dat niet geldt, kan je namelijk na stap 1 wel een situatie hebben waarvoor alle 3 de eisen gelden, maar die toch niet symmetrisch is. Wanneer je de situatie nog minimaal 1 keer moet bewerken zou dit volgens mij direct weer worden weggewerkt, maar als je niets meer hoeft recht te zetten heb je dus een probleem.

[Math-E-Mad-X]

Okee, ik heb nog eens naar het hoofdstuk over Dijkstra gekeken en zie nu dat er staat:

Om verwarring te voorkomen dient direct al vermeld te worden dat het algoritme van Dijkstra dus niet gebruikt zal worden om de kortste route tussen verschillende punten te berekenen.

Echter, van de volgende zin begrijp ik weer helemaal niets, waardoor ik dus nog steeds niet snap waarom en hoe je Dijkstra gebruikt:

De situatie zoals deze voor een bepaalde bewerking is wordt ingevoerd in het algoritme van Dijkstra om hiermee de bewerking te bepalen waarbij er zo min mogelijk afstand bij komt. Dit is een belangrijk verschil en verdient dan ook genoemd te worden

Sorry, maar ik denk dat je echt het hele stuk zult moeten herschrijven in de stijl zoals je dat in post nummer 67 gedaan hebt. Verder zou het daarbij handig zijn voor elke stap aangeeft wat je met de stap bereikt. Bijvoorbeeld:

"Na deze stap geldt dat iedere stad X met precies twee andere steden Y en Z is verbonden, waarbij Y en Z de twee steden zijn met de kortste afstand tot X."

(ik zeg maar wat hier)

Verder zou ik bij idere stap een tekening zetten en een voorbeeld tabel.

[Math-E-Mad-X]

In feite zou voor 1 situatie alleen hoeven te gelden dat in elke kolom 2 vakjes staan. MAAR, je ontkomt er dan niet aan dat je de rijen moet gaan labellen, anders hebben de vakjes in een kolom geen harde betekenis, alleen dat er 2 lijnen aan het punt verbonden zijn.

Deze zin bestaat uit drie delen die aanelkaar geplakt zijn door de verbindingswoorden 'maar' en 'anders'. Helaas ontgaat het verband tussen deze drie delen mij totaal. Het lijken voor mij drie totaal ongerelateerde zinnen. Ik begrijp hier dus niets van.

Als je het mij vraagt moeten die inkomende pijlen uiteindelijk ‘automatisch’ samenvallen met de uitgaande pijlen. Dit komt misschien wat verwonderlijk over, maar toch is het ergens ook wel logisch.

Het zou best kunnen dat dat klopt, maar dat soort dingen moet je er wel expliciet bij vermelden. Je kunt niet verwachten dat de lezer dat soort verbanden vanzelf inziet. De lezer zal namelijk hoe dan ook minder energie hierin steken dan jij al gedaan hebt. Bovendien geef je, door dit expliciet te vermelden, de lezer de kans om zelf na te gaan of dit klopt en dus te proberen jouw theorie onderuit te halen. Het is in principe immers altijd mogelijk dat de lezer iets ziet wat jij over het hoofd gezien hebt.

[317070]

Ik heb ook even geleden een veredelde poging gedaan om het te programmeren, maar ik kon niet uitvogelen wat je exact met scenario 1 bedoelde. Ik had al even tijd nodig om uit te vinden of je bij 'de laagste 2 in iedere kolom' de nullen op de diagonaal mag meerekenen, of niet (ik veronderstel van niet).

Ook: de kortste route tussen 2 steden zal altijd de rechte weg ertussen zijn, daar heb je geen andere algoritmes voor nodig.

Ik post hier even wat ik had:

from numpy import *

import scipy.spatial.distance as distance

import heapq

def generateRandomPoints(n=10):

return random.rand(n,2)

def distanceMatrix(points):

return distance.squareform(distance.pdist(points, 'euclidean'))

def shortestPath(points):

D = distanceMatrix(points)

n = len(points)

X = zeros((n,n))

for i in xrange(n):

indexes = heapq.nsmallest(3, enumerate(D[:,i]), key=lambda(k, v): v)

X[indexes[1][0],i] = 1

X[indexes[2][0],i] = 1

"Scenario 1"

for i in xrange(n):

if sum(X[i,:])<2:

v = D[i,X[:,i]==1]

print v

return X

print shortestPath(generateRandomPoints())

[Esthetisch]

Sorry, maar ik denk dat je echt het hele stuk zult moeten herschrijven in de stijl zoals je dat in post nummer 67 gedaan hebt. Verder zou het daarbij handig zijn voor elke stap aangeeft wat je met de stap bereikt. Bijvoorbeeld:

"Na deze stap geldt dat iedere stad X met precies twee andere steden Y en Z is verbonden, waarbij Y en Z de twee steden zijn met de kortste afstand tot X."

(ik zeg maar wat hier)

Verder zou ik bij idere stap een tekening zetten en een voorbeeld tabel.

het hele stuk herschrijven zoals in #67 is opzich niet zo heel veel werk meer, alleen dijkstra nog en misschien een stukje van stap3. Dat was ik sowieso ook nog wel een keer van plan, net zoals voor beide delen een voorbeeldje toevoegen. Aangeven wat ik bij elke stap doe gebeurt volgens mij toch wel voldoende, in de bijbehorende beschrijvingen. Maar ik zal e.e.a. wel wat verder uitwerken, een geporgrammeerde code (macro voor Excel) zou ook bijna klaar moeten zijn (behalve het echte algoritme bij ‘Dijkstra”, wel de omvorming naar de juiste tabel) die kan ik ter verduidelijking misschien hier er wel op zetten, als de eigenaar van die code het daarmee eens is.

De reden dat ik die voorbeelden er nog niet op heb gezet, is dat ik nog een beetje ertegen aan loop te hikken wat nu het beste is. Sowieso geef ik de voorkeur eraan om naar Dijkstra te verwijzen, omdat ik die begrijp, maar ook omdat hij lijkt me een Nederlander is…. das dan toch leuker. Maar Dijkstra zal dan wel IETS moeten worden aangepast. Het bellmanford-algoritme begrijp ik maar half want daarvan kan ik niet echt bevredigende voorbeelden vinden, maar vooral alleen geprogrammeerde codes met foutmeldingen.. Het is op internet zo te vinden dat er makkelijke manieren zijn om voor een situatie inclusief negatieve afstanden de ‘kortste routes’ te bepalen, maar hoe je dit nu precies op een specifieke tabel stap voor stap uitvoert moet ik nog even uitvogelen. Hulp daarbij is natuurlijk welkom, wie het weet mag het zeggen. Zodra het me duideiljk is hoe dat stukje precies werkt, heb ik binnen mum van tijd de bijbehorende voorbeelden.

Deze zin bestaat uit drie delen die aanelkaar geplakt zijn door de verbindingswoorden 'maar' en 'anders'. Helaas ontgaat het verband tussen deze drie delen mij totaal. Het lijken voor mij drie totaal ongerelateerde zinnen. Ik begrijp hier dus niets van.

Ik begrijp je maar toch vind ik het zelf niet eens zo’n slechte zin. Maarja ik weet ook hoe het bedoeld is. Het is helaas niet mogelijk om alles tegelijkertijd te vermelden, dus probeer ik bij 1 feit te beginnen en daar steeds een feit aan toe te voegen. Hopelijk kan je kan zien naar welk totaalplaatje dat leidt. Maargoed, misschien moet je inderdaad alle 3 de feiten wel gewoon los zien en vanuit daar verder redeneren.

Het zou best kunnen dat dat klopt, maar dat soort dingen moet je er wel expliciet bij vermelden. Je kunt niet verwachten dat de lezer dat soort verbanden vanzelf inziet. De lezer zal namelijk hoe dan ook minder energie hierin steken dan jij al gedaan hebt. Bovendien geef je, door dit expliciet te vermelden, de lezer de kans om zelf na te gaan of dit klopt en dus te proberen jouw theorie onderuit te halen. Het is in principe immers altijd mogelijk dat de lezer iets ziet wat jij over het hoofd gezien hebt.

Dat kan ik er wel expliciet bij vermelden, maar de vraag is dan waar leg je de grens he. Ieder feit kan extreem diep worden uitgespit, dus het is dan een beetje zoeken naar wat nu al pure logica is, en wat nog niet. Kritiek zoals die van jouw helpt daar alleen maar bij, dus ik neem aan dat die sorry van je als medelijden was bedoeld…

Ik zou zeggen als je het niet begrijpt probeer zelf te beredeneren hoe het zou moeten, of wacht het even af. Ik hoop binnenkort toch wel de laatste puntjes op de i te kunnen zetten, en dan hier de laatste nodige voorbeelden/beschrijvingen erop te zetten. Als stap 1 en stap 2 (uitgezonderd Dijsktra) bij jouw duidelijk zijn is de grootste slag eigenlijk al gemaakt. Daarna is het vooral nog een kwestie van schaven en aanvullen.

Ik heb ook even geleden een veredelde poging gedaan om het te programmeren, maar ik kon niet uitvogelen wat je exact met scenario 1 bedoelde. Ik had al even tijd nodig om uit te vinden of je bij 'de laagste 2 in iedere kolom' de nullen op de diagonaal mag meerekenen, of niet (ik veronderstel van niet).

De veronderstelling dat daar nullen staan is fout, in het voorbeeld staan er ook geen 0-en maar XXX-en. Je zou XXX wel kunnen vervangen met oneindig, maar niet met 0. De veronderstelling dat je die 0 niet mee mag nemen klopt dan dus weer wel.

Ook: de kortste route tussen 2 steden zal altijd de rechte weg ertussen zijn, daar heb je geen andere algoritmes voor nodig.

Zie bericht #71 de eerste quote

Dus nogmaals:

Mocht iemand de werking van het BellmanFord algoritme voor een tabel hebben waar wel negatieve afstanden in voor komen, maar geen negatieve ‘cylces’, dan kan stap 2 ook worden afgerond. Dan zet ik de omwerking naar de tabel er ook gelijk op, en wat extra voorbeeldjes en wat extra duidelijke stappenplannen, plus eventueel de codes. Ik weet zeker dat dan voor iedereen duidelijk moet kunnen worden hoe het werkt.

[Esthetisch]

@317070 bedankt trouwens voor de code, ik zal proberen te kijken of ik zie waar het precies niet klopt, maar dat lukt niet zo 1234 omdat ik die taal niet spreek. Maar je hoort van me, ofwel door een verbeterde code, ofwel door een opmerking op de jouwe.