Ako funguje algoritmus spätného sledovania na efektívnom preskúmaní všetkých možných riešení vo vyhľadávacom priestore?

Algoritmus spätného sledovania efektívne skúma vyhľadávací priestor tým, že systematicky skúša rôzne kombinácie a opustenie ciest, ktoré sú zaručené, že nevedú k riešeniu. Funguje to na princípe * hĺbkového hľadania * s zásadným doplnkom: prerezávanie .

Tu je zrútenie toho, ako to funguje:

1. Štátne zastúpenie priestoru: Problém je znázornený ako strom alebo graf, kde každý uzol predstavuje čiastočné riešenie. Koreňový uzol predstavuje počiatočný stav a pobočky predstavujú možnosti alebo rozhodnutia prijaté v každom kroku. Listy predstavujú kompletné riešenia alebo slepé uličky.

2. Algoritmus začína v koreňovom uzle a skúma jednu vetvu po druhej, čo najhlbšie (hĺbka prvé). To znamená, že robí sériu možností, kým nenájde riešenie alebo nezasiahne slepú uličku.

3. Kontrola/sľubné obmedzenia: V každom uzle sa vykonáva kontrola, aby sa zistilo, či je súčasné čiastočné riešenie stále „sľubné“ - čo znamená, že je možné ho rozšíriť na úplné riešenie. Tu prichádza efektívnosť. Ak súčasné čiastočné riešenie porušuje obmedzenia problému (napr. V hádanke Sudoku, ktorý umiestni číslo, ktoré už je v riadku, stĺpci alebo bloku 3x3), algoritmus vie, že túto vetvu nemusí ďalej skúmať. Toto je prerezávanie krok.

4. spätné sledovanie: Ak sa uzol považuje za sľubný, alebo ak listový uzol predstavuje neúspešný pokus o nájdenie riešenia, algoritmus „spätne“ do predchádzajúceho uzla (jeho rodič) a pokúsi sa inú vetvu (iná voľba). Zahŕňa to zrušenie rozhodnutí v tejto vetve a skúmanie alternatívnych možností.

5. Ak listový uzol predstavuje úplné a platné riešenie, algoritmus našiel riešenie a môže sa zastaviť (ak nájdenie jedného riešenia je dostatočné) alebo pokračujte v hľadaní iných riešení spätným sledovaním a skúmaním iných vetiev.

Príklad:problém N-queens

Zoberme si umiestňovanie N Chess Queens na šachovnici N × N tak, aby sa žiadne dve kráľovné neohrozili.

* Stav priestoru: Každý uzol v strome predstavuje čiastočné umiestnenie kráľovien na doske.

* Choice: Na každej úrovni stromu sa vyberie výber, kam umiestniť ďalšiu kráľovnú do stĺpca.

* obmedzenie: Obmedzenie je, že žiadne dve kráľovné nemôžu byť v rovnakom riadku, stĺpci alebo diagonále.

* prerezávanie: Ak umiestnenie kráľovnej porušuje obmedzenie, táto pobočka je prerezaná. Algoritmus ešte viac nepreskúmajú túto vetvu.

* backtracking: Ak umiestnenie vedie k porušeniu, algoritmus sa vráti do predchádzajúceho stĺpca, odstráni kráľovnú a v tomto stĺpci sa pokúsi o inú pozíciu.

v súhrne: Účinnosť spätného sledovania je odvodená z jeho schopnosti vyhnúť sa skúmaniu zbytočných častí priestoru vyhľadávania inteligentnými prerezávajúcimi pobočkami, ktoré sú zaručené, že nevedú k riešeniu. To významne skracuje čas výpočtu v porovnaní s vyčerpávajúcimi metódami vyhľadávania, ktoré by vyskúšali každú jednotlivú kombináciu. Efektívnosť závisí od toho, ako dobre je „sľubná“ kontrola navrhnutá na identifikáciu a eliminovanie nežíovateľných ciest na začiatku vyhľadávania.

• Predchádzajúca strana: Údaje a informácie o všetkých predtým realizovaných projektoch sú v? 
• Ďalšia strana: Môžete s cloudovým úložiskom načítať svoje údaje kedykoľvek odkiaľkoľvek na svete?