Ristsõna koostamine kasutades kitsenduste rahuldamist ja libalõõmutamist
Nimi
Pavel Tomozov
Kokkuvõte
Selle töö eesmärk on luua programm, mis koostab ristsõnu, kasutades kahte meetodit:
kitsenduste rahuldamist (KR) ahne algoritmiga ja libalõõmutamist (LL), ning võrrelda nende
meetodite efektiivsust. Tööd hakatakse kasutama õppematerjalina aine Tehisintellekt I
õpetamisel.
Ristsõna koostamine on üks tehisintellekti probleemidest, mis kuulub NP-täielike klassi.
Seega hea lahenduse leidmine nõuab palju ressursse ja aega. Aga eksisteerivad meetodid, mis
võimaldavad lahenduse leidmise aega vähendada. Nende hulgas on ka KR ja LL.
KR kasutades seatakse antud ülesandele kitsendusi, mis teevad lahendamise lihtsamaks.
Ristsõna koostamisel kehtivad järgmised kitsendused:
1.Sõna ei saa olla lühem, kui ruutude järjend, kuhu seda pannakse.
2.Sõna ei saa olla pikem, kui ruutude järjend, kuhu seda pannakse.
3.Kui järjendis on mõned tähed juba olemas, siis sõna, mis pannakse sellesse järjendisse, peab
neid tähti sisaldama täpselt nendel samadel positsioonidel ja ei saa sisaldada mingeid teisi
tähti nendel positsioonidel.
Kui sõna rahuldab neid tingimusi, siis teda võetakse vastu ning ahne algoritm otsustab,
kasutades heuristilist funktsiooni, kas see sõna on parim lahendus selles olukorras.Niiviisi
püüab programm lõpliku sammude hulgaga optimaalse lahenduseni jõuda.
LL töötab nii: antud on suvaline algseisund s, leida tema naaberseisund s', kui uus seisund on
jooksvast seisundist parem, siis valida see, aga kui leitud seisund on jooksvast seisundist
halvem, siis kasutada tõenäosus funktsiooni P, et otsustada, kas valida seda seisundit või
mitte. Sellist operatsiooni korratakse kuni rahuldav lahendus on leitud või algoritm on juba
teinud lubatud arvu samme. Tõenäosus, et algoritm valib uueks seisundiks halvema seisundi
väheneb aja jooksul (kooskõlas nn temperatuuri alanemisega).
Meetodeid on testitud ja võrreldid, kasutades erinevaid heuristikuid.
Lõputöö keel
inglise
Lõputöö tüüp
Bakalaureus - Informaatika
Juhendaja(d)
Mare Koit
Kaitsmise aasta
2013