FINÁLNÍ VÝPRODEJ KREDITŮ na ITnetwork je tady. Využij poslední šanci a získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjisti více:
NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:

Diskuze: Toky v sítích - přiřazení žáků do místnosti

V předchozím kvízu, Test znalostí C# .NET online, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
Petr Šťastný
Tvůrce
Avatar
Petr Šťastný:25.4.2018 16:27

Zdravím, tohle je můj druhý dotaz na problém, který řeším. Jde o toto:

  • Mám místnost, která má otevřeno několik dní v týdnu, pokaždé v jinou dobu
  • Mám několik žáků, kteří také mají čas několik dní v týdnu, pokaždé v jinou dobu
  • Každého žák musí být v místnosti právě jednou za zadaný týden, a to na dobu 50 minut
  • Po prvních dvou žácích, kteří budou daný den v místnosti, je nutné před třetím žákem udělat 20 minut pauzu
  • Je potřeba žáky rozřadit tak, aby se pokud možno všichni dostali do místnosti

Nechci to dělat bruteforcem, přijde mi to jako špatné řešení. Nicméně mě napadlo na to použít toky v sítích, o kterých jsem se před pár dny dozvěděl. Použil bych bipartitní graf. Vypadalo by to nějak takhle:

IN - input
OUT - output
G1, G2, ... - skupina, která sdružuje hodiny, které se mezi sebou vylučují
H00, H05, H920 - začátek hodiny od minuty 0, 5, 920, ...
S1, S2, ... - student 1, 2, ...

Všechny hrany kromě hran, co sousedí s IN a OUT mají kapacitu 1. Hrany, co sousedí s IN nebo OUT mají neomezenou kapacitu. Všechny skupiny (G1, G2, ...) mají navíc uměle omezenou kapacitu na 1. Přikládám náhled.

Skupiny zajišťují, že nemůžou být vybrány dva časy, které by se překrývaly (třeba 800 a 820). Každý student si vybere právě jeden čas. Takhle by to mělo fungovat, jak popisuji nahoře, ale byl bych velmi rád, kdyby mi to mohl někdo zkontrolovat.

Problém bude s tím, že po druhém žákovi, který navštíví místnost, musí být 20 minut pauze. Jak to mám vyřešit? Jde to udělat pomocí toků v sítích? Mám nějak upravit algoritmus pro nalezení největšího toku, aby nějak prioritizoval první časy a jakmile by byly první dva určené, některé bych vyškrtal? Jestli ano, jak? Nebo mám pomocí tohoto modelu jenom najít řešení a potom bruteforcovat přestávku? Nebo mám udělat jedno řešení, zapamatovat si dva žáky, co jdou nejdřív a pustit to znova s tím, že ti dva žáci tam už nebudou, stejně jako časy, které jsou obsazené žáky + přestávkou?

Napsal jsem to trochu zmatečně, tak napište, kdybyste potřebovali něco vysvětlit - už to musím dodělat a potřebuji na to přijít.

Díky

 
Odpovědět
25.4.2018 16:27
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petr Šťastný
DarkCoder:25.4.2018 18:35

Toto jsme už společně řešili před několika měsíci. Popsal jsem Ti postup jak to udělat. Zkusil si to tak udělat? Musíš začít od těch žáků, co mají nejméně volna až po ty co mohou kdykoli. Rovněž musíš začít od těch termínů, na které se hlásí co nejméně žáků. Pokud byť jen jeden termín nebo žáka vynecháš, už to nemusíš sestavit.

Nahoru Odpovědět
25.4.2018 18:35
"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder
Avatar
Petr Šťastný
Tvůrce
Avatar
Odpovídá na DarkCoder
Petr Šťastný:25.4.2018 22:30

To jsem dělal, ale pokaždé jsem našel způsob, jak to udělat, aby moje stávající řešení nefungovalo. Pak je tady problém, že ty časy mohou být kdykoliv - tedy třeba 10:04, nebo 10:17, je to jedno, takže nemůžu úplně mluvit o termínech. Taky když beru od těch, co mají nejméně času, tak snadno mohou třeba vyřadit místa pro více lidí. Nebo kdybych je umístil někam jinam, tak by se všechno vyřešilo a umístěni by byli všichni. Když to opravím, zase to jde rozbít jinde - je tam strašně práce a pořád to nefunguje jak by mělo. To by šel lépe i ten bruteforce, ale to je takové hnusné a pomalé řešení.

 
Nahoru Odpovědět
25.4.2018 22:30
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Petr Šťastný
DarkCoder:25.4.2018 22:52

Úloha není nejsnazší, ale je řešitelná. To že časy mohou být proměnlivé, je jedno. Po vložení žáka nebo vyplnění termínu musíš aktualizovat všechno. Když nezačneš těmi, kteří mají nejméně času a jejich možné termíny zaplníš těmi, kteří toho času mají více, tak si herní terminologií "prohrál". Úloha může mít ale nemusí mít řešení. Bruteforce by byl opravdu hodně pomalý, musíš optimalizovat. Jak jsem psal minule, zjednoduš si úlohu na pár studentů a stanov časy, se kterými se bude lépe pracovat. A pak postupně zvyšuj náročnost. To hlavní je znalost principu proč zrovna daného žáka popřípadě jakou s jakou místností musím v tu chvíli pracovat.

Nahoru Odpovědět
25.4.2018 22:52
"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder
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 4 zpráv z 4.