Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Najbližším inzerčným algoritmom je heuristický algoritmus, ktorý sa používa na nájdenie približného riešenia problému cestovania (TSP). Cieľom TSP je nájsť tú najkratšiu možnú trasu, ktorá navštevuje každé mesto (uzol) presne raz a vráti sa do východiskového mesta.
Ako to funguje:
1. Inicializácia:
- Začnite s ľubovoľným uzlom ako počiatočnou prehliadkou (napr. Služba jedného uzla). Zavolajme tento uzol `start_node`.
- Nech `V` je súbor uzlov, ktoré ešte neboli pridané na turné.
2. iterácia:
- Nájdite najbližší uzol: Pre každý uzol `i` v aktuálnej prehliadke nájdite uzol` j` v `v` (sada neistených uzlov), ktorý je najbližšie k` i` (t. J. Má najmenšiu vzdialenosť). Tento „najbližší“ uzol `j` je ten, ktorý chceme vložiť. Matematicky nájdeme:
`j =argmin_ {v ∈ V} min_ {i ∈ Tour} dist (i, v)`
- Vložte najbližší uzol: Nájdite Edge (i, k) v súčasnej prehliadke, kde vloženie uzla `j` medzi uzlami` i` a `k` vedie k najmenšiemu zvýšeniu dĺžky zájazdu. To znamená, že nájdite `i` a` k` tak, že:
`Dist (i, j) + dist (j, k) - dist (i, k)` je minimalizovaný.
- Vložte uzol `j` medzi uzlami` i` a `k`, efektívne nahradiť okraj (i, k) dvoma hranami (i, j) a (j, k).
- Odstráňte uzol `j` zo sady neistených uzlov` v`.
3. Terminácia:
- Opakujte krok 2, kým sa do prehliadky pridajú všetky uzly (t. J. „V` nie je prázdny).
4. Zatvorenie slučky:
- Pripojte posledný uzol pridaný k prehliadke späť do `start_node`, aby ste dokončili cyklus.
Príklad:
Povedzme, že máme mestá A, B, C, D a E s nasledujúcimi vzdialenosťami:
`` `
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. Štart: Začnime s uzlom A ako počiatočné turné:`Tour ={a}`
2. iterácia 1:
- Najbližší uzol k A je B (vzdialenosť 10).
-Vložte B do prehliadky (a -> b -> a). `Tour ={a, b, a}`
3. iterácia 2:
- Nájdite najbližší neuverený uzol do akéhokoľvek uzla v aktuálnej prehliadke:
- najbližšie k A:C (15), D (20), E (25)
- najbližšie k B:C (35), D (25), E (30)
- minimum týchto vzdialeností je 15 (A až C).
- Zistite, kde vložiť C.
- vloženie C medzi A a B:15 + 35 - 10 =40
- vloženie C medzi B a A:35 + 15 - 10 =40
- Vložte C medzi A a B (alebo B a A). `Tour ={a, c, b, a}`
4. iterácia 3:
- Nájdite najbližší neistý uzol:
- najbližšie k:D (20), E (25)
- najbližšie k C:D (30), E (20)
- najbližšie k B:D (25), E (30)
- Minimálna vzdialenosť je 20 (C až E alebo A až D). Vezmime C k E.
- Vložte e:
- vloženie E medzi A a C:25 + 20 - 15 =30
- Vloženie E medzi C a B:20 + 30 - 35 =15 (minimálne!)
- vloženie E medzi B a A:30 + 25 - 10 =45
- Vložte e medzi C a B. `Tour ={a, c, e, b, a}`
5. iterácia 4:
- Zostáva iba uzol D.
- najbližšie k:D (20)
- najbližšie k C:D (30)
- najbližšie k E:D (10) (minimálne!)
- najbližšie k B:D (25)
- Vložte d:
- vloženie D medzi A a C:20 + 30 - 15 =35
- vloženie D medzi C a E:30 + 10 - 20 =20
- vloženie D medzi E a B:10 + 25 - 30 =5 (minimálne!)
- vloženie D medzi B a A:25 + 20 - 10 =35
- Vložte d medzi E a B. `Tour ={a, c, e, d, b, a}`
Optimalizácia (alebo skôr aproximácia) aspekty:
Najbližší inzerčný algoritmus optimalizuje iteratívne pridanie uzla, ktorý predstavuje najmenšie okamžité zvýšenie celkovej dĺžky zájazdu v každom kroku. Toto je chamtivý prístup, čo znamená, že robí najlepšiu voľbu v každej fáze bez toho, aby zvážil globálny vplyv tejto voľby.
* lokalita: Algoritmus sa zameriava na minimalizáciu miestnych vzdialeností. Vyberie uzol, ktorý je najbližšie k súčasnej prehliadke, s cieľom udržať pridaný segment prehliadky čo najkratší.
* Prírastkový rast: Prehliadka je postavená postupne pridaním jedného uzla naraz. Každé rozhodnutie vloženia je založené na súčasnom stave prehliadky, takže sa neplánuje dopredu, aby zistil, ako by pridanie konkrétneho uzla mohlo ovplyvniť budúce inzercie.
Obmedzenia:
* nie je optimálny: Najbližší algoritmus vloženia je heuristika, čo znamená, že nezaručuje absolútnu najkratšiu cestu. Môže uviaznuť v miestnej optime, kde trochu iná skorá voľba by mohla viesť k výrazne lepšiemu celkovému riešeniu.
* chamtivá príroda: Chamtivá povaha algoritmu môže viesť k suboptimálnym výberom, najmä v prípadoch, keď vzdialenosti nie sú jednotné. Niekedy môže výber o niečo ďalej ďalej otvoriť príležitosti pre kratšie spojenia neskôr.
* závislosť od štartovacieho uzla: Počiatočný uzol môže ovplyvniť poslednú prehliadku. Rôzne počiatočné uzly môžu mať za následok rôzne trasy.
Výhody:
* jednoduché implementácia: Je relatívne ľahké pochopiť a implementovať.
* rýchle: Všeobecne je rýchlejšie ako algoritmy, ktoré zaručujú optimálne riešenia (ako napríklad vyhľadávanie Brute-Force). Časová zložitosť je zvyčajne O (n^2), kde n je počet uzlov.
* Primeraná aproximácia: Zvyčajne poskytuje primerane dobrú aproximáciu optimálnej prehliadky TSP, najmä ak vzdialenosti uspokojujú nerovnosť trojuholníka (t. J. Priama vzdialenosť medzi dvoma bodmi je vždy menšia alebo rovná súčtu vzdialeností pozdĺž akejkoľvek inej cesty).
v súhrne:
Najbližším inzerčným algoritmom je chamtivá heuristika, ktorá vytvára prehliadku TSP opakovaným pridaním najbližšieho nevideného uzla do existujúcej prehliadky. Aj keď nie je zaručené, že vytvorí optimálne riešenie, je to rýchly a jednoduchý spôsob, ako nájsť primerane dobrú aproximáciu. V každom kroku sa zameriava na minimalizáciu miestnej vzdialenosti.