Adatszerkezet a probléma megoldásához
Egy sorozat tárolása egy vektorban történhet. Az egyes sorozatok elemszáma c1; c2; …ci;…cn, tehát ha Max(c1; c2; …ci;…cn) elemszámú vektort alkalmazunk, akkor abban biztosan el tudjuk tárolni bármely sorozat elemeit. Mivel n sorozattal írható le a probléma, n számú vektorra lesz szükség, ahol az i. sorozat elemeit az i. vektor elemei az első ci számú eleme tárolja (1- ci). Természetesen akkor minden sorozathoz meg kell jegyeznünk még az elemszámukat is. A megoldás során ki kell választanunk minden sorozatnak pontosan egy elemét. Hogy mely elemét választottuk az i. sorozatnak, az szintén jellemezhető a sorozat egy elemének sorszámával, ezt jelölje ki (1£ ki £ ci). Ezt az információt is tekinthetjük a sorozathoz tartozónak.
Ezek alapján a következő adatszerkezet alkalmas a szükséges adatok tárolására.
Konstans
Maxelem=a leghosszabb sorozat elemszáma;
N=A sorozatok száma;
Típus
SorozatElemT= a tárolandó sorozat elemeinek típusa;
Elemek= Tömb[1..Maxelem] SorozatElemT;
Sorozat= Rekord
C: Egész;
A: Elemek;
K: Egész;
RekordVége;
Változó
S: Tömb [1..N] Sorozat;
Megjegyzés:
S[I].C: az i. sorozat elemszáma.
S[I].A[J]: az i. sorozat j. eleme.
S[I].K: az i. sorozatból kiválasztott elem sorszáma.
S[I].A[S[I].K]: az i. sorozatból kiválasztott elem értéke.
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 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 a 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.
A megoldó-algoritmus funkcionális elemei
A megoldás menete:
Az első sorozattal kezdve, kiválasztjuk a sorozat első megfelelő elemét, majd aktuálissá tesszük a következő sorozatot.
Az aktuális sorozat elemeit sorban megvizsgálva kiválasztjuk annak első megfelelő elemét. Ha van ilyen, akkor aktuálissá tehetjük a következő sorozatot, ha pedig nem található az aktuális sorozatnak megfelelő eleme, akkor az eggyel kisebb sorszámú sorozat legyen az aktuális, és abban keresünk újabb megfelelő elemet, a korábban nem vizsgáltak között.
A feladatnak megtaláltuk egy megoldását, ha az utolsó sorozatból is sikerült megfelelő elemet választani. Nincs megoldása a feladatnak, ha az első sorozat utolsó eleméhez sem lehetett megfelelő elemeket választani a többi sorozat elemei közül.
A feladat minden megoldásának megkeresése
A visszalépéses feladat összes megoldását meghatározhatjuk, ha egy sikeres megoldás után, tovább folytatjuk a keresést az utolsó sorozatban, mintha nem találtunk volna abban megfelelő elemet.
21. századi közoktatás - fejlesztés, koordináció (TÁMOP-3.1.1-08/1-2008-0002)
