Uþduotis

Sudaryti programà, kuri nuskaito ið duomenø failo jau sudarytà vidurinës mokyklos penktø - dvyliktø klasiø vienos savaitës pamokø tvarkarastá ir já optimizuoja.

Uþduoties analizë

Pagrindinis uþdavinio tikslas - optimizuoti tvarkaraðtá taip, kad mokytojai turëtø kuo maþiau langø. Pamokø tvarkaraðèio uþdavinys iðsiskiria tuo, kad jam egzistuoja apribojimai, t.y., pamokos tvarkaraðtyje iðdëstomos pagal tam tikras taisykles:

  1. Pamokø skaièius savaitëje turi atitikti mokymo planà;
  2. Mokiniai negali turëti langø;
  3. Mokytojas ir mokinys vienu metu turi tik po vienà pamokà;
  4. Kai kurios pamokos gali bûti sudvejintos (pvz.: dvi lietuviø klb. pamokos ið eilës);
  5. Kai kurios pamokos gali bûti dvigubos (klasë gali bûti skaidoma á grupes vienai pamokai. Ðioms grupëms pamokos turi vykti tuo paèiu metu);
  6. Mokytojas gali bûti uþimtas,t.y., tam tikromis valandomis negali dëstyti;
  7. Egzistuoja vienos dienos maksimalus pamokø skaièius.

Pradiniai programos duomenys - jau sudarytas realus vidurinës mokyklos tvarkaraðtis.
Tvarkaraðèio programa duomenis nuskaito ið dviejø failø:

Teorinë dalis

Tvarkaraðèio uþdavinys yra priskiriamas NP-complete uþdaviniø klasei. Norint rasti tikslø sprendiná, naudojama formulë T=C*2^m. Taèiau galimø sprendimo variantø yra labai daug, todël naudojama heuristika - tam tikros taisyklës. Naudojant heuristikas perþiûrima tik tam tikra leistinø sprendiniø dalis. Ið jø iðrenkamas geriausias sprendinys. Pastarasis yra pateikiamas kaip optimaliausias sprendinys.

Tikslas, sprendþiant pamokø tvarkaraðèio uþdaviná, minimizuoti pamokø tvarkaraðèio ávertinimo funkcijà. Sprendþiant pamokø tvarkaraðèio optimizavimo uþdaviná, naudojome ðias heuristikas:

  1. Monte Carlo metodà: 1/N. Ið galimø sprendiniø aibës parenkamas atsitiktinis sprendinys;
  2. Kvadratinæ priklausomybæ: h(n)^2 / sum(h(j))^2;
  3. Grynà heuristikà: 1, jei h(n)=min(h(j)); 0 kitu atveju.

Turime dvi loterijas:

Algoritmas

Programa suranda tikimybes, pagal kurias turi bûti pasirenkamas metodas, kuris iðrenka vienà tvarkaraðèio variantà ið 10 galimø. Perstatymas atliekamas nuo pradinio tvarkaraðèio, kad bûtø sudarytos vienodos sàlygos pasirenkant sprendinius.

Uþdaviniui iðspræsti sukûrëme ðias duomenø struktûras:

Programa optimizuoja tvarkaraðtá pagal algoritmà:

1. Duomenys nuskaitomi ið failø 'tvarkar.txt' ir 'busy.txt'
2. for (i=0; i<10; i++)
3. Sunormuojamos funkcijai double fi(const double* probab, int n) perduodamos tikimybës - masyvas probab.
4. Sugeneruojamas atsitiktinis skaièius, pagal kurá pasirenkamas Monte Carlo, kvadratinës priklausomybës ar grynos heuristikos metodas.
5. Metodas gràþina vienà ið 10 galimø tvarkaraðèio sprendiniø. Ðis sprendinys - funkcijos double fi(const double* probab, int n) gràþinama reikðmë po vienos iteracijos.

Tvarkaraðtis perstatomas pagal algoritmà (funkcijoje permutate()):

