Rozvrhování

Lokální prohledávání: Tabu prohledávání, simulované žíhání, genetické algoritmy.


Přednáška 03
Dotazy k přednášce

  1. Jaký je rozdíl mezi konstruktivními metodami a lokálním prohledáváním?
  2. Popište konstru algoritmu lokálního prohledávání.
  3. Jak budeme reprezentovat rozvrh pro problém jednoho stroje a jaké můžeme použít okolí?
  4. Jak vygenerujete iniciální řešení? Jak mohou vypadat podmínky ukončení?
  5. Jaké znáte metody pro akceptování horšího rozvrhu?
  6. Popište princip tabu prohledávání. Co to je aspirační kritérium?
  7. Popište pseudokód algoritmu tabu prohledávání.
  8. Popište jednotlivé kroky řešení příkladu na průsvitce 10.
  9. Jaké myšlenky využívá algoritmus simulovaného žíhání?
  10. Vysvětlete, jak funguje Metropolisovo kritérium.
  11. Vysvětlete pseudokód algoritmu simulovaného žíhání.
  12. Popište jednotlivé kroky řešení příkladu na průsvitce 17.
  13. Popište princip genetických algoritmů.
  14. Jaký je princip křížení? Proč nelze pro rozvrhování na jednom stroji použít operátor jednobodového (jednoduchého) křížení?
  15. Popište křížení  dané pořadím na příkladu z průsvitky 22.
  16. Jaké znáte typy mutace?
  17. Jak funguje princip ruletového kola?
  18. Jak funguje turnajový výběr a jak funguje elitářský model?
  19. Popište pseudokód genetického algoritmu
  20. Popište jednotlivé kroky řešení příkladu na průsvitce 27.

Předchozí
Následující