Den nærmeste indsættelsesalgoritme

Den nærmeste indsættelsesalgoritme er en heuristisk algoritme, der bruges til at finde en omtrentlig løsning på det rejsende sælgerproblem (TSP). TSP sigter mod at finde den kortest mulige rute, der besøger hver by (node) nøjagtigt en gang og vender tilbage til startbyen.

hvordan det fungerer:

1. Initialisering:

- Start med en vilkårlig knude som den indledende turné (f.eks. En enkelt knudepunkt). Lad os kalde denne knude "start_node".

- Lad `V` være sættet af noder, der endnu ikke er føjet til turen.

2. iteration:

- Find den nærmeste knude: For hver node `Jeg er i den aktuelle turné, find noden` j` i `V '(sættet med uviserede knudepunkter), der er tættest på` jeg' (dvs. har den mindste afstand). Denne "nærmeste" node `j` er den, vi vil indsætte. Matematisk finder vi:

`j =argmin_ {v ∈ V} min_ {i ∈ Tour} dist (i, v)`

- Indsæt den nærmeste knude: Find kanten (i, k) i den aktuelle turné, hvor indsættelse af knudepunkt `j` mellem noder` og `k` resulterer i den mindste stigning i turnélængden. Det vil sige, find `Jeg 'og` k' sådan, at:

`dist (i, j) + dist (j, k) - dist (i, k)` minimeres.

- Indsæt knudepunkt `j` mellem noder` I` og `K ', og udskift effektivt kanten (i, k) med to kanter (i, j) og (j, k).

- Fjern noden `j` fra sættet med ikke -viste knudepunkter` V`.

3. Opsigelse:

- Gentag trin 2, indtil alle noder er føjet til turen (dvs. `V` er tom).

4. Lukning af løkken:

- Tilslut den sidste knude, der er føjet til turen tilbage til `start_node 'for at afslutte cyklussen.

Eksempel:

Lad os sige, at vi har byer A, B, C, D og E med følgende afstande:

`` `

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: Lad os starte med knudepunkt A som den indledende turné:`Tour ={a}`

2. iteration 1:

- nærmeste knude til A IS B (afstand 10).

-Indsæt B i turen (A -> B -> A). `Tour ={a, b, a}`

3. iteration 2:

- Find den nærmeste uviserede knude til enhver knude i den aktuelle turné:

- nærmest A:C (15), D (20), E (25)

- nærmest B:C (35), D (25), E (30)

- Minimum af disse afstande er 15 (A til C).

- Find, hvor du skal indsætte C.

- Indsættelse af C mellem A og B:15 + 35 - 10 =40

- Indsættelse af C mellem B og A:35 + 15 - 10 =40

- Indsæt C mellem A og B (eller B og A). `Tour ={a, c, b, a}`

4. iteration 3:

- Find den nærmeste uviserede knude:

- nærmest A:D (20), E (25)

- nærmest C:D (30), E (20)

- nærmest B:D (25), E (30)

- Minimum afstand er 20 (C til E eller A til D). Lad os tage C til E.

- Indsæt E:

- Indsættelse af E mellem A og C:25 + 20 - 15 =30

- Indsættelse af E mellem C og B:20 ​​+ 30 - 35 =15 (minimum!)

- Indsættelse af E mellem B og A:30 + 25 - 10 =45

- Indsæt e mellem C og B. `Tour ={a, c, e, b, a}`

5. iteration 4:

- Kun knudepunkt D er tilbage.

- nærmest A:D (20)

- nærmest C:D (30)

- nærmest E:D (10) (minimum!)

- nærmest B:D (25)

- Indsæt D:

- Indsættelse af D mellem A og C:20 + 30 - 15 =35

- Indsættelse af D mellem C og E:30 + 10 - 20 =20

- Indsættelse af D mellem E og B:10 + 25 - 30 =5 (minimum!)

- Indsættelse af D mellem B og A:25 + 20 - 10 =35

- Indsæt d mellem E og B. `Tour ={a, c, e, d, b, a}`

optimering (eller rettere sagt tilnærmelse) aspekter:

Den nærmeste indsættelsesalgoritme optimeres ved iterativt at tilføje den knude, der indfører den mindste øjeblikkelige stigning i den samlede turnélængde på hvert trin. Dette er en grådig tilgang, hvilket betyder, at det gør det bedste valg på hvert trin uden at overveje den globale virkning af dette valg.

* lokalitet: Algoritmen fokuserer på at minimere lokale afstande. Den vælger den knude, der er tættest på den aktuelle turné, med det formål at holde det ekstra segment af turen så kort som muligt.

* trinvis vækst: Turen er bygget trinvist ved at tilføje en knude ad gangen. Hver indsættelsesbeslutning er baseret på den aktuelle tilstand af turen, så den planlægger ikke at se, hvordan tilføjelse af en bestemt knude kan påvirke fremtidige indsættelser.

Begrænsninger:

* ikke optimal: Den nærmeste indsættelsesalgoritme er en heuristisk, hvilket betyder, at den ikke garanterer den absolutte korteste rute. Det kan sidde fast i lokal optima, hvor et lidt andet tidligt valg kan føre til en markant bedre samlet løsning.

* grådig natur: Den grådige natur af algoritmen kan føre til suboptimale valg, især i tilfælde, hvor afstandene ikke er ensartede. Nogle gange kan det at vælge en lidt længere node tidligt åbne muligheder for kortere forbindelser senere.

* afhængighed af startnode: Startnoden kan påvirke den sidste turné. Forskellige startknudepunkter kan resultere i forskellige ruter.

Fordele:

* enkel at implementere: Det er relativt let at forstå og implementere.

* hurtig: Det er generelt hurtigere end algoritmer, der garanterer optimale løsninger (som brute-force-søgning). Tidskompleksiteten er typisk O (n^2), hvor n er antallet af knudepunkter.

* Rimelig tilnærmelse: Det giver normalt en rimelig god tilnærmelse af den optimale TSP -turné, især når afstandene tilfredsstiller trekantens ulighed (dvs. den direkte afstand mellem to punkter er altid mindre end eller lig med summen af ​​afstandene langs enhver anden sti).

Kortfattet:

Den nærmeste indsættelsesalgoritme er en grådig heuristik, der konstruerer en TSP -turné ved gentagne gange at tilføje den nærmeste uvisiske knude til den eksisterende turné. Selvom det ikke garanteres at producere den optimale løsning, er det en hurtig og enkel måde at finde en rimelig god tilnærmelse. Det fokuserer på at minimere den lokale afstandsstigninger på hvert trin.