Problemet är gammalt och ännu olöst. Det står klart att någon av alla möjliga resrutter måste vara kortast (ev. är flera lika korta) men hittills känner man inte till någon annan metod än att beräkna samtliga möjliga resrutter och jämföra. Och antalet resrutter ökar mycket snabbt med antalet städer. Till slut blir det antalet för stort också för dagens datorer.
Nedan finns några java applets, som åskådliggör
problemet och dess lösning. De utgår från en enkel praktisk
rutin och undersöker dess effektivitet och effektiviteten hos några varianter.
Det går bra att peka med musen, klicka och placera ut
städerna efter eget val (begränsningar: högst 150 st. och minst
3 pixlar emellan dem).
Ett klick på knappen "ordna", och appletten (?!) visar hur dess algoritm löser problemet. Den längd, som anges för den så konstruerade rutten, utgår från att ytan motsvarar 100 * 100 längdenheter.
Knappen "slump" placerar ut 100 städer slumpmässigt.
Knappen "serie" slutligen, ger en serie av 100 slumpade uppsättningar av städer och ett genomsnitt av de uppnådda rutterna.
Ett första försökFler än handelsresanden möter problemet. Hur planerar man t. ex. utkörning av varor till slumpmässigt utspridda kunder ?Ett sätt: Utgå från den osorterade bunten med följesedlar. Tag upp de tre första och lägg dem i den ordning som det är bäst att besöka de kunderna. Tag upp den fjärde och sortera in den, där avstickaren till fjärde kunden innebär minst extra körning. Fortsätt så tills alla följesedlar har sorterats upp till en lämplig körordning. Detta enkla förfaringssätt ger faktiskt ett hyfsat bra resultat. Prova själv ! Peka med musen, klicka och placera ut punkter eller klicka på knappen "slump" och låt datorn placera ut 100 punkter. Klicka sedan på "ordna" och följ hur rutten växer fram. I praktiken upptäcker man ofta under sorteringen av följesedlar att man får göra omsorteringar när en ny adress passar illa in i den tidigare ordningen. | Minsta motståndets principI "första försöket" presenteras de nya destinationer som rutten ska utökas med helt slumpmässigt. Man tar det som det kommer, och det blir som det blir.Vän av ordning vill naturligtvis gå systematiskt fram. Så varför inte följa principen att alltid utöka med den destination som ger minsta utökningen ? Den principen tillämpas här, och i fysiken finns ju flera exempel där minsta motståndet får styra vägvalet. Resultatet ? Prova själv ! Om man skärskådar de figurer, som genereras på de slumpade punktmängderna, så slås man av att de är påfallande taniga och spinkiga. Så blir det förståss om man börjar med en liten figur, och hela tiden utökar så snålt som möjligt. Vi har fått vad vi begärde, men alls inte vad vi ville ha. Idealfiguren ska vara så fet och rund som möjligt. En cirkel är drömmålet, men slumpade punkter ligger knappast så förmånligt. | Skal-principenI förra exemplet visades effekten av att börja med en liten figur och utöka i små steg. Låt oss göra tvärt om !Börja med att slå en ring kring alla punkter; med att förse punktmängden med ett skal. Länka sedan in de inre punkterna allteftersom i skalet. Vi arbetar s.a.s. utifrån och inåt och gör hela tiden så små ändringar som möjligt. Principen är enkel, men den resulterar i en påtaglig förbättring. Trots det upptäcker man vid betraktandet snabbt brister i de alstrade figurerna. En del figurer har turer, som korsar sig sjäva, och ett irriterande inslag är de smala långsträckta "vikar", som förekommer allt för ofta. Vi vill inte ha "fjordar", vi vill ha "bukter". Noteras bör kanske att här används för första gången geometriska tvådimensionella egenskaper hos avbildningarna av punktmängderna. I de två föregående exemplen utgår algoritmerna enbart från avstånden mellan punkterna - alltså skalärer, som skulle kunna representera mycket annat. | Skal-principen med utslätningSom nämnts, krävs i praktiken ofta omsortering av de tidigare ordnade adresserna, om en ny adress passar dåligt in i den ordningen. Låt oss göra samma sak här.Här byggs resrutten upp på samma sätt som i föregående exempel, men efter varje ny punkt gås rutten igenom, och om en eller flera förbundna punkter då passar bättre på en annan plats i turen, så länkas de in där (och därefter gås den omsorterade rutten igenom igen, tills inga fler förbättringar kan göras). På så sätt försöker vi släta ut de knöligheter, som uppstår. Prova gärna att slumpa och ordna en punktmängd i föregående exempel och jämför med den bild, som fås med samma punktmängd när utslätning tillkommer. Det blir rätt många genomgångar, och det märks på tiden för en serie (Java är inte särskilt snabbt). Men det märks också på genomsnittet, som sjunker med drygt 5%, eller nästan 50 längdenheter, och hamnar klart under 800. |
Vårt syncentrum utför ett omfattande arbete med databehandling, och när intrycken når vårt medvetande är många samband redan klarlagda; vad är utanför, vad är innanför osv. Här finns kanske en orsak till det gäckande intryck som problem inom graf-teorin kan ge - man kan känna vad som är rätt, men det kan vara mycket svårt att bevisa det formellt. De sökta sambanden finns kanske tidigare än i det stadium där de enkelt kan formuleras i ord (symboler).
Isadora Duncan ombads en gång att berätta vad hennes dans
handlade om. Hon svarade - "kunde jag berätta det, behövde jag inte
dansa det".
| Ändrad 00 03 30 |
Besök:
|