====== Rozděl a panuj! ======
  * Data s referenčními hodnotami: {{:courses:a0m33eoa:semestralni_ulohy:rozdel_a_panuj:data_s_referencnimi_hodnotami.zip|}}
  * Data s umistenim uzlu: {{:courses:a0m33eoa:semestralni_ulohy:rozdel_a_panuj:divide_and_conquer_test_data_2.zip|}}
===== Popis problému =====
Jste správci rozlohou velké oblasti s množstvím měst s hustou sítí silnic. Každodenní správcovské povinnosti už vás ale nebaví a chtěli byste práci delegovat na několik svých zástupců. Je proto třeba rozdělit celé panství na několik stejně velkých regionů, každý z nich bude řídit jeden zástupce.

Cílem je najít rozdělení původní oblasti na maximálně autonomní regiony tj. s minimálním propojením mezi regiony.  

  * Vstup: Graf <latex>$G(V,E)$</latex>, kde //V// je množina měst <latex>${v_1,…,v_M}$</latex> a //E// je množina silnic spojujících města. Číslo //n// je počet požadovaných regionů.
  * Výstup: Rozdělení množiny //V// na vzájemně disjunktní podmnožiny <latex>${V_1,…,V_n}$</latex>, kde <latex>$\bigcup_{i=1}^{n}V_i=V$</latex> a <latex>$||V_i|-|V_j||\leq 1$</latex> pro všechny <latex>$i\neq j$</latex>

===== Možné reprezentace =====
  * Pole velikosti //M//, kde //i//-tá pozice obsahuje číslo regionu, do kterého //i//-té město patří.
  * ...

===== Jednotná ohodnocovací funkce =====
Počet cest mezi městy z jiného regionu

<latex>
\begin{equation*} 
f(s) = \sum_{l\in V_i, k\in V_j,i\neq j}e_{lk}
\end{equation*}
</latex>		

Tato funkce je minimalizována.

===== Multikriteriální rozšíření =====
U této úlohy dává dobrý smysl řešit úlohu s omezením jako multikriteriální:
  * místo hledání stejně velkých (omezení) minimálně propojených (kritérium) regionů bychom hledali
  * minimálně propojené (kritérium 1) regiony s co nejmenším rozdílem velikostí (kritérium 2).
Přeměna omezení na kritérium 2 by nám možná mohla umožnit najít hodně autonomní regiony, které jsou přibližně stejně velké.