den närmaste insättningsalgoritmen
Den närmaste insättningsalgoritmen är en heuristisk algoritm som används för att hitta en ungefärlig lösning på det resande säljarproblemet (TSP). TSP syftar till att hitta den kortaste möjliga rutten som besöker varje stad (nod) exakt en gång och återvänder till startstaden.
Hur det fungerar:
1. Initialisering:
- Börja med en godtycklig nod som den första turnén (t.ex. en enda nodslinga). Låt oss kalla den här noden `Start_Node`.
- Låt `v` vara den uppsättning noder som inte har lagts till i turnén ännu.
2. iteration:
- Hitta den närmaste noden: För varje nod `i 'i den aktuella turnén, hitta noden` J` i `V` (uppsättningen av oöverträffade noder) som är närmast` i' (dvs har det minsta avståndet). Denna "närmaste" nod "J" är den vi vill infoga. Matematiskt hittar vi:
`j =argmin_ {v ∈ V} min_ {i ∈ Tour} dist (i, v)`
- sätt in den närmaste noden: Hitta kanten (i, k) i den aktuella turnén där infoga nod `j` mellan noderna` i` och `k` resulterar i den minsta ökningen i turnélängden. Det vill säga, hitta `Jag 'och` k` så att:
`Dist (i, j) + dist (j, k) - dist (i, k)` minimeras.
- Infoga nod `j` mellan noderna` i` och `k`, effektivt ersätta kanten (i, k) med två kanter (i, j) och (j, k).
- Ta bort noden `J` från uppsättningen av oöverträffade noder` V`.
3. Uppsägning:
- Upprepa steg 2 tills alla noder har lagts till i turnén (dvs. `v` är tom).
4. Stäng slingan:
- Anslut den sista noden som läggs till i turnén tillbaka till `Start_Node 'för att slutföra cykeln.
Exempel:
Låt oss säga att vi har städer A, B, C, D och E med följande avstånd:
`` `
A B C D E
A 0 10 15 20 25
B 10 0 35 25 30
C 15 35 0 30 20
D 20 25 30 0 10
E 25 30 20 10 0
`` `
1. Start: Låt oss börja med Node A som den första turnén:`turné ={A}`
2. iteration 1:
- Närmaste nod till A är B (avstånd 10).
-Sätt i B i turnén (A -> B -> A). `Tour ={A, B, A}`
3. iteration 2:
- Hitta närmaste oöverträffade nod till vilken nod som helst i den aktuella turnén:
- närmast A:C (15), D (20), E (25)
- närmast B:C (35), D (25), E (30)
- Minsta av dessa avstånd är 15 (A till C).
- Hitta var du ska infoga C.
- Infoga C mellan A och B:15 + 35 - 10 =40
- Infoga C mellan B och A:35 + 15 - 10 =40
- Infoga C mellan A och B (eller B och A). `Tour ={A, C, B, A}`
4. iteration 3:
- Hitta närmaste oöverträffade nod:
- närmast A:D (20), E (25)
- närmast C:D (30), E (20)
- närmast B:D (25), E (30)
- Minsta avstånd är 20 (C till E eller A till D). Låt oss ta C till E.
- INSERT E:
- Infoga E mellan A och C:25 + 20 - 15 =30
- Infoga E mellan C och B:20 + 30 - 35 =15 (minst!)
- Infoga E mellan B och A:30 + 25 - 10 =45
- Infoga E mellan C och B. `Tour ={A, C, E, B, A}`
5. iteration 4:
- endast nod D återstår.
- närmast A:D (20)
- närmast C:D (30)
- närmast E:D (10) (minimum!)
- närmast B:D (25)
- Infoga D:
- Infoga D mellan A och C:20 + 30 - 15 =35
- Infoga D mellan C och E:30 + 10 - 20 =20
- Infoga D mellan E och B:10 + 25 - 30 =5 (minst!)
- Infoga D mellan B och A:25 + 20 - 10 =35
- Infoga D mellan E och B. `Tour ={A, C, E, D, B, A}`
optimering (eller snarare approximation) aspekter:
Den närmaste insättningsalgoritmen optimerar genom att iterativt lägga till noden som introducerar den minsta omedelbara ökningen av den totala turnélängden vid varje steg. Detta är ett girigt tillvägagångssätt, vilket innebär att det gör det bästa valet i varje steg utan att beakta den globala effekten av det valet.
* lokalitet: Algoritmen fokuserar på att minimera lokala avstånd. Den väljer noden som är närmast den aktuella turnén, som syftar till att hålla det extra segmentet av turnén så kort som möjligt.
* Inkrementell tillväxt: Turnén byggs stegvis genom att lägga till en nod åt gången. Varje insättningsbeslut är baserat på det nuvarande tillståndet för turnén, så det planerar inte framåt att se hur man lägger till en specifik nod kan påverka framtida införingar.
Begränsningar:
* inte optimalt: Den närmaste insättningsalgoritmen är en heuristik, vilket innebär att den inte garanterar den absolut kortaste rutten. Det kan fastna i lokalt optima, där ett något annorlunda tidigt val kan leda till en betydligt bättre övergripande lösning.
* girig natur: Algoritmens giriga natur kan leda till suboptimala val, särskilt i fall där avståndet inte är enhetliga. Ibland kan du välja en något längre nod tidigt öppna möjligheter för kortare anslutningar senare.
* Beroende på startnod: Startnoden kan påverka den slutliga turnén. Olika startnoder kan resultera i olika rutter.
Fördelar:
* Enkelt att implementera: Det är relativt lätt att förstå och implementera.
* Fast: Det är i allmänhet snabbare än algoritmer som garanterar optimala lösningar (som brute-force-sökning). Tidskomplexiteten är vanligtvis o (n^2), där n är antalet noder.
* Rimlig approximation: Det ger vanligtvis en ganska bra tillnärmning av den optimala TSP -turnén, särskilt när avståndet tillfredsställer triangel -ojämlikheten (dvs det direkta avståndet mellan två punkter är alltid mindre än eller lika med summan av avståndet längs någon annan väg).
Sammanfattningsvis:
Den närmaste insättningsalgoritmen är en girig heuristik som konstruerar en TSP -turné genom att upprepade gånger lägga till den närmaste oöverträffade noden till den befintliga turnén. Även om det inte garanteras att producera den optimala lösningen, är det ett snabbt och enkelt sätt att hitta en ganska bra tillnärmning. Det fokuserar på att minimera lokala avståndsökningar vid varje steg.
