Optimizacijske metode

Hallov izrek. Naj bo $G = (X+Y, E)$ dvodelen graf. Potem obstaja popolno prirejanje iz $X$ v $Y$ (tj., prirejanje, ki pokrije $X$) natanko tedaj, ko velja $\forall A \subseteq X: |A| \le |N(A)|$, kjer je $N(A) = \{v \in Y \mid \exists u \in A: uv \in E\}$ soseščina (angl. neighbourhood) množice $A$.

Dokaz.

• ($\Longrightarrow$) Naj bo $M$ popolno prirejanje iz $X$ v $Y$. Obstaja injektivna preslikava $f : A \to N(A)$, $f(u) = v \Leftrightarrow uv \in M$.

  graph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]
  
  a -- i
  b -- j
  b -- k [style=invis]
  c -- k [style=invis]
  d -- l [style=invis]
  e -- m [style=invis]
  e -- n [style=invis]
  e -- o [style=invis]
  f -- m [style=invis]
  f -- n [style=invis]
  g -- o [style=invis]
  h -- k [style=invis]
  h -- p [style=invis]
  a -- k [color=red]
  b -- i [color=red]
  c -- j [color=red]
  c -- l
  d -- j
  d -- m [color=red]
  e -- k
  e -- l [color=red]
  e -- p
  f -- o [color=red]
  g -- m
  g -- p [color=red]
  h -- n [color=red]
  h -- o
  
  a [xlabel=<<i>A</i>>]
  d [xlabel=" "]
  e [xlabel=<<i>A</i>>]
  f [xlabel=<<i>A</i>>]
  i [xlabel=<                            <i>N</i>(<i>A</i>)>]
  k [xlabel=<                            <i>N</i>(<i>A</i>)>]
  l [xlabel=<                            <i>N</i>(<i>A</i>)>]
  o [xlabel=<                            <i>N</i>(<i>A</i>)>]
  p [xlabel=<              <i>N</i>(<i>A</i>)>]
  }
  

• ($\Longleftarrow$) Uporabimo madžarsko metodo, da dobimo največje prirejanje $M$ in najmanjše pokritje $C$.

  graph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  
  S [label=<<i>S</i>>]
  T [label=<<i>T</i>>]
  XS [label=<<i>X \ S</i>>]
  YT [label=<<i>Y \ T</i>>]
  
  S -- T [color=red]
  S -- T
  XS -- T
  XS -- YT
  XS -- YT [color=red]
  S -- YT [style=invis]
  }
  

  Velja $N(S) \subseteq T$, torej $|S| \le |N(S)| \le |T|$. Nadalje velja $$ |M| = |C| = |T| + |X \setminus S| \ge |S| + |X \setminus S| = |X|. $$ Ker velja $|M| \le |X|$, sledi $|M| = |X|$, torej smo našli popolno prirejanje iz $X$ v $Y$.

Opomba. Zgornji izrek je oblike $\exists \ldots \Leftrightarrow \forall \ldots$.

• Če želimo dokazati, da obstaja popolno prirejanje iz $X$ v $Y$, ga poiščemo.
• Če želimo dokazati, da ne obstaja popolno prirejanje iz $X$ v $Y$, poiščemo $A \subseteq X$, da velja $|A| > |N(A)|$.

Taka karakterizacija recimo ni znana za hamiltonskost grafa (obstoj Hamiltonovega cikla).

Minimalna in maksimalna popolna prirejanja

Imamo poln dvodelen graf $K_{n, n} = (X + Y, E)$, kjer je $X = \{u_1, u_2, \dots, u_n\}$, $Y = \{v_1, v_2, \dots, v_n\}$ in $E = \{u_i v_j \mid 1 \le i, j \le n\}$, ter uteži $c_{ij}$ (cene) na povezavah $u_i v_j$ ($1 \le i, j \le n$), ki jih zapišemo v matriko $A = (c_{ij})_{i,j=1}^n$.

Tak graf ima $n!$ popolnih prirejanj. Iščemo popolno prirejanje z minimalno (maksimalno) ceno, kjer je cena prirejanja $M$ enaka $\sum_{u_i v_j \in M} c_{ij}$.

Primeri.

• Problem štafete;
• druge razporeditve opravil ($n$ ljudi, $n$ opravil, vsak dobi natanko eno opravilo).

Opazimo: če v matriki $A$ odštejemo konstanto $\epsilon$ od vseh elementov v eni vrstici ali enem stolpcu, se optimalna rešitev ne spremeni, saj ima vsako popolno prirejanje natanko eno povezavo s krajiščem v vozlišču, ki ustreza izbrani vrstici ali stolpcu. Cena vsakega popolnega prirejanja se tedaj zmanjša za $\epsilon$.

Primer. Zmanjšajmo za najmanjšo vrednost v vsaki vrstici, nato pa še v vsakem stolpcu: $$ \begin{bmatrix} 3 & 1 \\ 4 & 2 \end{bmatrix} \to \begin{bmatrix} 2 & 0 \\ 2 & 0 \end{bmatrix} \to \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} $$

Madžarska metoda z utežmi za iskanje minimalnega popolnega prirejanja:

