Sellised on enamus planeerimisülesannetest, näiteks tunniplaani koostamise ülesanne. See on vana ja paljudes koolides ja kõrgkoolides esinev probleem, kuid rahuldavalt töötavat arvutiprogrammi pole seni veel loodud, nii et näiteks Tallinna Tehnikaülikooli tunniplaanid tehakse seniajani käsitsi.
Praktikas lahendatakse selliseid planeerimisprobleeme tavaliselt nii, et arvuti koostab mingid esialgsed plaanivariandid (võttes arvesse kõige olulisemaid piiranguid), mille seast siis inimeksperdid valivad rahuldava või modifitseerivad mõnd arvuti esitatud varianti. Selline strateegia annab tavaliselt täiesti rahuldava lahenduse.
Vaatleme järgnevas 1988. a Tampere Tehnikaülikoolis põhjamaade tehisintellektikonverentsi ajakava koostamisel tekkinud planeerimisprobleemi. Ka siin esines mitmeid vastuolulisi piiranguid, kuid tudengite poolt Prolog-kursuse harjutusülesandena koostatud programm töötas niivõrd hästi, et seda kasutati nii selle kui ka mitme järgneva konverentsi ajakava planeerimisel.
Lähteandmetena olid konverentsi sessioonid ja nende kestvused:
Prolog-programmeerimine_1, 90 min
Prolog-programmeerimine_2, 120 min
Teadmisete_esitamisviisid, 60 min
jne
Sessioonid tuli paigutada Tampere Tehnikaülikooli auditooriumidesse, kui need olid vabad (kooli
tunniplaani ei muudetud):
10.00 H210 45 min
12.00 H220 240 min
(s.t. auditoorium H210 on alates kella 10-st 45 minutit vaba jne).
Need algandmed võib esitada predikaatidega sessioon, auditoorium:
auditoorium([h210,10,60]).
auditoorium([h212,12,60]).
auditoorium([b200,12,240]).
auditoorium([b210,14,120]).
Predikaat planeeri/1 kogub algul süsteemipredikaadi findallabil kõik sessioonid ja auditooriumid nimistuteks ja käivitab siis tegeliku planeerimispredikaadi planeeri/4, mis paigutab sessioonid auditooriumidesse:
planeeri(Plaan) :-
sessioonid(Sessioonid),
auditooriumid(Auditooriumid),
planeeri(Sessioonid,Auditooriumid,[],Plaan),
esita(Plaan).
Sessioonide auditooriumidesse paigutamisel peab jälgima, et auditoorium oleks vaba piisavalt kaua. Planeerimine lõpeb, kui kõik sessioonid on paigutatud (sesioonide nimistu on tühi): enne kasutajale esitamist järjestatakse plaan sessioonide algusaegade järgi:
planeeri([],_,Plaan,Plaan0) :-
predsort(enne,Plaan,Plaan0).
planeeri([Sessioon|Sessioonid],Auditooriumid,Plaan,Plaan0) :-
member(Auditoorium,Auditooriumid),
sobib(Sessioon, Auditoorium),
delete(Auditooriumid, Auditoorium, Auditooriumid1),
planeeri(Sessioonid, Auditooriumid1,[[Sessioon, Auditoorium]|Plaan],Plaan0).
sobib([Sessioon,Kestvus],[Auditoorium,Aeg,Vapaa]) :-
Kestvus =< Vapaa.
Enne kasutajale esitamist järjestatakse plaan sessioonide algusaegade järgi. Plaan on nimistu, mille liikmed on üsna keeruka struktuuriga : [[Sessioon,Kestvus],[Auditoorium,Aeg,Vapa]] , kuid Swi-Prologi sisseehitatud järjestamispredikaadi predsort abil on ka keerukate liikmetega nimistute järjestamine lihtne: predsort esimene argument on kasutaja poolt kirjeldatud predikaat, mis määrab järjestatava nimistu liikme (termi) struktuuri põhjal, millal liikmete vahel kehtivad suhted < , = ja >; kuna enamus sessiooni kirjeldava termi liikmetest pole olulised, esineb kirjelduses palju anonyymseid muutujaid _ :
enne(<,[[_,_],[_,Aeg,_]], [[_,_],[_,Aeg1,_]]):-
Aeg < Aeg1,!.
enne(=,[[_,_],[_,Aeg,_]], [[_,_],[_,Aeg,_]]):-!.
enne(>,_,_).
Ülaltoodu on täiesti "sirgjooneline" planeerimisprogramm. Sobiva ajakava saamiseks tuleb
arvesse võtta ka palju kitsendusi: sessioonide vahele peab sobitama kohvipausid, samateemalised
(Prolog-programmeerimine_1, Prolog-programmeerimine_2 jt) sessioonid peaks toimuma võimalikult üksteise järel,
kuid mitte samal ajal (kõigil sellest teemast huvitatutel peaks olema võimalik kuulata kõikki ettekandeid); kõigi konverentsipäevade koormus (konverents kestis 3 päeva) peaks olema
enam-vähem sama jne, sageli esitasid ettekandjad lisatingimusi (mõni ei jõudnud kohale konverentsi alguseks või
pidi lahkuma enne konverentsi lõppu jne). Kõigi tingimuste arvessevõtmisel poleks lahendust üldse leidunud,
sellepärast anti tingimustele kaalud: need, mida tingimata pidi arvesse võtma (esinejate kohalolek) said suure kaalu, kuid
need, mille suhtes võis tingida (samateemaliste sessioonide ajaline lähedus) said väiksema kaalu ja plaani
koostamise järel arvutas programm kohe ka selle kaalu (võttes arvesse kõigile piirangutele antud kaale).
Kui ülesanne on suur, (kolmepäevasel konverentsil oli kokku ligi viiskümmend sessiooni), ei ole
mõtet lasta arvutil
otsida kõigi plaanide seast parimat, pealegi sõltub parima valik kitsendustele antud kaaludest
ja sellepärast ei oleks võibolla praktikas üldse sobinud.
Programm hakkas väljastama nn lokaalseid maksimume:
ta arvutas uusi plaane kuni plaanid paranesid (kirjeldatud kaalude põhjal);
kui järgmisena leitud plaan osutus halvemaks kui senine parim, väljastati senine parim (lokaalne optimum) ja
kasutaja pidi otsustama, kas jätkata plaanide arvutamist või oli äsjaväljastatud plaan
kasutamiseks sobiv. Kuna programmi töö algul leiti senistest paremaid plaane
suhteliselt sageli ja senine parim kaal kasvas kiiresti, ei olnud mõtet
väljastada neid kõikki, programm hakkas lokaalselt optimaalseid plaane väljastama alles siis, kui
uus maksimum enam palju ei erinenud eelnevast.
Selline strateegia osutus väga õnnestunuks, tavaliselt kõlbas juba teine-kolmas arvuti poolt väljastatud
plaan ja edasisel arvutamisel need enam oluliselt ei paranenud.
Olgu plaanile näitek esitatud nõuded:
- paralleelsessioone ei või olla;
- sessioonide vahelised vaheajad (kokku) peavad olema võimalikult väikesed
(ka need nõuded on sisuliselt vastuolulised: kui kõik sessioonid toimuks samal ajal, ei oleks
vaheaegu üldse!)
Paralleelsessioonidega plaanide avastamine on lihtne (kuna kõik loengud algasid alati täistundidel):
pole_samaaegseid([[[_,_],[_,Aeg,_]]|Plaan]):-
not(member([[_,_],[_,Aeg,_]],Plaan)),
pole_samaaegseid(Plaan).
pole_samaaegseid([]).
vahed([[[Sessioon,Kestvus],[Auditoorium,Aeg,Vapaa]],[[Sessioon1,Kestvus1],[Auditoorium1,Aeg1,Vapaa1]]|Plaan],Vahed,Vahed0):-
Vaheaeg is Aeg1 - (Aeg + Kestvus/60),
Vahed1 is Vahed + Vaheaeg,
vahed([[[Sessioon1,Kestvus1],[Auditoorium1,Aeg1,Vapaa1]]|Plaan], Vahed1,Vahed0).
vahed([_],Vahed,Vahed).
Kell 10.00 auditooriumis h210 teadmiste_esitamisviisid, kestvus: 50 min
Kell 12.00 auditooriumis b200 prolog_programmeerimine1, kestvus: 80 min
Kell 14.00 auditooriumis b210 prolog_programmeerimine2, kestvus: 110 min
1.83333
...
Kell 11.00 auditooriumis h212 teadmiste_esitamisviisid, kestvus: 50 min
Kell 12.00 auditooriumis b200 prolog_programmeerimine2, kestvus: 110 min
Kell 14.00 auditooriumis b210 prolog_programmeerimine1, kestvus: 80 min
0.333333
Lennukompanii lennuplaan on salvestatud
formaadis: Hind Lennukood Lähtelinn Lähteaeg
Sihtkoht Saabumisaeg;
hind on reaalarv (kümnendosa eraldajaks koma ja kümnendosa kohal '-'), lennukood
-kaks suurtähte ja kolm või neli numbrit, lähte ja sihtkoht esitatakse kolmest
suurtähest koosneva koodina ja ajad formaadis tund
: min,
näiteks Finnairi lennud Brüsselisse näevad välja nii:
111,-
AY6783 HEL 13:30 BRU
15:10
111,- AY817 HEL 16:35 BRU
18:15
Koosta predikaat, mis oskaks planeerida mitmest järjestikusest lennust koosneva reisi ja arvutada selle kogumaksumuse; mitme võimaliku marsruudi korral valida odavaim; saabumise ja järgmise reisi lähteaja vahel peab olema vähemalt 45 min, kuid mitte rohkem kui 3 tundi; reis võib minna ka üle kesköö, näit saabumisaja 23.30 järel järgmine lähteaeg võib olla 00:45
©2004
Jaak Henno