Rozděl a panuj!

• Data s referenčními hodnotami: data_s_referencnimi_hodnotami.zip
• Data s umistenim uzlu: divide_and_conquer_test_data_2.zip

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 G(V,E), kde V je množina měst <latex>${v_1,…,v_M}$</latex> a E je množina silnic spojující města.
• 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>

• Pole velikosti M, kde i-tá pozice obsahuje číslo regionu, do kterého i-té město patří.
• …

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.