Het dichtstbijzijnde invoegalgoritme
Het Nearest Insertion Algorithm is een heuristisch algoritme dat wordt gebruikt om een benaderende oplossing te vinden voor het Travelling Salesperson Problem (TSP). Het TSP streeft ernaar de kortst mogelijke route te vinden die elke stad (knooppunt) precies één keer bezoekt en terugkeert naar de startstad.
Hoe het werkt:
1. Initialisatie:
- Begin met een willekeurig knooppunt als initiële rondleiding (bijvoorbeeld een lus met één knooppunt). Laten we dit knooppunt 'start_node' noemen.
- Laat `V` de set knooppunten zijn die nog niet aan de tour zijn toegevoegd.
2. Iteratie:
- Zoek het dichtstbijzijnde knooppunt: Zoek voor elk knooppunt 'i' in de huidige tour het knooppunt 'j' in 'V' (de verzameling niet-bezochte knooppunten) dat het dichtst bij 'i' ligt (d.w.z. de kleinste afstand heeft). Dit "dichtstbijzijnde" knooppunt `j` is het knooppunt dat we willen invoegen. Wiskundig vinden we:
`j =argmin_{v ∈ V} min_{i ∈ tour} dist(i, v)`
- Voeg het dichtstbijzijnde knooppunt in: Zoek de rand (i, k) in de huidige tour waarbij het invoegen van knooppunt `j` tussen knooppunten `i` en `k` resulteert in de kleinste toename van de tourlengte. Dat wil zeggen:zoek 'i' en 'k' zo dat:
`dist(i, j) + dist(j, k) - dist(i, k)` wordt geminimaliseerd.
- Voeg knooppunt `j` in tussen de knooppunten `i` en `k`, waarbij u effectief de rand (i, k) vervangt door twee randen (i, j) en (j, k).
- Verwijder knooppunt `j` uit de reeks niet-bezochte knooppunten `V`.
3. Beëindiging:
- Herhaal stap 2 totdat alle knooppunten aan de tour zijn toegevoegd (d.w.z. `V` is leeg).
4. De cirkel rondmaken:
- Verbind het laatste knooppunt dat aan de tour is toegevoegd terug naar het `start_node` om de cyclus te voltooien.
Voorbeeld:
Laten we zeggen dat we steden A, B, C, D en E hebben met de volgende afstanden:
```
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. Begin: Laten we beginnen met knooppunt A als de initiële tour:`Tour ={A}`
2. Iteratie 1:
- Het dichtstbijzijnde knooppunt bij A is B (afstand 10).
- Voeg B in de tour in (A -> B -> A). `Rondleiding ={A, B, A}`
3. Iteratie 2:
- Vind het dichtstbijzijnde onbezochte knooppunt bij een knooppunt in de huidige tour:
- Dichtst bij A:C (15), D (20), E (25)
- Dichtst bij B:C (35), D (25), E (30)
- Het minimum van deze afstanden is 15 (A t/m C).
- Zoek waar je C moet invoegen.
- C tussen A en B plaatsen:15 + 35 - 10 =40
- C tussen B en A invoegen:35 + 15 - 10 =40
- Plaats C tussen A en B (of B en A). `Rondleiding ={A, C, B, A}`
4. Iteratie 3:
- Vind het dichtstbijzijnde onbezochte knooppunt:
- Dichtstbijzijnde bij A:D (20), E (25)
- Dichtst bij C:D (30), E (20)
- Dichtstbijzijnde B:D (25), E (30)
- Minimale afstand is 20 (C tot E of A tot D). Laten we C naar E brengen.
- E invoegen:
- E tussen A en C invoegen:25 + 20 - 15 =30
- E tussen C en B invoegen:20 + 30 - 35 =15 (Minimaal!)
- E tussen B en A invoegen:30 + 25 - 10 =45
- Voeg E in tussen C en B. `Tour ={A, C, E, B, A}`
5. Iteratie 4:
- Alleen knooppunt D blijft over.
- Dichtstbijzijnde A:D (20)
- Dichtstbij C:D (30)
- Dichtstbij E:D (10) (Minimaal!)
- Dichtstbijzijnde B:D (25)
- Voeg D in:
- D tussen A en C invoegen:20 + 30 - 15 =35
- D tussen C en E invoegen:30 + 10 - 20 =20
- D tussen E en B invoegen:10 + 25 - 30 =5 (Minimaal!)
- D tussen B en A invoegen:25 + 20 - 10 =35
- Voeg D in tussen E en B. `Tour ={A, C, E, D, B, A}`
Optimalisatie-aspecten (of liever:benadering):
Het Nearest Insertion-algoritme optimaliseert door iteratief het knooppunt toe te voegen dat bij elke stap de kleinste onmiddellijke toename van de totale tourlengte introduceert. Dit is een hebzuchtige benadering, wat betekent dat er in elke fase de beste keuze wordt gemaakt zonder rekening te houden met de mondiale impact van die keuze.
* Plaats: Het algoritme richt zich op het minimaliseren van lokale afstanden. Het selecteert het knooppunt dat het dichtst bij de huidige tour ligt, met als doel het toegevoegde segment van de tour zo kort mogelijk te houden.
* Incrementele groei: De tour wordt stapsgewijs opgebouwd door één knooppunt tegelijk toe te voegen. Elke invoegbeslissing is gebaseerd op de huidige status van de tour, dus er wordt niet vooruit gepland om te zien hoe het toevoegen van een specifiek knooppunt toekomstige invoegingen kan beïnvloeden.
Beperkingen:
* Niet optimaal: Het Nearest Insertion-algoritme is een heuristiek, wat betekent dat het niet de absoluut kortste route garandeert. Het kan vastlopen in lokale optima, waarbij een iets andere vroege keuze zou kunnen leiden tot een aanzienlijk betere algehele oplossing.
* Hebzuchtige aard: De hebzuchtige aard van het algoritme kan leiden tot suboptimale keuzes, vooral in gevallen waarin de afstanden niet uniform zijn. Soms kan het in een vroeg stadium kiezen voor een iets verder gelegen knooppunt mogelijkheden bieden voor kortere verbindingen later.
* Afhankelijkheid van startknooppunt: Het startknooppunt kan de laatste tour beïnvloeden. Verschillende startknooppunten kunnen resulteren in verschillende routes.
Voordelen:
* Eenvoudig te implementeren: Het is relatief eenvoudig te begrijpen en te implementeren.
* Snel: Het is over het algemeen sneller dan algoritmen die optimale oplossingen garanderen (zoals zoeken met brute kracht). De tijdscomplexiteit is doorgaans O(n^2), waarbij n het aantal knooppunten is.
* Redelijke benadering: Het biedt meestal een redelijk goede benadering van de optimale TSP-tour, vooral wanneer de afstanden voldoen aan de driehoeksongelijkheid (dat wil zeggen, de directe afstand tussen twee punten is altijd kleiner dan of gelijk aan de som van de afstanden langs elk ander pad).
Samengevat:
Het Nearest Insertion-algoritme is een hebzuchtige heuristiek die een TSP-tour construeert door herhaaldelijk het dichtstbijzijnde niet-bezochte knooppunt aan de bestaande tour toe te voegen. Hoewel het niet gegarandeerd de optimale oplossing oplevert, is het een snelle en eenvoudige manier om een redelijk goede benadering te vinden. Het richt zich op het minimaliseren van de lokale afstandsvergroting bij elke stap. |
