Grafer och nätverkDet resande säljaren problemet

Låt oss tänka ännu en gång om nätverk och kartor. Föreställ dig att en leveransservice måste besöka ${tsn} olika städer för att distribuera paket. Vi kan tänka på dessa städer som topparna i en graf. Om alla städer är anslutna med vägar är detta en , så det finns det ${tsn} × ( ${tsn} - 1)2 = ${tsn*(tsn-1)/2} kanter totalt.

Leveransbilen måste besöka alla städer i alla ordningar. I Königsberg-broproblemet ville vi hitta stigar som går längs varje kant exakt. Nu vill vi hitta vägar som besöker varje toppunkt exakt en gång. Dessa vägar kallas Hamiltonian cykler .

Det finns otaliga olika möjligheter för Hamiltonian-cykler i kompletta diagram. I själva verket kan vi välja valfri toppunkt som startpunkt och sedan välja någon av de återstående städerna i valfri ordning:

Diagram coming soon…

Diagram Coming Soon…

I en graf med ${tsn1} städer, måste varje Hamiltonian-cykel också innehålla ${tsn1} städer. Nu,

Detta innebär att det totalt finns ${tsnPaths(tsn1)} möjliga vägar. En korthet för denna produkt är ${tsn1} ! eller ${tsn1} Factorial .

Du kan tänka dig att det kanske inte är möjligt att resa direkt mellan två städer - utan att gå via en annan stad. I så fall har vi inte längre en komplett graf, och att hitta antalet Hamiltonian-cykler, om de finns alls, blir mycket svårare.

Hittills har vi ignorerat det faktum att vissa städer kan vara längre från varandra än andra. I verkliga livet är detta emellertid ett mycket viktigt övervägande: vi vill inte bara hitta någon väg utan vi vill hitta den kortaste vägen. Detta kallas Travelling Salesman Problem . Det måste lösas inte bara inom transport och logistik, utan också när man placerar transistorer på mikrochips, för att göra snabbare datorer eller när man analyserar DNA- strukturen.

En enkel metod skulle vara att prova alla möjliga vägar, hitta längden på varje och sedan välja den kortaste. Men vi har bara visat det, även med bara ${tsn2} städer finns ${tsn2} ! = ${factorial(tsn2)} möjliga vägar. När du väl har hundratals eller tusentals vertikaler blir det omöjligt att prova alla möjliga vägar, även med kraftfulla datorer.

Tyvärr finns det ingen effektivare algoritm för att lösa det resande säljaren problemet. Istället har matematiker och datavetare utvecklat olika algoritmer som hittar bra lösningar, även om de kanske inte är de allra bästa. Dessa algoritmer, som bara ger ungefärliga lösningar, kallas Heuristics .

Försök omarrangera städerna på den här kartan och se hur den kortaste vägen mellan dem ändras. Du kan ta bort städer genom att trycka på dem och du kan lägga till städer genom att klicka var som helst på kartan (upp till 8):

Den giriga algoritmen (eller närmaste grannalgoritm) är mycket enkel: du börjar i en slumpmässig stad och flyttar i följd till den närmaste stad du inte har besökt tidigare. När du har besökt alla städer stannar du.

Animering kommer snart ...

Du kan visa att i genomsnitt är banor som hittas med den giriga algoritmen 25% längre än den kortaste möjliga sökvägen.

2-optalgoritmen börjar med en slumpmässig möjlig sökväg. Sedan väljer du upprepade gånger två kanter och byter runt dem om det skulle minska banans längd. Du stannar när du inte kan minska längden ytterligare genom att byta några par par kanter.

Animering kommer snart ...

Det visar sig att naturen länge innan datorer existerade hade hittat ett smart sätt att hitta optimala vägar mellan olika platser: i myrkolonier.

Myror vill hitta kortast möjliga rutter mellan deras bo och möjliga matkällor. De kan kommunicera med varandra genom kemikalier som de lämnar längs sin spår och vilka andra myror kan följa.

Myrkolonin skickar ut många speider som ursprungligen reser i slumpmässiga riktningar. När de har hittat mat återvänder de och lämnar efter sig ett spår av feromon. * Andra myror tenderar att följa en spår när de hittar en, vilket leder dem till mat. På sin återresa deponerar de mer feromon, vilket förstärker spåret. * Med tiden avdunstar feromon. Ju längre en väg är, desto mer tid tar det myror att resa längs den, och så har feromonen mer tid att avdunsta. Korta vägar kan å andra sidan förstärkas snabbare, så att deras styrka ökar snabbare.

Diagram kommer snart ...

Ant Colony System (ACS) algoritmer försöker replikera detta beteende på datorer med många "virtuella" myror. De kan snabbt hitta mycket bra lösningar för det resande säljaren problemet.

En särskilt användbar egenskap hos ACS-algoritmer är att de kan köras kontinuerligt och anpassa sig i realtid till förändringar i grafen. Dessa förändringar kan orsakas av bilolyckor och vägstängningar i gatunät, eller av trafikspikar till webbservrar i datornät.

Problemet med den resande säljaren är NP-hårt , vilket innebär att det är mycket svårt att lösas av datorer (åtminstone för ett stort antal städer).

Att hitta en snabb och exakt algoritm skulle ha allvarliga konsekvenser inom datavetenskapen: det skulle betyda att det finns snabba algoritmer för alla NP-hårda problem. Det skulle också göra det mesta av Internet-säkerhet värdelös, vilket förlitar sig på att vissa problem tros vara mycket svåra för datorer.

Att hitta en snabb algoritm för att lösa Travelling Salesman-problemet skulle också lösa ett av de mest kända öppna problemen inom matematik och datavetenskap, P vs NP- problemet. Det är ett av de sju tusenprisproblemen , var och en har ett pris på 1 miljoner dollar.

Ändra språk

Logga in på Mathigon

Dela med sig

Återställ framsteg

Ordlista

Grafer och nätverkDet resande säljaren problemet