L'algoritmo di inserimento più vicino è un algoritmo euristico usato per trovare una soluzione approssimativa al problema del venditore di viaggi (TSP). Il TSP mira a trovare il percorso più breve possibile che visita ogni città (nodo) esattamente una volta e ritorna alla città di partenza.
Come funziona:
1. Inizializzazione:
- Inizia con un nodo arbitrario come tour iniziale (ad esempio un singolo ciclo nodo). Chiamiamo questo nodo `start_node`.
- Sia `V` il set di nodi che non sono ancora stati aggiunti al tour.
2. Iterazione:
- Trova il nodo più vicino: Per ogni nodo `I` nel tour attuale, trova il nodo` j` in `V` (l'insieme di nodi non visitati) che è più vicino a` io '(cioè ha la distanza più piccola). Questo nodo "più vicino" `j` è quello che vogliamo inserire. Matematicamente, stiamo trovando:
`j =argmin_ {v ∈ V} min_ {i ∈ Tour} dist (i, v)`
- Inserire il nodo più vicino: Trova il bordo (i, k) nel tour attuale in cui l'inserimento del nodo `j` tra i nodi` I` e `k` risulta nel più piccolo aumento della lunghezza del tour. Cioè, trova `io` e` k` tale che:
`dist (i, j) + dist (j, k) - dist (i, k)` è minimizzato.
- Inserisci il nodo `j` tra i nodi` i` e `k`, sostituendo efficacemente il bordo (i, k) con due bordi (i, j) e (j, k).
- Rimuovere il nodo `j` dall'insieme di nodi non visitati` V`.
3. Terminatura:
- Ripetere il passaggio 2 fino a quando tutti i nodi non sono stati aggiunti al tour (cioè `V` è vuoto).
4. Chiusura del ciclo:
- Collegare l'ultimo nodo aggiunto al tour al `start_node` per completare il ciclo.
Esempio:
Diciamo che abbiamo città A, B, C, D ed E con le seguenti distanze:
`` `
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 0
`` `
1. Inizia: Cominciamo con il nodo A come tour iniziale:`tour ={a}`
2. Iterazione 1:
- Nodo più vicino ad A è B (distanza 10).
-Inserisci B nel tour (a -> b -> a). `Tour ={a, b, a}`
3. Iterazione 2:
- Trova il nodo non visitato più vicino a qualsiasi nodo nel tour attuale:
- più vicino a A:C (15), D (20), E (25)
- più vicino a B:C (35), D (25), E (30)
- Il minimo di queste distanze è da 15 (da A a C).
- Trova dove inserire C.
- Inserimento di C tra A e B:15 + 35 - 10 =40
- Inserimento di C tra B e A:35 + 15 - 10 =40
- Inserire C tra A e B (o B e A). `Tour ={a, c, b, a}`
4. Iterazione 3:
- Trova il nodo non visitato più vicino:
- più vicino a A:D (20), E (25)
- più vicino a c:d (30), e (20)
- più vicino a B:D (25), E (30)
- La distanza minima è da 20 (da C a E o A a D). Prendiamo C a E.
- Inserisci E:
- Inserimento e tra A e C:25 + 20 - 15 =30
- Inserimento e tra C e B:20 + 30 - 35 =15 (minimo!)
- Inserimento e tra B e A:30 + 25 - 10 =45
- Inserisci E tra C e B. `tour ={a, c, e, b, a}`
5. Iterazione 4:
- Rimane solo il nodo D.
- più vicino a:d (20)
- più vicino a c:d (30)
- più vicino a E:D (10) (minimo!)
- più vicino a b:d (25)
- Inserisci D:
- Inserimento di D tra A e C:20 + 30 - 15 =35
- Inserimento di D tra C ed E:30 + 10 - 20 =20
- Inserimento di D tra E e B:10 + 25 - 30 =5 (minimo!)
- Inserimento di D tra B e A:25 + 20 - 10 =35
- Inserisci D tra E e B. `tour ={a, c, e, d, b, a}`
Ottimizzazione (o meglio, approssimazione) Aspetti:
L'algoritmo di inserimento più vicino ottimizza aggiungendo iterativamente il nodo che introduce il più piccolo aumento immediato della lunghezza totale del tour ad ogni passaggio. Questo è un approccio avido, il che significa che fa la scelta migliore in ogni fase senza considerare l'impatto globale di quella scelta.
* Località: L'algoritmo si concentra sulla minimizzazione delle distanze locali. Seleziona il nodo più vicino al tour attuale, con l'obiettivo di mantenere il segmento aggiunto del tour il più breve possibile.
* Crescita incrementale: Il tour è costruito in modo incrementale aggiungendo un nodo alla volta. Ogni decisione di inserimento si basa sullo stato attuale del tour, quindi non pianifica in anticipo per vedere come l'aggiunta di un nodo specifico potrebbe influire sugli inserimenti futuri.
Limitazioni:
* Non ottimale: L'algoritmo di inserimento più vicino è un euristico, il che significa che non garantisce il percorso più breve assoluto. Può rimanere bloccato in Optima locale, in cui una scelta iniziale leggermente diversa potrebbe portare a una soluzione complessiva significativamente migliore.
* Natura avida: La natura avida dell'algoritmo può portare a scelte non ottimali, specialmente nei casi in cui le distanze non sono uniformi. A volte, scegliere un nodo leggermente più lontano all'inizio può aprire opportunità per connessioni più brevi in seguito.
* Dipendenza dal nodo iniziale: Il nodo iniziale può influire sul tour finale. Diversi nodi iniziali possono comportare percorsi diversi.
Vantaggi:
* semplice da implementare: È relativamente facile da capire e implementare.
* veloce: È generalmente più veloce degli algoritmi che garantiscono soluzioni ottimali (come la ricerca della forza bruta). La complessità temporale è in genere O (n^2), dove n è il numero di nodi.
* Approssimazione ragionevole: Di solito fornisce un'approssimazione ragionevolmente buona del tour ottimale TSP, specialmente quando le distanze soddisfano la disuguaglianza del triangolo (cioè la distanza diretta tra due punti è sempre inferiore o uguale alla somma delle distanze lungo qualsiasi altro percorso).
In sintesi:
L'algoritmo di inserimento più vicino è un avido euristico che costruisce un tour TSP aggiungendo ripetutamente il nodo non visitato più vicino al tour esistente. Sebbene non sia garantito per produrre la soluzione ottimale, è un modo rapido e semplice per trovare un'approssimazione ragionevolmente buona. Si concentra sulla minimizzazione degli aumenti della distanza locale ad ogni passaggio.
networking © www.354353.com