Feladványkészítés redukció segítségével

Ezen a lapon kétféle redukcióról lesz szó. Az elsőt már leírtam a Fogalmak című lapon. Az algoritmus végigmegy a feladvány összes beírt elemén, ideiglenesen törli, és megnézi, hogy megoldható feladványt kapott-e. Ha igen, akkor ezt megjegyzi. Nézzük, hogy ez hogyan néz ki a gyakorlatban. Válasszunk egy olyan adatbázist, amelyben még találhatók redukálható feladványok. (Én az archiváltakban már csak nem redukálható feladványokat tárolok.) Ilyen a D-25.gsf (200). Először csak BS segítségével próbálkozzunk redukálni. Ezt kapjuk:

A program 11 db redukálási lehetőséget talált. A 110-es, 112-es és a 166-os feladványban több elemre vonatkozóan is. Ezeket a cellákat kiürítve (csak egyet-egyet, így 24 eleműek lesznek), újra megoldható feladványokat kapunk. Nézzük van-e olyan, amely kétszeresen redukálható, azaz 23 elemű feladványokat hozhatunk létre belőlük:

Pontosan azok, amelyekben többször is lehetett elemet elhagyni, kétszeresen redukálhatók. Eddig csak a BS metódus alkalmazásával próbáltunk redukálni. Kapcsoljuk most be a HS-t. Ezt kapjuk:

Összesen 331 db redukálási lehetőség van, nyilván azért, mert egy feladványban több is lehet. Minél több metódust használunk, annál több lesz az ilyen eset (csak a futási idő megnő). Például:

Látható, hogy ez így is lett, 399 lehetőséget talált, de a futási idő 167 másodperc volt. Míg a feladványkezelőben csak ellenőrzés hajtódik végre, természetesen mód van a redukció tényleges végrehajtására is. Megválaszthatjuk milyen metódusok segítségével történjen a redukció és mi legyen a Célfájl:

A másik redukció, amire utaltam, az előzőtől lényegesen különbözik. Itt is szükség van egy forrásállományra, amelyből feladványokat vesz elő az algoritmus. Ebben az esetben véletlenül töröl egy elemet a kiválasztott feladványból, majd ezt tekinti az indirekt keresés véletlen választásának, és ezzel folytatja a keresést. Ennek az alapkoncepciója az, hogy egy helyes feladványból könnyebb egy eggyel kisebb elemszámú feladványt generálni, mint egy teljesen véletlen feltöltésből. Ezzel mintegy kibővítettük a genetikus algoritmust. Abban bízunk, hogy egy jó feladványból származhatnak olyan információk, melyek az eggyel kisebb elemű feladványok keresésénél hasznosak lehetnek (természetesen mindezt mi nem tudjuk felfedezni, számunkra rejtve maradnak). Nem is csalódunk, működik a keresőprogram. Íme egy példa erre. A 19A.gsf (228) adatbázisból 7 perc alatt 10 darab 18-as feladványt tudtunk készíteni:

A képernyőről leolvasható, hogy 105-ször választott feladványt és átlagosan 1.635.487 elemi lépést kellet a keresések folyamán végrehajtani. Megfigyelhető még, hogy a keresés közben 75-ször fordult elő, hogy csak két hibára (két üres helyre) volt a teljes kitöltéshez az algoritmus.