1. Od vsake vrstice odštejemo njen minimum. Od vsakega stolpca odštejemo njegov minimum. Dobimo nenegativno matriko z vsaj eno ničlo v vsaki vrstici in vsakem stolpcu.
2. Poiščemo $n$ ničel, v vsaki vrstici in vsakem stolpcu eno. Če jih najdemo, nam dajo minimalno popolno prirejanje.
3. Sicer lahko vse ničle v matriki pokrijemo z manj kot $n$ vrsticami in stolpci. Naj bo $\epsilon$ minimum nepokritih števil. Od nepokritih števil odštejemo $\epsilon$, dvakrat pokritim številom pa prištejemo $\epsilon$. Vrnemo se na 2. korak.

Primer - štafeta.

Minimum v vsaki vrstici je $0$ - odštejmo še minimume stolpcev:

Vse ničle smo pokriti s tremi vrsticami in dvema stolpcema (skupaj manj kot $n = 6$). Najmanjša nepokrita vrednost je $\epsilon = 2$ - zmanjšamo nepokrita in povečamo dvakrat pokrita števila za $\epsilon$:

Dobimo optimalno rešitev:

Cena optimalne rešitve: 65 + 69 + 65 + 55 + 0 + 0 = 254.

Kaj pravzaprav naredimo v 2. in 3. koraku? Naj bo $H = (X+Y, E')$ dvodelen graf, kjer je $E' = \{u_i v_j \mid c_{ij} = 0\}$ (ničelni graf).

graph H {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [fillcolor=red]

  1 [style=filled]
  2 [xlabel=<<i>S</i>>]
  3 [style=filled]
  4 [xlabel=<<i>S</i>>]
  5 [style=filled]
  6 [xlabel=<<i>S</i>>]
  p1 [label="počiva", style=filled, xlabel=<                                   <i>T</i>>]
  p2 [label="počiva", style=filled, xlabel=<                                   <i>T</i>>]

  1 -- prsno
  5 -- hrbtno [color=red]
  1 -- delfin [color=red]
  3 -- prosto [color=red]
  1 -- p1
  2 -- p1
  3 -- p1
  4 -- p1 [color=red]
  5 -- p1
  6 -- p1
  1 -- p2
  2 -- p2
  3 -- p2
  4 -- p2
  5 -- p2
  6 -- p2 [color=red]
}

Na $H$ poiščemo največje prirejanje $M$ in najmanjše pokritje $C = (X \setminus S) + T$ z madžarsko metodo.

• Če je $M$ popolno prirejanje ($|M| = n$), nam to da $n$ ničel, eno v vsaki vrstici in stolpcu.
• Če je $|M| = |C| < n$, nam vozlišča iz $C$ dajo manj kot $n$ vrstic in stolpcev, ki pokrijejo vse ničle. Vrsticam v $C$ (torej v $X \setminus S$) prištejemo $\epsilon$, stolpcem izven $C$ (torej v $X \setminus T$) odštejemo $\epsilon$. Res torej od nepokritih števil odštejemo $\epsilon$, dvakrat pokritim pa prištejemo $\epsilon$.

Zakaj se madžarska metoda z utežmi vedno ustavi?

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [arrowhead=none]

  S [label=<<i>S</i>>]
  T [label=<<i>T</i>>]
  XS [label=<<i>X \ S</i>>]
  YT [label=<<i>Y \ T</i>>]
  x [style=invis]
  y [style=invis]
  S2 [label=<<i>S</i>>]
  T2 [label=<<i>T</i>>]
  XS2 [label=<<i>X \ S</i>>]
  YT2 [label=<<i>Y \ T</i>>]

  S -> T [color=red]
  S -> T
  XS -> T
  XS -> YT
  XS -> YT [color=red]
  S -> YT [style=invis]

  T -> x [style=invis]
  YT -> x [style=invis]
  x -> y [arrowhead=normal]
  y -> S2 [style=invis]
  y -> XS2 [style=invis]

  S2 -> T2 [color=red]
  S2 -> T2
  XS2 -> T2 [style=invis]
  XS2 -> YT2
  XS2 -> YT2 [color=red]
  S2 -> YT2
}

V tretjem koraku se znebimo povezav med $X \setminus S$ in $T$ (dvakrat pokrita števila) in pridelamo vsaj eno povezavo med $S$ in $Y \setminus T$ (med nepokritimi števili je bil $\epsilon$, ki smo ga zmanjšali na $0$) - naj bo to povezava $uv$ ($u \in S$, $v \in Y \setminus T$). Imamo dve možnosti:

• $v$ je prosto vozlišče: našli smo povečujočo pot, prirejanje se poveča;
• $v$ je vezano vozlišče: poveča se množica $S$.

Množica $S$ se lahko poveča največ $n$-krat, preden se poveča prirejanje. Prirejanje se poveča največ $n$-krat. Madžarska metoda z utežmi ima torej največ $n^2$ korakov. Ker pri tem opravi približno $n^2$ operacij za izvedbo madžarske metode, za madžarsko metodo z utežmi potrebujemo $O(n^4)$ operacij.

Opomba. Če iščemo maksimalno popolno prirejanje, poiščemo minimalno popolno prirejanje za $-A$.

Opomba. Iščemo $\min \sum_{i=1}^n A_{i \pi(i)}$ po vseh permutacijah $\pi \in S(n)$ ($n!$ permutacij). Če se omejimo samo na ciklične permutacije (tj., oblike $\pi = (i_1 \ i_2 \ \dots \ i_n)$ - $(n-1)!$ permutacij), je to problem potujočega trgovca - zanj ne poznamo učinkovitega algoritma.