A kiválasztott változat és az aktuális verzió közötti különbségek a következők.
inf-prog-fszi:backtrack_-_visszalepeses_kereses [2017/06/15 12:54] beistvan létrehozva |
inf-prog-fszi:backtrack_-_visszalepeses_kereses [2017/06/23 17:56] (aktuális) beistvan |
||
---|---|---|---|
Sor 1: | Sor 1: | ||
+ | ====== Backtrack - visszalépéses keresés ====== | ||
+ | |||
+ | |||
+ | **Feladat**: | ||
+ | |||
+ | Először megpróbálunk az első sorozatból választani egy elemet, ezután a következőből, | ||
+ | |||
+ | Ha nincs jó választás, | ||
+ | |||
+ | <code bash visszalepes1.txt> | ||
+ | Eljárás: | ||
+ | I:=1 | ||
+ | Ciklus amíg I>=1 és I<=N | ||
+ | Ha VAN_JÓ_ESET(I) akkor I:=I+1 | ||
+ | X(I):=0 | ||
+ | különben I:=I-1 | ||
+ | Ciklus vége | ||
+ | VAN: | ||
+ | Eljárás vége. | ||
+ | </ | ||
+ | |||
+ | Az I. sorozatból úgy választunk elemet, hogy próbálunk mindaddig új elemet venni, amíg egyáltalán van további elem, és az éppen vizsgált nem felel meg a feladatnak. | ||
+ | |||
+ | Ha a keresgélés közben a sorozat elemei nem fogytak el, akkor az előző szintnek válaszolhatjuk azt, hogy sikeres volt a választás. | ||
+ | |||
+ | Ha pedig az utolsó sem felelt meg, akkor azt, hogy vissza kell lépni az előző sorozathoz. | ||
+ | |||
+ | <code bash visszalepes2.txt> | ||
+ | VAN_JÓ_ESET(I): | ||
+ | Ciklus | ||
+ | X(I): | ||
+ | amíg X(I)< | ||
+ | Ciklus vége | ||
+ | VAN_JÓ_ESET: | ||
+ | Eljárás vége. | ||
+ | </ | ||
+ | |||
+ | Rossz választásnak nevezzük azt, amelyet a korábbi választások közül valamelyik megakadályoz. | ||
+ | |||
+ | <code bash visszalepes3.txt> | ||
+ | ROSSZ_ESET(I, | ||
+ | J:=1 | ||
+ | Ciklus amíg J < I és (J,X(J)) nem zárja ki (I,X(I))-t | ||
+ | J:=J+1 | ||
+ | Ciklus vége | ||
+ | ROSSZ_ESET: | ||
+ | Eljárás vége. | ||
+ | </ | ||
+ | |||