Linkek

Programozási ismeretek

Alapoktól a speciálisig...

Backtrack

visszalépéses keresés

"A visszalépéses algoritmus általános elve

A bizonyos problémák visszalépéses kereséssel való megoldásának stratégiája már viszonylag régóta ismert, de nagy műveletigénye miatt gyakorlati alkalmazása csak a számítógépek nagyarányú elterjedésével válhatott jelentőssé.

A megoldás alapja, hogy szisztematikus próbálgatások sorozatával próbálunk eljutni a megoldáshoz. Ha a megoldási folyamat egy adott szintjén beláttuk, hogy onnan nincs út a megoldáshoz, akkor visszatérünk az előző szintre, és ott próbálunk más utat találni.

A visszalépéses algoritmus egy általános megfogalmazása

A visszalépéses keresés algoritmusa alkalmazható minden olyan probléma megoldásakor, amikor a feladat megfeleltethető az alábbi általános megfogalmazásnak.

Adott n darab nem üres, véges elemszámú sorozat. Legyenek elemszámaik rendre c1; c2; …ci;…cn, ahol ci az i. sorozat elemszáma és 0< ci . Tehát a i, ci az i. sorozat utolsó elemét jelöli.

Határozzunk meg egy n elemű sorozatot úgy, hogy i. elemét az i. sorozat ci számú eleme közül választjuk, és az adott sorozatból való választást befolyásolja, hogy a többi sorozatból már milyen elemeket választottunk ki."

Útkeresés

(Sulinet Tudásbázis)

Klasszikus backtrackes feladatok: ELTE

Három kidolgozott példa következik:

  1. Az egyik H számból N darab számot húzunk (pl. 6-os lottó vagy 5-ös lottó). Írjuk ki az összes lehetséges húzást.
  2. A másik a klasszikus "királynős" feladat. Egy NxN-es sakktáblán helyezzünk el N darab királynőt úgy, hogy ne üssék egymást!
  3. A harmadik pedig, a jól ismert sudoku játék.

SZÁMHÚZÁS - Python példa (letöltés: szamhuzas.py)

KIRÁLYNŐ - Python példa (letöltés: kiralyno.py)

SUDOKU - Python példa (letöltés: sudoku.py)

SUDOKU - C++ példa (letöltés: sudokuC++.cpp)