Warning
This page is located in archive.

Rozděl a panuj!

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 $G(V,E)$, kde V je množina měst ${v_1,…,v_M}$ 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 ${V_1,…,V_n}$, kde $\bigcup_{i=1}^{n}V_i=V$ a $||V_i|-|V_j||\leq 1$ pro všechny $i\neq j$

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


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

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é nejsou přibližně stejně velké.

courses/a0m33eoa/semestralni_ulohy/rozdel_a_panuj/start.txt · Last modified: 2018/11/19 18:50 by xposik