NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
mnauik
Člen
Avatar
mnauik:30.5.2014 20:31

Netusite nekdo, jak sestavit nejlepsi rozvrh hodin, ktery vyhovuje podminkam?

Mejme napr. predmet 1 a predmet 2, u kazdeho predmetu si student vybira, kdy bude mit prednasky a kdy cviceni. Jak vybrat nejlepsi variantu?

Napadlo me toto, ale nevim prave, jestli je to spravne reseni:

  1. Oznacim si "okynka" rozvrhu a ohodnotim je (napr. 1 - nejlepsi, 10 - nejhorsi)
  2. Priradim do rozvrhu prednasky - ty, ktere si vybirat nemohu
  3. Seradim si "okynka" rozvrhu od nejmensi hodnoty do nejvetsi
  4. Okynkum prirazuji postupne predmety

Nebo-li nalezt takovy soucet okynek, ktere obsadim, aby byl co nejmensi.

Existuje lepsi zpusob?

Odpovědět
30.5.2014 20:31
minusuj mě, ale zdůvodni to ;)
Avatar
coells
Tvůrce
Avatar
Odpovídá na mnauik
coells:30.5.2014 20:43

To je typická optimalizační úloha v oblasti, které se říká programování s omezujícími podmínkami.

Potřebuješ:

  1. jasně definovat vstupní a výstupní podmínky
  2. vytvořit ohodnocovací funkci F, která určuje kvalitu rozvrhu

Poté procházíš různé možnosti, jak lze sestavit rozvrh a hledáš min(F) na oboru všech rozvrhů.

Klíčové se správné vytvoření funkce F, protože ta určuje, který rozvrh je lepší, a který je horší.
Samotný algoritmus je obyčejný backtracking, který se dá urychlit heuristikou, kdy většinu rozvrhů ignoruješ, protože "odhadneš", že nedají správný výsledek.

 
Nahoru Odpovědět
30.5.2014 20:43
Avatar
Gramli
Tvůrce
Avatar
Odpovídá na mnauik
Gramli:30.5.2014 21:32

Re: coells: Problém je vymyslet ohodnocovací funkci tak, aby byl algoritmus ideální.
Jesti se chceš dozvědět více o takových algortimech, podívej se na informované metody prohledávání:
algoritmus A* (A star), AND/OR grafy-> MinMax -> AlfaBeta.

Nahoru Odpovědět
30.5.2014 21:32
Kdo to říká ten to je...
Avatar
coells
Tvůrce
Avatar
Odpovídá na Gramli
coells:30.5.2014 22:53

Re: coells: Problém je vymyslet ohodnocovací funkci tak, aby byl algoritmus ideální.

Nerozumím, cos tím myslel, můžeš to vysvětlit?
Algoritmus je, jaký je, nějakým způsobem hledá optimální nebo skoro-optimální nebo alespoň dostačující řešení.
Označit něco za "ideální" v sobě zahrnuje řadu faktorů a je to příliš nejasné.

 
Nahoru Odpovědět
30.5.2014 22:53
Avatar
Gramli
Tvůrce
Avatar
Odpovídá na coells
Gramli:31.5.2014 10:10

Myslel jsem to tak, že je problém vymyslet ohodnocovací funkci, tak aby byl algortimus efektivní a fungoval podle zadání. Slovo "ideální" jsem neměl použít.

Nahoru Odpovědět
31.5.2014 10:10
Kdo to říká ten to je...
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.