1. Atsitiktinai pasirenkama tvarkaraðèio eilutë.
2. Jei eilutëje mokytojas neturi langø, gráþtama á 1. punktà; jei mokytojas turi langø vykdomas 3. punktas.
3. Atsitiktinai parenkamas tos eilutës mokytojo langas.
4. Atsitiktinai parenkama tos eilutës paskutinë bet kurios dienos mokytojo pamoka.
5. Punkte 4. parinkta pamoka keliama á punkte 3. rastà mokytojo langà.
6. Randama prieðtaringa tvarkaraðèio eilutë - situacija, kai mokinys turi dvi pamokas vienu metu. Jei prieðtaravimo nëra, perstatymas baigtas; jei egzistuoja prieðtaringa eilutë, vykdomas punktas 7.
7. Prieðtaringa pamoka keliama á punkte 4. surastà pamokà jau prieðtaringoje eilutëje.
8. Gráþtama á punktà 6.

Perstatant tvarkaraðtá pagal ðá algoritmà - gautas tvarkaraðtis yra neprieðtaringas, t.y., gali bûti paþeistos tik 4, 5 ir 6 tvarkaraðèio sudarymo taisyklës (þr. skyriø Uþduoties analizë).

Instrukcija vartotojui

Programos vykdomui reikalinga Unix aplinka ir xWindows. Programa vykdoma Unix komandinëje eilutëje surinkus 'test'. Tada atidaromas programos langas, kuris turi tokius meniu punktus: "Global", "Local", "Operations", "Quit", "Parameters", "Results", "Output", "Help". Per "Global" ir "Local" meniu punktus vartotojas pasirenka globalø ir lokalø funkcijos minimizavimo metodus. Meniu punkte "Parameters" vartotojas nurodo:

  1. Iteracijø skaièiø.
  2. Funcijai double fi(const double* probab, int n) perduodamo masyvo probab reikðmiø rëþius (kintamieji A(1), A(2), A(3) - pradiniai rëþiai, jie turi bûti lygus 0; kintamieji B(1), B(2), B(3) - galiniai rëþiai, jie turi bûti lygûs 1).
  3. Pradines funkcijai double fi(const double* probab, int n) perduodamas reikðmes (kintamieji X(1), X(2), X(3)).

Meniu punktas "Output" suteikia vartotojui galimybæ parþiûrëti skaièiavimo rezultatus programos vykdymo metu. Per meniu punktà "Operations/Run" vartotojas vykdo uþdavinio optimizavimà. Per meniu punktà "Results" vartotojas gali pasiþiûrëti galutinius optimizavimo rezultatus. Programa baigiama, pasirinkus meniu punktà "Quit".

Rezultatai

Optimizuojant pasirinkome Bayes1 globaliná ir LBayes lokaliná metodus. Pradines tikimybes pasirinkti vienà ið trijø heuristikos taisykliø, nustatëme vienodas: 0.5, 0.5, 0.5. Vienu atveju buvo pasirinkta 50 iteracijø, kitu - 100. Pirmu atveju gauti tokie rezultatai:

Kai iteracijø skaièius 100, gauti tokie rezultatai:

Iðvados

Ið gautø rezultatø akivaizdu, kad tvarkaraðèio optimizavimui labiausiai tinka grynos heuristikos taisyklë ir visiðkai netinka Monte Carlo taisyklë. Be to, uþdavinio sprendimo eigoje pastebëjome, kad mokyklos pamokø tvarkaraðèio optimizavimas yra sunkiai pritaikomas praktikoje, nes sunku sugalvoti tvarkaraðèio perstatymo algoritmà. Pamokø tvarkaraðtis turi daug apribojimø. Daugumos ið jø negalima paþeisti, kitaip tvarkaraðtis tampa nebepritaikomas praktikoje. Galimas sprendimas - ávedamos baudos uþ apribojimø paþeidimà, bet tai negarantuoja, kad sudarytas tvarkaraðtis bus pritaikomas. Mes sugaiðome daug laiko perstatymo algoritmui sugalvoti. Ðis algoritmas nepaþeidþia pagrindiniø tvarkaraðèio sudarymo taisykliø, taèiau nei viena mokykla nenaudotø pagal já perstatyto tvarkaraðèio.