Aká je časová zložitosť algoritmu spätného sledovania?

Časová zložitosť algoritmov spätného sledovania je všeobecne exponenciálna , špecificky sa často vyjadrené ako o (b^d) , kde:

* b je vetviaci faktor (počet možných možností v každom rozhodovacom bode).

* d je hĺbka stromu vyhľadávania (maximálny počet rozhodnutí, ktoré je potrebné prijať, aby sa dosiahlo riešenie).

Vysvetlenie:

BackTracking skúma všetky možné riešenia tým, že systematicky vybuduje kandidátske riešenie jeden krok po druhom. V každom kroku kontroluje, či je súčasný kandidát sľubný (t. J. Ak by to mohlo viesť k platnému riešeniu). Ak je kandidát sľubný, algoritmus rekurzívne skúma ďalšie rozhodnutia. Ak kandidát nie je sľubný („slepá ulička“), algoritmus * ustúpi * do predchádzajúceho kroku a pokúsi sa inú voľbu.

Pretože algoritmus skúma strom možností a počet vetiev môže rásť rýchlo, časová zložitosť môže byť veľmi veľká, najmä keď sa zvyšuje hĺbka `d`.

Prečo exponenciálny?

Myslite na to ako na vyhľadávanie stromov. Ak má každý uzol v strome `b` deti (vetviaci faktor` b`) a maximálna hĺbka stromu je „d`, potom v najhoršom prípade by ste potenciálne preskúmali všetky uzly` b^d`.

Dôležité úvahy:

* Najhorší scenár: Časová zložitosť O (B^d) je zvyčajne scenár * najhoršieho prípadu. Skutočný beh runtime do značnej miery závisí od problému a efektívnosti prerezávania (ako efektívne môže algoritmus identifikovať a vyhnúť sa skúmaniu nepomoderných vetiev).

* prerezávanie: Algoritmy dobrého spätného sledovania využívajú rôzne techniky prerezávania na výrazné zníženie priestoru vyhľadávania. Prerezávanie môže dramaticky vylepšiť runtime, ale v najhoršom prípade nemení prirodzenú exponenciálnu povahu algoritmu.

* Príklad: Klasickým príkladom je riešenie problému N-queens. Na umiestnenie N Queens na šachovnicu NXN je vetvinový faktor súvisiaci s počtom dostupných stĺpcov v rade a hĺbka súvisí s počtom riadkov. Najhoršia časová zložitosť sa výrazne znížila kontrolou konfliktov (útočiacich na kráľovné) v každom kroku, čo srezáva mnohé z potenciálnych vetiev.

* Ostatné faktory: Okrem `b` a` d` môžu ďalšie faktory ovplyvniť runtime. Významným faktorom môže byť napríklad čas potrebný na vyhodnotenie toho, či je kandidátske riešenie sľubné.

* np-kompletnosť: Mnoho problémov, ktoré sa vyriešia pomocou spätného sledovania, sú komplexné NP. To znamená, že sa verí, že neexistuje žiadny algoritmus polynomiálneho času, ktorý by ich vyriešil všeobecne, a spätné sledovanie sa často stáva nevyhnutným (aj keď niekedy neefektívnym) prístupom.

v súhrne:

Zatiaľ čo spätné sledovanie môže byť výkonnou technikou riešenia problémov, jej exponenciálna časová zložitosť znamená, že je najvhodnejšia pre problémy, kde:

* Veľkosť problému je relatívne malá.

* Na výrazné zníženie vyhľadávacieho priestoru je možné použiť efektívne stratégie prerezávania.

* Približné riešenie je prijateľné, ak presné riešenie je príliš časovo náročné.

Ak je váš problém veľký a prerezávanie je neúčinné, možno budete musieť zvážiť alternatívne algoritmy alebo aproximačné techniky.

• Predchádzajúca strana: Aká je časová zložitosť algoritmu chrbta? 
• Ďalšia strana: No