Diskuze: Algoritmus na sestaveni rozvrhu hodin

Ostatní jazyky Ostatní programovací jazyky Algoritmus na sestaveni rozvrhu hodin

Avatar
mnauik
Člen
Avatar
mnauik:

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
Redaktor
Avatar
Odpovídá na mnauik
coells:

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  +1 30.5.2014 20:43
Avatar
Gramli
Redaktor
Avatar
Odpovídá na mnauik
Gramli:

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  +1 30.5.2014 21:32
Kdo to říká ten to je...
Avatar
coells
Redaktor
Avatar
Odpovídá na Gramli
coells:

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
Redaktor
Avatar
Odpovídá na coells
Gramli:

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.