Užití
Místnosti a modely jejich obsazení
Každá místnost může mít více modelů (tj. způsobů, jak může být obsazena). Místnost definuje, kolik je řad a sloupců a kde jsou židle. Např. v první řadě je sedadel méně, protože se počítá s místy pro vozíčkáře. Model místnosti určuje, kam budeme chtít studenty obsazovat - např. každá třetí řada ob dvě sedadla. Pro jiné použití téže místnosti, kdy je studentů větší počet, potřebujeme jiný model a obsazujeme do sudých řad jen ob jedno sedadlo. To způsobuje rozdíl mezi kapacitou místnosti (je dána počtem sedadel) a kapacitou modelu (je dána počtem volných sedadel).
Výpočet zasedacího pořádku
Pro každý běh algoritmu máme zadán model místnosti (zároveň víme i místnost, ke které model patří) a velikost skupiny studentů N, skupiny po sobě jdoucích studentů, které se snažíme rozsadit - chceme je usadit co nejdál od sebe.
Pro výpočet použijeme model založený na řešení Problému batohu. Takto získané řešení nemusí být optimální. Je totiž konstruováno na základě lokálních optim, které však nemusejí vést optimu globálnímu. V každém kroku algoritmu se snažíme obsadit takové obsaditelné sedadlo, které je od posledních N (= velikost skupiny studentů) obsazených sedadel, co nejdále. Modely vzdálenosti (metriky) lze použít různé, např. Manhattanskou, Euklidovskou. Pro řešení problému batohu je také podstatné, jak transformovat vícerozměrné kritérium vzdálenosti k již obsazeným sedadlům na jednorozměrnou cenu. Nejsnazší způsob je aditivní, tj. jako cenu použijeme součet vzdáleností k N naposledy obsazeným sedadlům. Můžete samozřejmě s touto transformací experimentovat a hledat vhodnější řešení.
Požadované průchody aplikací
Definování místnosti a modelu
Webové uživatelské rozhraní aplikace umožní uživateli definovat novou místnost a k ní příslušné modely, a to pomocí nahrání souborů v CSV formátu. Rozhraní musí uživatele informovat minimálně v následujících případech:
- Definování místnosti, příp. modelu, proběhlo úspěšně.
- Došlo k některé z následujících chyb:
- soubor je prázdný
- formát souboru je nevyhovující (budou rozlišeny minimálně následující problémy):
- model nevyhovuje parametry zvolené místnosti (např. místnost má méně řad než předpokládá model),
- model obsahuje neplatné hodnoty,
- model má nevyhovující počet sloupců v řádku,
- ostatní chyby formátu
- interní chyba při zpracování (např. nedostupná relační databáze).