Legközelebbi szomszéd algoritmus

0 Comments

Ezek az algoritmus lépései:

  1. inicializálja az összes csúcsot látogatatlanként.
  2. válasszon ki egy tetszőleges csúcsot, állítsa be jelenlegi csúcsként u. jelölje meg az u-t látogatottnak.
  3. Ismerje meg a legrövidebb él, amely összeköti az aktuális csúcs u és egy nem látogatott vertex v.
  4. állítsa v, mint a jelenlegi vertex u.Mark v meglátogatott.
  5. ha a tartomány összes csúcsát meglátogatják, akkor fejezze be. Más, menj a 3. lépésre.

a meglátogatott csúcsok sorrendje az algoritmus kimenete.,

a legközelebbi szomszéd algoritmus könnyen végrehajtható, gyorsan végrehajtható, de néha rövidebb útvonalakat is kihagyhat, amelyeket emberi betekintéssel könnyen észrevehet, “kapzsi” jellege miatt. Általános útmutatóként, ha a túra utolsó néhány szakasza hosszúságban összehasonlítható az első szakaszokkal, akkor a túra ésszerű; ha sokkal nagyobbak, akkor valószínű, hogy sokkal jobb túrák léteznek. Egy másik ellenőrzés egy olyan algoritmus használata, mint például az alsó kötésű algoritmus, annak becslésére, hogy ez a túra elég jó-e.,

a legrosszabb esetben az algoritmus olyan túrát eredményez, amely sokkal hosszabb, mint az optimális túra. Pontosabban, minden állandó r esetében van egy példány az utazó ügynök problémájáról, hogy a legközelebbi szomszéd algoritmus által kiszámított túra hossza nagyobb, mint az optimális túra hosszának r-szerese. Sőt, minden egyes város esetében olyan távolságok vannak kijelölve a városok között, amelyekre a legközelebbi szomszéd heurisztikus a lehető legrosszabb túrát hozza létre., (Ha az algoritmust minden csúcson kiindulási csúcsként alkalmazzák, akkor a legjobb elérési út jobb lesz, mint legalább N/2-1 más túra, ahol N A csúcsok száma.)

a legközelebbi szomszéd algoritmus egyáltalán nem talál megvalósítható túrát, még akkor sem, ha létezik.


Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük