Aká je časová zložitosť algoritmu chrbta?

Časová zložitosť algoritmu spätného sledovania je všeobecne exponenciálna , hoci sa môže líšiť v závislosti od problému a jeho obmedzení. Neexistuje žiadna jediná časová zložitosť „The“ pre spätné sledovanie, pretože veľmi závisí od:

* Počet možností v každom kroku: Ak máte v každom kroku výber *b *a hĺbka stromu vyhľadávania je *d *, potom zložitosť môže byť o (b

d ).

* Špecifické obmedzenia a techniky prerezávania problému: Spätné sledovanie často zahŕňa prerezávanie priestoru vyhľadávania. Ak dokážete účinne prerezať vetvy, ktoré nevedú k riešeniu, môžete výrazne znížiť vyhľadávací priestor a zlepšiť výkon. Účinnosť stratégie prerezávania silne ovplyvňuje zložitosť poslednej času.

* Povaha problému: Niektoré problémy sú vo svojej podstate prístupnejšie k spätnému sledovaniu ako iné.

Tu je zrútenie toho, prečo je to všeobecne exponenciálne a niektoré príklady:

* Exponenciálna povaha: Backtracking skúma všetky možné kombinácie alebo permutácie, kým sa nenájde riešenie. V najhoršom prípade bude musieť preskúmať veľkú časť vyhľadávacieho priestoru, čo vedie k exponenciálnemu rastu počtu navštívených uzlov.

* Príklady a ich zložitosť:

* n-queens Problém: Nájdenie všetkých možných umiestnení N Queens na šachovnici NXN tak, že sa žiadne dve kráľovné neohrozujú navzájom. Časová zložitosť je približne O (n!), V najhoršom prípade. Techniky prerezávania môžu výrazne zlepšiť výkon.

* Problém s cestovným predajcom (TSP): Nájdenie najkratšej možnej trasy, ktorá navštívi každé mesto presne raz a vráti sa do východiskového mesta. Naivný prístup k spätnému sledovaniu by mal časovú zložitosť O (n!), Kde „n“ je počet miest. Pobočka a viazané sa používajú ako prerezávanie pre rýchlejšie vykonanie.

* Problém s podmnožinou: Určenie, či existuje podmnožina danej množiny čísel, ktorých súčet sa rovná cieľovej hodnote. Časová zložitosť môže byť O (2 ^{n ), kde „N“ je počet prvkov v sade, pretože možno budete musieť zvážiť všetky možné podskupiny.}

* Sudoku Solver: V najhoršom prípade môže riešiteľ Sudoku vyskúšať veľké množstvo možností pre každú prázdnu bunku. Aj keď teoreticky exponenciálna, dobrá heuristika a obmedzenia robia sudoku v reálnom svete veľmi rýchlo.

* Graf sfarbenie: Priradenie farieb k vrcholom grafu tak, že žiadne dve susedné vrcholy nemajú rovnakú farbu. Najhorší prípad je exponenciálny, ale efektívnosť závisí od toho, ako si objednáte uzly.

* Faktory ovplyvňujúce časovú zložitosť:

* hĺbka rekurzie: Čím hlbší je strom vyhľadávania, tým viac výpočtov je potrebných.

* Faktor vetvenia: Počet možností v každom uzle stromu vyhľadávania. Väčší vetvovací faktor vedie k rýchlejšiemu exponenciálnemu rastu.

* prerezávanie: Efektívne prerezávanie znižuje priestor na vyhľadávanie a zlepšuje výkon. Prerezávanie je jediným najdôležitejším faktorom, ktorý je potrebné zvážiť.

v súhrne:

Aj keď je ťažké poskytnúť presnú časovú zložitosť pre spätné sledovanie všeobecne, je možné povedať, že je zvyčajne exponenciálny (o (B

d

) alebo o (2 n ) alebo o (n!)) V najhoršom prípade. Skutočná časová zložitosť je silne ovplyvnená štruktúrou problému, účinnosťou akýchkoľvek použitých stratégií prerezávania a veľkosťou vstupu. Je dôležité navrhnúť algoritmy spätného sledovania s efektívnym prerezávaním, aby ste sa vyhli prieskumu zbytočných ciest. V niektorých prípadoch môže byť orezávanie tak účinné, že v praxi spôsobuje, že algoritmus je oveľa rýchlejší, ako by naznačovala jeho najhoršia exponenciálna zložitosť. Avšak pre mnoho problémov, dokonca aj pri prerezávaní, zostáva spätné sledovanie neodmysliteľne neefektívne pre veľké veľkosti vstupov.

• Predchádzajúca strana: Aká je časová zložitosť algoritmov spätného sledovania? 
• Ďalšia strana: Aká je časová zložitosť algoritmu spätného sledovania?