Dotaz: rozházení do skupin (zápis do seminářů)

[David Fridrich]

Dobrý den,

potřebuji napsat program, který mi rozhází semináře do skupin (kvůli rozvrhu), tak, aby si co nejvíc lidí mohlo zapsat všechno, jak potřebují, tzn, aby v jedné skupině nebyly dva semináře, které má někdo zapsané zároveň. Data mám v jako seznam seznamů (v pythonu zapsáno [[1,4,5,6],[9,8,5,6]], kde vnitřní seznamy představují data zapsaná jednotlivými uživateli). Neporadí někdo nějaký algoritmus, příp. hotové řešení či nápad, kde to hledat?

Díky předem...

Odpovědi

[chrono]

Možno by sa dal použiť program FET (netuším, ako zložité bude nastaviť práve také požiadavky, ale malo by sa to tam dať urobiť).

[Vladimír Čunát]

Ten problém je IMO ekvivalentní barvení grafu. Pokud vezmeme semináře jako vrcholy pak podle přihlášených studentů je každá dvojice seminářů buď kompatibilní nebo ne. Každá barva pak odpovídá jednomu termínu. (Opačně, pokud dostaneme libovolný graf, můžeme vzít za každou hranu studenta který si ty dva semináře zapíše.)

Jak je vidět v odkazovaném článku, dokonce i aproximace optimálního počtu termínů je těžká (pokud přihlašování na semináře není nijak omezené). Předpokládám, že to je nějaký zápočťák a bude stačit použití hladového algoritmu: bereš semináře v nějakém pořadí a zkoušíš zda je možné ho přidat k některému už obsazenému termínu a pokud ne tak jím obsadíš nový termín. V tom wiki článku jsou taky nějaké heuristiky pro zlepšení výsledku v některých případech (třeba brát semináře od nejobsazenějších po nejméně obsazené).

[Radek Miček]

Lze to řešit například následujícím predikátem v Prologu:

:- use_module(library(clpfd)).

rozvrhni(Seminare, Zapsano, PocetSkupin) :-
  length(Seminare, PocetSeminaru),

  Seminare ins 1..PocetSeminaru,
  PocetSkupin in 0..PocetSeminaru,

  indomain(PocetSkupin), % pocet skupin postupne zvysujeme
  maplist(#>=(PocetSkupin), Seminare), % pocet skupin nebude prekrocen
  maplist(all_distinct, Zapsano), % nikdo nebude mit dva seminare
                                  % ve stejne skupine

  label(Seminare).

Ve vašem konkrétním příkladě se predikát volá takto: rozvrhni([X1, X4, X5, X6, X8, X9], [[X1,X4,X5,X6],[X9,X8,X5,X6]], PocetSkupin)., kde první seznam obsahuje všechny semináře a druhý seznam jsou semináře jednotlivých uživatelů. První řešení vypadá takto:

X1 = 1,
X4 = 2,
X5 = 3,
X6 = 4,
X8 = 1,
X9 = 2,
PocetSkupin = 4

Seminář X1 dáme do skupiny 1, X4 do skupiny 2, … a celkový počet skupin není vyšší než 4.