\documentclass[fullscreen=true,unicode,bookmarks=false]{beamer}
\usetheme{Boadilla}
%\includeonlyframes{SumSubsetShow}
%\includeonlyframes{OtherPProblems}

\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{tikz}

\theoremstyle{definition}
\newtheorem{mydefinition}{Определение}
\newtheorem{myexample}{Пример}
\newtheorem{myproblem}{Задача}
\newtheorem{mysign}{Обозначение}
\newtheorem{algorithm}{Алгоритм}

\newtheorem{given}{Дано}
\newtheorem{result}{Результат}
\theoremstyle{remark}
\newtheorem{remark}{Замечание}

\definecolor{mygreen}{rgb}{0.7,1,0.7}
\definecolor{darkgreen}{rgb}{0,0.5,0}
\definecolor{greenyellow}{rgb}{0.8,1,0.6}

\newcommand<>{\txtcell}{\only#1{\textcolor{darkgreen}}}

\newcommand{\bZ}{{\mathbb Z}}
\newcommand{\bZpositiv}{{\mathbb Z_+}}
\newcommand{\bZnonnegativ}{{\mathbb Z_{\ge0}}}
\renewcommand{\emptyset}{\ensuremath{\varnothing}}
\newcommand{\qu}{\text{\textquestiondown}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\DeclareMathOperator{\logOR}{or}
\DeclareMathOperator{\logAND}{and}
\DeclareMathOperator{\Time}{Time}
\DeclareMathOperator{\Length}{Length}
\DeclareMathOperator{\Max}{Max}
\DeclareMathOperator{\NPclass}{NP}
\DeclareMathOperator{\Pclass}{P}
\newcommand{\mysim}[1]{\stackrel{#1}{\sim}}
\newcommand{\notmysim}[1]{\stackrel{#1}{\nsim}}
\newcommand{\Partitions}{{\mathcal{P}}}
\newcommand{\Colorings}{{\mathcal{C}}}
\newcommand{\eqdef}{\stackrel{\textrm{def}}{=}}

\tikzstyle{thickarrow}=[densely dashed,very thick]


\title[Жадное скрещивание разбиений]{Жадный алгоритм\\
устойчивого скрещивания разбиений}
\author[Синяк, Максименко]{Т. С. Синяк, Е. А. Максименко}
\institute[ЮФУ]{Южный федеральный университет}
\keywords{разбиения множеств, скрещивание разбиений, генетические алгоритмы,
жадный алгоритм, расстояние между разбиеиями}

\AtBeginSubsection[] {
\begin{frame}{План доклада}
\tableofcontents[currentsection,currentsubsection]
\end{frame}
}

\begin{document}

\begin{frame}[label=titlepage]
\titlepage
\end{frame}

\begin{frame}{План доклада}
\tableofcontents
\end{frame}

\section{Введение}

\begin{frame}{Генетические алгоритмы}

\begin{block}{}
Генетические алгоритмы~--- один из современных методов 
решения NP-трудных задач оптимизации.
\end{block}

\begin{block}{Схема алгоритма}
Создать начальную популяцию\\
Для $t=1\ldots T$ ($T$~--- число поколений):\\
\qquad Для $i=1\ldots NP/2$ ($NP$~--- число особей):\\
\qquad\qquad Выбрать две особи\\
\qquad\qquad Скрестить выбранные особи\\
\qquad\qquad Поместить потомков во множество потомков\\
\qquad Для $i=1\ldots NP$:\\
\qquad\qquad Мутировать $i$-ую особь\\
\qquad\qquad Поместить мутанта во множество мутантов\\
\qquad Добавить всех потомков и мутантов в популяцию\\
\qquad Провести отбор
\end{block}
\end{frame}


\begin{frame}{Задачи, связанные с перебором разбиений}
\framesubtitle{Задача о минимальной правильной раскраске графа}

\begin{myproblem}
\begin{description}
\item[Дано:] неориентированный граф $G=(V,E)$.
\item[Найти:] минимальную правильную раскраску графа $G$, 
т.~е. функцию $f\colon V\to\{1,2,\ldots,k\}$, такую что\\
$f(u)\neq f(v)$ для любых смежных вершин $u,v\in V$\\
и $k$ минимально.
\end{description}
\end{myproblem}

\begin{remark}
Правильную $k$-раскраску графа $G$ можно рассматривать как разбиение $V$ 
на не более, чем $k$ непустых непересекающихся подмножеств.
\end{remark}

\end{frame}

\begin{frame}{Задачи, связанные с перебором разбиений}
\framesubtitle{Задача о $3$-разбиении взвешенного множества}

\begin{myproblem}
\begin{description}
\item[Дано:] множество $X$ из $3m$ элементов,\\
граница $B\in\bZpositiv$,\\
«размеры» $s(x)\in\bZpositiv$, где $x\in X$, 
причём $B/4<s(x)<B/2$ и $\displaystyle\sum_{x\in X} s(x)=mB$.
\item[Найти:] $m$ непересекающихся подмножеств $Y_1,\ldots,\ Y_m$, 
таких что $\displaystyle\bigcup_{i=1}^{m} Y_i=X$ и 
$\displaystyle\sum_{x\in Y_i} s(x)=B$ для $1\le i\le m$.
\end{description}
\end{myproblem}
\end{frame}


\begin{frame}{Тривиальный алгоритм скрещивания разбиений}

\only<1>{Разбиения хранятся в виде раскрасок:}
\only<2->{Обмен генами осуществляется с заданной вероятностью:}
\par\medskip
\visible<1->{
\begin{tabular}{@{}r@{}c@{}l@{}}
\texttt{\{\{1\},\{2,5\},\{3,4,6\}\}} $\leftrightharpoons$
\texttt{1\alert<2->{2}\alert<2->{3}32\alert<2->{3}}& &
\visible<4->{%
\texttt{112322} $\rightleftharpoons$
\texttt{\{\{1,2\},\{3,5,6\},\{4\}\}}
}
\\%
\only<2>{\texttt{обмен?}}\hfill%
\only<2>{\texttt{FTTFFT}}%
\only<3->{\phantom{0}$\updownarrow$$\updownarrow$\phantom{0}\phantom{0}$\updownarrow$}
& \visible<3->{\,$\mapsto$} &
\\
\texttt{\{\{1,2\},\{3,4,5,6\}\}} $\rightleftharpoons$
\texttt{1\alert<2->{1}\alert<2->{2}22\alert<2->{2}}& &
\visible<4->{%
\texttt{123223} $\rightleftharpoons$
\texttt{\{\{1\},\{2,4,5\},\{3,6\}\}}}
\end{tabular}
}
\begin{block}{Недостаток}<visible@5->
Плохо согласуется со структурой разбиений:

\begin{tabular}{@{}rcl@{}}
\texttt{\{1,2,3,4,5,6\}} $\leftrightharpoons$
\texttt{1\alert<5->{1}\alert<5->{1}11\alert<5->{1}}& &
\texttt{122112} $\rightleftharpoons$
\texttt{\{\{1,4,5\},\{2,3,6\}\}}
\\%
\phantom{0}$\updownarrow$$\updownarrow$\phantom{0}\phantom{0}$\updownarrow$
&$\,\mapsto$&
\\
\texttt{\{\{1\},\{2,3,4,5,6\}\}} $\rightleftharpoons$
\texttt{1\alert<5->{2}\alert<5->{2}22\alert<5->{2}}& &
\texttt{111221} $\rightleftharpoons$
\texttt{\{\{1,2,3,6\},\{4,5\}\}}
\end{tabular}
\end{block}

\end{frame}

\begin{frame}{Цели работы}

\begin{block}{}
\vspace{0.5cm}
\begin{itemize}
\item Разработать алгоритм скрещивания,\\согласованный со структурой разбиений.
\end{itemize}

\begin{itemize}
\item Опробовать его в генетических алгоритмах.
\end{itemize}
\vspace{0.5cm}
\end{block}

\end{frame}

\section{Разбиения множеств и раскраски}

\subsection{Разбиения множеств}

\begin{frame}{Разбиения множеств}

\begin{block}{Определение разбиения множества}
Множество $P$ непустых подмножеств множества $\{1,\ldots,n\}$
называется \textcolor{red}{разбиением} множества $\{1,\ldots,n\}$, если
\[
\displaystyle\bigcup_{X\in P} X=\{1,\ldots,n\}
\quad\text{и}\quad
\forall X,Y\in P\colon Y\neq X\Rightarrow X\cap Y=\varnothing.
\]
\end{block}

\begin{block}{Обозначение}
$\Partitions_n$~--- множество всех разбиений множества $\{1,\ldots,n\}$.
\end{block}

\begin{block}{Отношение эквивалентности, соответствующее разбиению}
Пусть $P\in\Partitions_n$.
Определим отношение $\mysim P$ :
\[
\qquad\qquad\forall i,j\in\{1,\ldots,n\}\quad i\mysim P j\quad\iff\quad
\exists X\in P\quad i,j\in X.
\]
\end{block}

\end{frame}

\subsection{Хранение разбиений в виде кортежей (<<раскрасок>>)}

\begin{frame}{Раскраски}

\begin{block}{Определение раскраски}
\textcolor{red}{Раскраской} множества $\{1,\ldots,n\}$ будем называть
любое отображение $a\colon \{1,\ldots,n\}\to\{1,\ldots,n\}$.


Это отображение $a$ будем отождествлять
с кортежем $(a_1,\ldots,a_n)$, где $a_i=a(i)$.


Значение $a_i$ будем называть \textcolor{red}{цветом} элемента $i$ для $i\in\{1,\ldots,n\}$ 
(при раскраске $a$).
\end{block}

\begin{mysign}
$\Colorings_n$~--- множество всех раскрасок
множества $\{1,\ldots,n\}$.
\end{mysign}


\end{frame}


\begin{frame}{Раскраски и разбиения}
\framesubtitle{Определение и пример}

\begin{block}{Определение разбиения, соответствующего раскраске}
Пусть $a\in\Colorings_n$. Определим разбиение $P_a$,
соответствующее раскраске $a$:\\
\[
P_a=\{a^{-1}(k)\colon\quad k=1,\ldots,n,\quad a^{-1}(k)\neq\varnothing\}.
\]
Другими словами, в одну долю попадают элементы одного цвета:
\[
i\mysim {P_a} j\quad\iff\quad a_i=a_j\quad(i,j\in\{1,\ldots,n\}).
\]
\end{block}

\begin{myexample}
$a=(5,2,2,1,5),$\\
$a^{-1}(1)=\{4\},\
a^{-1}(2)=\{2,3\},\
a^{-1}(3)=a^{-1}(4)=\varnothing,\
a^{-1}(5)=\{1,5\},$\\
$P_a=\{\{1,5\},\{2,3\},\{4\}\}.$
\end{myexample}

\end{frame}

\begin{frame}{Раскраски и разбиения}
\framesubtitle{Эквивалентность раскрасок}

\begin{block}{}
Отображение $a\mapsto P_a$ сюръективно, но не инъективно.
Несколько раскрасок могут соответствовать одному разбиению:\\
$a=(2,5,2,5,3),\  b=(3,2,3,2,1),\  P_a=P_b=\{\{1,3\},\{2,4\},\{5\}\}.$
\end{block}

\begin{block}{Определение эквивалентных раскрасок}
Пусть $a,b\in\Colorings_n$. Раскраски $a$ и $b$ будем называть
\textcolor{red}{эквивалентными} ($a\sim b$), если $P_a=P_b$.
\end{block}

\begin{block}{Критерий эквивалентности раскрасок}
Раскраски эквивалентны, если одну можно получить из другой
путём перенумерации цветов:\\
\qquad\qquad\qquad$a\sim b\quad\iff\quad\exists\varphi\in S_n\colon\quad\varphi\circ a=b$.\\
Здесь $S_n$~--- множество всех перестановок порядка $n$,\\
т.~е. биективных отображений множества $\{1,\ldots,n\}$ в себя.
\end{block}

\end{frame}

\begin{frame}{Раскраски и разбиения}
\framesubtitle{Упорядоченные раскраски}

\begin{block}{Определение упорядоченной раскраски}
Раскраску $a$ из $\Colorings_n$ будем называть
\textcolor{red}{упорядоченной}, если
\[
\qquad\qquad a_1=1,\quad a_i\le 1+\max(a_1,\ldots,a_{i-1})\quad (2\le i\le n).
\]
\end{block}

\begin{myexample}
$a=(1,1,2,1,3,2,3)$~--- упорядоченная раскраска;\\
$b=(1,1,3,1,2,3,2)$~--- неупорядоченная раскраска 
(цвет 3 появился раньше, чем цвет 2).
\end{myexample}

\begin{block}{Свойства упорядоченных раскрасок}
Упорядоченная раскраска является 
лексикографически наименьшей среди всех 
эквивалентных ей раскрасок.
Соответствие между упорядоченными 
раскрасками и разбиениями биективно.
\end{block}

\end{frame}

\begin{frame}{Нормализация раскраски}
\framesubtitle{Понятие и алгоритм нормализации}

\begin{block}{}
Нормализация~--- преобразование произвольной раскраски в
эквивалентную ей упорядоченную раскраску.
\end{block}

\begin{block}{Вход}
$a=(a_1,\ldots,a_n)$~--- произвольная раскраска.
\end{block}

\begin{block}{Вспомогательная структура}
$t$~--- массив из $n$ элементов:\\
\qquad $t[j]$~--- цвет, в который перейдёт цвет $j$;\\
\qquad если для $j$ цвет ещё не найден, то $t[j]=0$.
\end{block}

\begin{block}{Выход}
$b=(t[a_1],\ldots,t[a_n])$~--- упорядоченная раскраска, эквивалентная $a$.
\end{block}

\end{frame}

\begin{frame}{Нормализация раскраски}
\framesubtitle{Демонстрация работы алгоритма нормализации}
\begin{columns}[T]
\begin{column}{4cm}
\begin{block}{Вход}
$a=(2,3,1,2,5,1)$.
\end{block}
\begin{block}{Выход}<visible@2->
\only<2-12>{$b=(t[a_1],\ldots,t[a_n]).$}
\only<13->{$b=(1,2,3,1,4,3).$}
\end{block}
\end{column}

\begin{column}{7cm}
\begin{block}{}
$a=(\alert<3>2,\alert<5>3,\alert<7>1,\alert<9>2,\alert<10>5,\alert<12>1),\qquad n=6$\\
\only<1>{\vphantom{$t=(0,\alert<3>0,0,0,0,0),\qquad c=0$}}
\only<2,3>{$t=(0,\alert<3>0,0,0,0,0),\qquad c=0$}
\only<4,5>{$t=(0,1,\alert<5>0,0,0,0),\qquad c=1$}
\only<6,7>{$t=(\alert<7>0,1,2,0,0,0),\qquad c=2$}
\only<8,9,10>{$t=(3,\alert<9>1,2,0,\alert<10>0,0),\qquad c=3$}
\only<11->{$t=(\alert<12>3,1,2,0,4,0),\qquad c=4$}
\end{block}
\begin{block}{Комментарии}
\only<1>{\vphantom{$t[0]$}}
\only<2>{$c$~--- число использованных цветов. \vphantom{$t[0]$}}
\only<3,4>{$t[2]=0\colon\quad c\gets c+1,\quad t[2]\gets c.$}
\only<5,6>{$t[3]=0\colon\quad c\gets c+1,\quad t[3]\gets c.$}
\only<7,8>{$t[1]=0\colon\quad c\gets c+1,\quad t[1]\gets c.$}
\only<9>{$t[2]=1\neq0\colon$ ничего не делаем.}
\only<10,11>{$t[5]=0\colon\quad c\gets c+1,\quad t[5]\gets c.$}
\only<12>{$t[1]=3\neq0\colon$ ничего не делаем.}
\only<13>{\vphantom{$t[0]$}}
\end{block}
\begin{block}{Сложность}<visible@13->
Сложность алгоритма $O(n)$.
\end{block}
\end{column}
\end{columns}
\end{frame}



\subsection{Расстояние между разбиениями}

\begin{frame}{Расстояние между разбиениями}
\begin{block}{Источники}
В работах L.~Denoeud и A.~Gu\`enoche определены
различные расстояния между разбиениями. 
Будем рассматривать расстояние R\`egnier.
\end{block}

\begin{block}{Определение расстояния}
\textcolor{red}{Расстояние} между разбиениями будем определять как
минимальное число элементарных операций, необходимых
для превращения одного разбиения в другое.
Здесь элементарная операция~--- перемещение одного элемента
из одной доли в другую (возможно, пустую).
\end{block}

\begin{myexample}
$P=\{\{1,2,5\},\{3,4\}\},\quad Q=\{\{1,4\},\{2,5\},\{3\}\},\quad d(P,Q)=2$\\
$P=\{\{1,2,5\},\{3,4\}\}\to\{\{2,5\},\{1,3,4\}\}\to
\{\{2,5\},\{1,4\},\{3\}\}=Q$
\end{myexample}
\end{frame}

\begin{frame}{Расстояние между разбиениями в терминах раскрасок}
\begin{block}{Расстояние Хэмминга}
Для $a,b\in\Colorings_n$
\[
d_{H}(a,b)
=|\{i\colon 1\le i\le n, a_i\neq b_i\}|
=n - \sum_{i=1}^n \delta(a_i,b_i),
\]
где $\delta(i,j)$~--- символ Кронекера.
\end{block}

\begin{block}{Расстояние между разбиениями}
Пусть $a,b\in\Colorings_n$. Тогда
\[
d(P_a,P_b)=\min_{\varphi\in S_n}d_{H}(\varphi\circ a,b).
\]
\end{block}

\end{frame}



\subsection{Простые алгоритмы мутации и скрещивания раскрасок}

\begin{frame}{Простые алгоритмы мутации и скрещивания раскрасок}
\framesubtitle{Алгоритм мутации раскрасок}

\begin{block}{Вход}
$a\in\Colorings_n,\quad k\in\bZpositiv,\quad$
генератор псевдослучайных чисел (ГПСЧ).
\end{block}

\begin{block}{Выход}
$b\in\Colorings_n$, такая что $d(P_a,P_b)\le k$.
\end{block}

\begin{algorithm}
\begin{enumerate}
\item $b\gets a$.
\item $k$ раз выбрать случайно $i\in\{1,\ldots,n\}$ и
записать в $b_i$ случайное число от $1$ до $n$.
\end{enumerate}
\end{algorithm}

\begin{myexample}<visible@2->
$a=(1,2,1,1,2,3)\quad k=3$\\
\begin{overlayarea}{\textwidth}{4ex}
\only<2>{\vphantom{(1)}}
\only<3>{$b=(1,2,1,1,2,3)\quad i=\phantom{2,4,2}\quad r=$}
\only<4>{$b=(1,\alert<4>2,1,1,2,3)\quad i=2\phantom{,4,2}\quad r=$}
\only<5>{$b=(1,\alert<5>2,1,1,2,3)\quad i=2\phantom{,4,2}\quad r=3$}
\only<6>{$b=(1,\alert<6>3,1,1,2,3)\quad i=2\phantom{,4,2}\quad r=3$}
\only<7>{$b=(1,3,1,\alert<7>1,2,3)\quad i=2,4\phantom{,2}\quad r=3,5$}
\only<8>{$b=(1,3,1,\alert<8>5,2,3)\quad i=2,4\phantom{,2}\quad r=3,5$}
\only<9>{$b=(1,\alert<9>3,1,5,2,3)\quad i=2,4,2\quad r=3,5,1$}
\only<10>{$b=(1,\alert<10>1,1,5,2,3)\quad i=2,4,2\quad r=3,5,1$}
\only<11>{$b=(1,1,1,5,2,3)\quad i=2,4,2\quad r=3,5,1$}
\end{overlayarea}
\end{myexample}
\end{frame}

\begin{frame}{Простые алгоритмы мутации и скрещивания раскрасок}
\framesubtitle{Алгоритм однородного скрещивания раскрасок}

\begin{columns}[T]

\begin{column}{8.5cm}
\begin{block}{Вход}
$a,b\in\Colorings_n$, вещественное число $p\in[0,1]$, ГПСЧ.
\end{block}
\end{column}

\begin{column}{3cm}
\begin{block}{Выход}
$s,t\in\Colorings_n$.
\end{block}
\end{column}

\end{columns}

\begin{algorithm}
\begin{enumerate}
\item $s\gets a$, $t\gets b$.
\item Для каждого $i = 1,\ldots,n$ cоздать
случайное вещественное число $\hat{p}\in [0,1]$ и
в случае $\hat{p} < p$ поменять местами гены $s[i]$ и $t[i]$.
\end{enumerate}
\end{algorithm}

\begin{myexample}<visible@2->
$a=(\alert<2->1,2,1,\alert<2->1,\alert<2->3,1)\qquad s=(2,2,1,5,2,1)$\\
$b=(\alert<2->2,1,3,\alert<2->5,\alert<2->2,3)\qquad t=(1,1,3,1,3,3)$
\end{myexample}

\begin{block}{Свойство}<visible@3->
$d_{H}(a,s)+d_{H}(s,b) = d_{H}(a,b),\qquad
d_{H}(a,t)+d_{H}(t,b) = d_{H}(a,b).$
\end{block}
\end{frame}


\section{Геометрическое и устойчивое скрещивания разбиений}


\subsection{Геометрическое и устойчивое скрещивания}

\begin{frame}{Геометрическое и устойчивое скрещивание}

\begin{block}{}
Пусть \ $(X,d)$~--- метрическое пространство,\\
\qquad\quad$(\Omega,\mu)$~--- вероятностное пространство.
\end{block}

\begin{block}{Определение геометрического скрещивания Moraglio \& Poli}
Скрещивание $f\colon X\times X\times\Omega\to X$
называется \textcolor{red}{геометрическим},
если для любых $a,b\in X$ и $\omega\in\Omega$
элемент $c=f(a,b,\omega)$ удовлетворяет соотношению
\[
  d(a,c)+d(c,b)=d(a,b).
\]
\end{block}

\begin{block}{Определение $\alpha$-устойчивого скрещивания}
Пусть $\alpha\ge 1$. Будем говорить, что скрещивание
$f\colon X\times X\times\Omega\to X$
является \textcolor{red}{$\alpha$-устойчивым},
если для любых $a,b\in X$ и $\omega\in\Omega$
элемент $c=f(a,b,\omega)$ удовлетворяет неравенству
\[
  d(a,c)+d(c,b)\le \alpha d(a,b).
\]
\end{block}
\end{frame}

\subsection{Сведение к задаче о назначении}

\begin{frame}{Свед\'ение к задаче о назначении}

\begin{block}{Схема свед\'ения}
\begin{center}
\tikzstyle{cell}=[shape=rectangle,text centered,draw]
\begin{tikzpicture}
    \node[cell] (t0) at (2.5,0) {$\substack{\displaystyle\text{Задача о геометрическом}\\\displaystyle\text{скрещивании разбиений}}$};
    \node[cell] (t1) at (-2.5,0) {$\substack{\displaystyle\text{Задача о расстоянии}\\\displaystyle\text{между разбиениями}}$};
    \node[cell] (t2) at (0,2) {$\substack{\displaystyle\text{Задача о наилучшем соответствии}\\\displaystyle\text{между раскрасками}}$};
    \node[cell] (t3) at (0,4) {$\substack{\displaystyle\text{Задача о назначении}\\}$};

    \draw[->] (t0) to (2.5,1.55);
    \draw[->] (t1) to (-2.5,1.55);
    \draw[->] (t2) to (t3);
\end{tikzpicture}
\end{center}
\vspace{0.5cm}
\end{block}
\end{frame}

\begin{frame}{Сведение к задаче о назначении}

\begin{block}{Задача о наилучшем соответствии между раскрасками}
\begin{description}
\item[Дано:] $a,b\in\Colorings_n$.
\item[Найти:] перестановку $\varphi\in S_n$,
такую что $d(P_a,P_b)=d_{H}(\varphi\circ a,b)$.
\end{description}
\end{block}

\begin{block}{Задача вычисления расстояния между разбиениями}<visible@2->
\begin{description}
\item[Дано:] $a,b\in\Colorings_n$.
\item[Найти:] $d(P_a,P_b)$.
\end{description}
\end{block}

\begin{block}{Задача о геометрическом скрещивании разбиениий}<visible@3->
\begin{description}
\item[Дано:] $a,b\in\Colorings_n$.
\item[Найти:] $c\in\Colorings_n$,
такую что $d(P_a,P_c)+d(P_c,P_b)=d(P_a,P_b)$.
\end{description}
\end{block}

\begin{remark}<visible@4->
Очевидно, что задача о расстоянии сводится к задаче о наилучшем
соответствии.
\end{remark}
\end{frame}


\begin{frame}{Сведение к задаче о назначении}

\begin{block}{}
Под задачей о назначении будем понимать задачу о
нахождении максимального паросочетания во
взвешенном двудольном графе.
\end{block}

\begin{block}{Задача о назначении}
\begin{description}
\item[Дано:] двудольный граф $G=(X,Y,E,w)$, где\\
$X,Y$~--- доли графа,\\
$E\subset X\times Y$~--- множество дуг,\\
$w\colon E\to\bZpositiv$~--- весовая функция.\\
\item[Найти:] паросочетание $M$ в $G$,
такое что величина $w(M)=\sum_{e\in M} w(e)$ максимальна.
\end{description}
\end{block}

\begin{block}{Определение паросочетания}
\textcolor{red}{Паросочетанием} называется такое множество $M\subset E$, 
что для любых различных дуг $(x_1,y_1)$ и $(x_2,y_2)$ 
из $M$ справедливо: $x_1\neq x_2, y_1\neq y_2$.
\end{block}

\end{frame}

\begin{frame}{Сведение к задаче о назначении}
\framesubtitle{Взвешенный двудольный граф для двух раскрасок}

\begin{block}{Задача построения взвешенного двудольного графа для двух раскрасок}
\begin{description}
\item[Дано:] $a,b\in\Colorings_n$.
\item[Построить:] взвешенный двудольный граф $G_{a,b}=(X,Y,E,w)$, где\\
$X=\{1,\ldots,n\},\quad Y=\{1,\ldots,n\}$,\\
$E = \{(a_i,b_i):1\le i\le n\}$,\\
$w(k,l)=|a^{-1}(k)\cap b^{-1}(l)|,\quad (k,l)\in E$.
\end{description}
\end{block}

\begin{myexample}
\begin{columns}[T]

\begin{column}{4cm}
$a=(\alert<2>1,\alert<3>1,\alert<4>2,\alert<3>1,\alert<5>3,\alert<4>2)$\\
$b=(\alert<2>3,\alert<3>1,\alert<4>4,\alert<3>1,\alert<5>2,\alert<4>4)$
\end{column}

\begin{column}{7cm}
\begin{tikzpicture}

\node[circle,text centered,draw=black](x1) at (0,0.75) {1};
\node[circle,text centered,draw=black](x2) at (1,0.75) {2};
\node[circle,text centered,draw=black](x3) at (2,0.75) {3};
\node[circle,text centered,draw=black](x4) at (3,0.75) {4};
\node[circle,text centered,draw=black](x5) at (4,0.75) {5};
\node[circle,text centered,draw=black](x6) at (5,0.75) {6};

\node[circle,text centered,draw=black](y1) at (0,-0.75) {1};
\node[circle,text centered,draw=black](y2) at (1,-0.75) {2};
\node[circle,text centered,draw=black](y3) at (2,-0.75) {3};
\node[circle,text centered,draw=black](y4) at (3,-0.75) {4};
\node[circle,text centered,draw=black](y5) at (4,-0.75) {5};
\node[circle,text centered,draw=black](y6) at (5,-0.75) {6};

\visible<2->{
\draw[->](x1) to node[left]{1} (y3);
}
\visible<3->{
\draw[->](x1) to node[left]{2} (y1);
}
\visible<4->{
\draw[->](x2) to node[right]{\ 2} (y4);
}
\visible<5->{
\draw[->](x3) to node[right]{1} (y2);
}
\end{tikzpicture}
\end{column}

\end{columns}
\end{myexample}
\end{frame}

\begin{frame}{Сведение к задаче о назначении}
\framesubtitle{Алгоритм создания двудольного взвешенного графа для двух раскрасок}

\begin{columns}[T]

\begin{column}{1.7cm}
\begin{block}{Вход}
$a,b\in\Colorings_n$.
\end{block}
\end{column}

\begin{column}{9.8cm}
\begin{block}{Выход}
$G_{a,b}$ в виде массива $T$ троек (вес~дуги,~начало,~конец).
\end{block}
\end{column}

\end{columns}

\begin{algorithm}
\begin{enumerate}
\item $Pairs \gets ((a_1,b_1),\ldots,(a_n,b_n))$.
\item Отсортировать элементы массива $Pairs$ лексикографически 
в порядке возрастания (одинаковые пары окажутся рядом).
\item $T\gets\varnothing$.
\item Последовательно для каждой пары $(a_k,b_k)$, имеющейся в массиве 
$Pairs$, найти количество $w_k$ её вхождений в массив $Pairs$, 
cформировать тройку $(w_k,a_k,b_k)$ и добавить в $T$.
\end{enumerate}
\end{algorithm}

\begin{block}{}
Сложность $O(n\log n)$.
\end{block}

\end{frame}

\begin{frame}{Сведение к задаче о назначении}
\framesubtitle{Алгоритм построения перестановки по паросочетанию}

\begin{block}{Задача построения перестановки по паросочетанию}
\begin{description}
\item[Дано:] $M=\{(x_1,y_1),\ldots,(x_s,y_s)\}$~--- паросочетание
в двудольном графе $G=(X,Y,E,w)$, где $|X|=|Y|=n$ и $1\le s\le |E|$.
\item[Построить:] перестановку $\varphi\in S_n$, соответствующую $M$, 
т.~е. такую что $M=\{(i,\varphi(i))\colon\quad i=1,\ldots,n,\quad (i,\varphi(i))\in E\}$.
\end{description}
\end{block}

\begin{columns}[T]

\begin{column}{4.7cm}
\begin{block}{Пример}<visible@2->
$n=5$\\
$M=\{\alert<3>{(1,3)},\alert<4>{(2,5)},\alert<5>{(4,1)}\}$\\
\vspace{0.3cm}
$\varphi=\left(
\begin{array}{@{}c@{}c@{}c@{}c@{}c@{}}
1&2&3&4&5\\
\visible<3->{\downarrow}&\visible<4->{\downarrow}&\visible<6->{\downarrow}&\visible<5->{\downarrow}&\visible<7->{\downarrow}\\
\visible<3->{3}&\visible<4->{5}&\visible<6->{2}&\visible<5->{1}&\visible<7->{4}
\end{array}
\right)$\\
\vspace{0.3cm}
$A=\{1,2,5\},\;B=\{3,5,1\}$
\end{block}
\end{column}

\begin{column}{6.8cm}
\begin{block}{Построение}<visible@2->
%\begin{description}
%\item[Шаг 1.]
1. Сформировать множества\\
\quad $A=\{x_1,\ldots,x_s\},\quad B=\{y_1,\ldots,y_s\}$.\\
%\item[Шаг 2.]
2. Определить $\varphi$ на $A$:\\
\quad $\varphi(x_i)=y_i$ для $i=1,\ldots,s$.\\
%\item[Шаг 3.]
3. Определить $\varphi$ на всём множестве $X$:\\
\quad элементам из $X\setminus A$ биективно\\
\quad сопоставить элементы из $Y\setminus B$.
%\end{description}
\end{block}
\end{column}

\end{columns}
\end{frame}

\begin{frame}{Сведение к задаче о назначении}
\framesubtitle{Обоснование сведения задачи о наилучшем
соответствии между раскрасками}

\begin{block}{Предложение}
Пусть\\
\qquad\quad $a,b\in\Colorings_n$;\\
\qquad\quad $G_{a,b}=(X,Y,E,w)$~--- взвешенный двудольный граф для $a$ и $b$;\\
\qquad\quad $M$~--- максимальное паросочетание в $G_{a,b}$.\\
Тогда\\
\qquad\qquad\qquad\qquad $d(P_a,P_b)=n-w(M)$\\
и перестановка $\varphi\in S_n$, соответствующая паросочетанию $M$,\\
является наилучшим соответствием между раскрасками $a$ и $b$.
\end{block}

\begin{block}{Имеющиеся алгоритмы для задачи о назначении}
1. Kuhn \&\ Munkres~--- $O(mn^2)$, где $m$~--- число дуг;\\
2. Edmonds \&\ Karp~--- $O(mn\log n)$;\\
3. Gabow \&\ Tarjan~--- $O(mn^{\frac{1}{2}}\log nU)$, где $U$~--- наибольший вес.
\end{block}
\end{frame}

\begin{frame}{Сведение к задаче о назначении}
\framesubtitle{Алгоритм геометрического скрещивания разбиений}

\begin{columns}[T]

\begin{column}{7.5cm}
\begin{block}{Вход}
$a,b\in\Colorings_n$~--- родители, $p\in[0,1]$, ГПСЧ.
\end{block}
\end{column}

\begin{column}{4cm}
\begin{block}{Выход}
$s,t\in\Colorings_n$~--- потомки.
\end{block}
\end{column}

\end{columns}

\begin{algorithm}
\begin{enumerate}
\item Найти наилучшее соответствие $\varphi$ между раскрасками $a$ и $b$.
\item Изменить раскраску $a$ согласно найденному соответствию:
$\tilde{a}\gets\varphi\circ a$.
\item Применить однородное скрещивание
к $\tilde{a}$ и $b$ с вероятностью $p$ и получить потомков $s$ и $t$.
\end{enumerate}
\end{algorithm}

\begin{block}{Свойство}
Такое скрещивание разбиений является геометрическим,
то есть для потомков $s$ и $t$ выполняются равенства:\\
$d(P_a,P_s)+d(P_s,P_b)=d(P_a,P_b)$ и $d(P_a,P_t)+d(P_t,P_b)=d(P_a,P_b)$.
\end{block}

\end{frame}


\subsection{Жадный алгоритм}

\begin{frame}{Жадный алгоритм}
\framesubtitle{Для задачи о назначении}

\begin{block}{}
\begin{description}
\item[Вход:] $n\in\bZpositiv$ (количество вершин в б\'ольшей доле графа),\\
взвешенный двудольный граф в виде массива троек 
$(w(x,y),x,y)$, где $1\le x,y\le n$ и $w(x,y)$~--- вес дуги $(x,y)$.
\item[Выход:] $M$~--- паросочетание.
\end{description}
\end{block}

\begin{algorithm}
\begin{enumerate}
\item Отсортировать массив троек в порядке убывания весов.
\item $L\gets (\underbrace{0,\ldots,0}_{n})$, 
$R\gets (\underbrace{0,\ldots,0}_{n})$, $M\gets\varnothing$.\\
($L[x]$~--- такая вершина $y$, что $(x,y)\in M$; 
если $L[x]=0$, то такой вершины нет (аналогично для $R[y]$).)
\item Для каждой тройки $(w(x,y),x,y)$ проделать следующее: 
если $L[x] = 0$ и $R[y] = 0$, то $L[x]\gets y$, $R[y]\gets x$ 
и $M\gets M\cup\{(x,y)\}$.
\end{enumerate}
\end{algorithm}

\end{frame}

\begin{frame}{Жадный алгоритм}
\framesubtitle{Для задачи о наилучшем соответствии между раскрасками}

\begin{block}{}
\begin{description}
\item[Вход:] $a,b\in\Colorings_n$.
\item[Выход:] $\varphi$~--- перестановка.
\end{description}
\end{block}

\begin{algorithm}
\begin{enumerate}
\item Создать взвешенный двудольный граф $G_{a,b}$ 
в виде массива троек (вес, начало дуги, конец дуги) 
для раскрасок $a$ и $b$.
\item Найти с помощью жадного алгоритма 
паросочетание $M$ в $G_{a,b}$.
\item Построить перестановку $\varphi$, соответствующую 
паросочетанию $M$.
\end{enumerate}
\end{algorithm}
\end{frame}


\subsection{Свойства жадного алгоритма}

\begin{frame}{Свойства жадного алгоритма}
\framesubtitle{Лемма о доминирующей дуге}

\begin{block}{Лемма}
Пусть\quad\ $G=(X,Y,E,w)$~--- взвешенный двудольный граф,\\
\qquad\qquad $N$~--- паросочетание, найденное жадным алгоритмом.\\
Тогда для любой дуги $(x,y)\in E$ 
во множестве
\[
N_{x,y}\eqdef\{(u,v)\in N\colon\quad u=x\quad\vee\quad v=y\}
\]
найдётся такая дуга $(x_1,y_1)$, что $w(x_1,y_1) \ge w(x,y)$.
\end{block}
\end{frame}

\begin{frame}{Свойства жадного алгоритма}
\framesubtitle{Оценка для веса паросочетания}

\begin{block}{Предложение}
Пусть
\begin{description}
\item $G=(X,Y,E,w)$~--- взвешенный двудольный граф, 
\item $N$~--- паросочетание, найденное жадным алгоритмом, 
\item $M$~--- максимальное паросочетание в $G$.
\end{description}
Тогда
\[
w(M)\le 2w(N).
\]
\end{block}

\begin{block}{Идея доказательства}
Доказательство основано на лемме о доминирующей дуге.
Множитель~$2$ появляется из-за того, что двум дугам из $M$ 
может соответствовать одна дуга из $N$. 
\end{block}

\end{frame}

\begin{frame}{Свойства жадного алгоритма}
\framesubtitle{Оценка для расстояния между разбиениями}

\begin{block}{Предложение}
Пусть
\begin{description}
\item $P,Q\in\Partitions_n$,
\item $d(P,Q)$~--- расстояние между $P$ и $Q$,
\item $d_{g}(P,Q)$~--- приближённое расстояние 
между $P$ и $Q$, найденное жадным алгоритмом.
\end{description}
Тогда
\[
d_{g}(P,Q)\le 2d(P,Q).
\]
\end{block}

\begin{block}{Идея доказательства}
Доказательство основано на лемме о доминирующей дуге
и на формуле, которая выражает расстояние между разбиениями 
через вес максимального паросочетания. 
\end{block}
\end{frame}


\begin{frame}{Свойства жадного алгоритма}
\framesubtitle{Результаты жадного алгоритма 
для расстояния между разбиениями из $\Partitions_7$}


\begin{block}{Таблица результатов для $n=7$ ($|\Partitions_7|=877$)}
\begin{tabular}{c|cccccc}
$d_g\backslash d$&1&2&3&4&5&6\\
\hline
1&9\,093&&&&&\\
2&525&63\,854&&&&\\
3&&9\,569&157\,100&&&\\
4&&245&36\,671&90\,486&&\\
5&&&1\,074&11\,476&4\,001&\\
6&&&&&31&1\\
\end{tabular}
\end{block}
\begin{block}{}
\begin{tikzpicture}[xcomb,xscale=0.1,yscale=0.42, baseline=(current bounding box.west)]

\tikzstyle{plotline}=[line width=0.3cm,color=green]

\draw[style=plotline] plot coordinates {(84,0) (15,1) (1,2) (0,3)};

\draw (84.5,0) node[anchor=west] {$84\%$};
\draw (15.5,1) node[anchor=west] {$15\%$};
\draw (1.5,2) node[anchor=west] {$1\%$};

\draw[->] (0,-1)--(0,4); 
\draw (0,3.8) node[anchor=west] {$\Delta d=d_g-d$};
\foreach \xpos in {0,1,2,3}
  \draw (-.5,\xpos) node[anchor=east]{$\xpos$};
\end{tikzpicture}
\end{block}

\end{frame}

\begin{frame}{Жадный алгоритм устойчивого скрещивания разбиений}

\begin{columns}[T]

\begin{column}{8.5cm}
\begin{block}{Вход}
$a,b\in\Colorings_n$, вещественное число $p\in[0,1]$, ГПСЧ.
\end{block}
\end{column}

\begin{column}{3cm}
\begin{block}{Выход}
$s,t\in\Colorings_n$.
\end{block}
\end{column}

\end{columns}
\begin{algorithm}
\begin{enumerate}
\item Найти соответствие $\varphi$ между раскрасками $a$ и $b$ 
с помощью жадного алгоритма.
\item Изменить раскраску $a$ согласно найденному соответствию:
$\tilde{a}\gets\varphi\circ a$.
\item Применить однородное скрещивание
к $\tilde{a}$ и $b$ с вероятностью $p$ и получить потомков $s$ и $t$.
\end{enumerate}
\end{algorithm}

\begin{block}{Свойство}
$d(P_a,P_s)+d(P_s,P_b)\le 2d(P_a,P_b)$ и $d(P_a,P_t)+d(P_t,P_b)\le 2d(P_a,P_b)$
\end{block}

\end{frame}


\section{Применение в генетических алгоритмах}


\subsection{Опробованные эволюционные схемы}

\begin{frame}{Случайное порождение, эволюция с мутацией}

\begin{block}{Схема случайного порождения (СП)}
Случайное порождение упорядоченных раскрасок 
и выбор наилучшей.
\end{block}

\begin{block}{Алгоритм случайного порождения упорядоченной раскраски}
\begin{description}
\item[Вход:] $n\in\bZpositiv$, ГПСЧ.
\item[Выход:] упорядоченная раскраска $a\in\Colorings_n$.
\end{description}
\begin{enumerate}
\item $a\gets(1,0,\ldots,0)$.
\item Для $i=2,\ldots,n$:\qquad$mc\gets\max(c_1,\ldots,c_{i-1}) + 1$;\\
$\qquad\qquad\qquad\qquad\quad\ a[i]\gets$ случайное число из $\{1,\ldots,mc\}$.
\end{enumerate}
\end{block}

\begin{block}{Схема эволюции с мутацией (М)}
\begin{enumerate}
\item Мутация.
\item Отбор усечением.
\end{enumerate}
\end{block}

\end{frame}

\begin{frame}{Эволюция с мутацией и скрещиванием}

\begin{block}{Схема с устойчивым скрещиванием (УС)}
\begin{enumerate}
\item Устойчивое скрещивание, родители выбираются с помощью рулетки.
\item Мутация.
\item Отбор усечением.
\end{enumerate}
\end{block}

\begin{block}{Схема с тривиальным скрещиванием (ТС)}
\begin{enumerate}
\item Однородное скрещивание раскрасок, родители выбираются 
с помощью рулетки.
\item Мутация.
\item Отбор усечением.
\end{enumerate}
\end{block}

\end{frame}


\subsection{Экспериментальные результаты}

\begin{frame}{Задача о разбиении графа с минимизацией\\
связей между долями и несвязей внутри долей}

\begin{myproblem}
\begin{description}
\item[Дано:] неориентированный граф $G=(V,E)$.
\item[Найти:] разбиение $P$ множества вершин $V$ 
(число долей не фиксируется), такое что 
величина $B(V,E,P)+2C(V,E,P)$ минимальна.
\end{description}
\end{myproblem}

\begin{block}{}
Величина $B(V,E,P)$ соответсвует числу отсутствующих связей внути долей:
\[
B(V,E,P)=|\{(i,j)\colon (i,j)\notin E\wedge i\mysim P j\}|.
\]
Величина $C(V,E,P)$ соответствует числу связей между долями:
\[
C(V,E,P)=|\{(i,j)\colon (i,j)\in E\wedge i\notmysim P j\}|.
\]
\end{block}

\end{frame}


\begin{frame}{Задача о наилучшем разбиении графа}
\framesubtitle{Пример}

\begin{tikzpicture}[scale=1, baseline=(current bounding
box.north)]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen]

\visible<1,8,13>{
\node[] (v6) at (0,0) {$6$};
\node[] (v3) at (0,-4) {$3$};
\node[] (v2) at (2,-2.3) {$2$};
\node[] (v4) at (-1.3,-3.1) {$4$};
\node[] (v1) at (1.5,-1) {$1$};
\node[] (v5) at (-1.5,-1.5) {$5$};
}

\visible<2,3>{
\node[] (v6) at (0,0) {$6$};
\node[] (v3) at (0,-4) {$3$};
\node[M] (v2) at (2,-2.3) {$2$};
\node[] (v4) at (-1.3,-3.1) {$4$};
\node[M] (v1) at (1.5,-1) {$1$};
\node[] (v5) at (-1.5,-1.5) {$5$};
}

\visible<4,5>{
\node[] (v6) at (0,0) {$6$};
\node[M] (v3) at (0,-4) {$3$};
\node[] (v2) at (2,-2.3) {$2$};
\node[M] (v4) at (-1.3,-3.1) {$4$};
\node[] (v1) at (1.5,-1) {$1$};
\node[M] (v5) at (-1.5,-1.5) {$5$};
}

\visible<6,7>{
\node[M] (v6) at (0,0) {$6$};
\node[] (v3) at (0,-4) {$3$};
\node[] (v2) at (2,-2.3) {$2$};
\node[] (v4) at (-1.3,-3.1) {$4$};
\node[] (v1) at (1.5,-1) {$1$};
\node[] (v5) at (-1.5,-1.5) {$5$};
}

\visible<9,10>{
\node[] (v6) at (0,0) {$6$};
\node[] (v3) at (0,-4) {$3$};
\node[M] (v2) at (2,-2.3) {$2$};
\node[] (v4) at (-1.3,-3.1) {$4$};
\node[M] (v1) at (1.5,-1) {$1$};
\node[M] (v5) at (-1.5,-1.5) {$5$};
}

\visible<11,12>{
\node[M] (v6) at (0,0) {$6$};
\node[M] (v3) at (0,-4) {$3$};
\node[] (v2) at (2,-2.3) {$2$};
\node[M] (v4) at (-1.3,-3.1) {$4$};
\node[] (v1) at (1.5,-1) {$1$};
\node[] (v5) at (-1.5,-1.5) {$5$};
}

\visible<1>{
\draw (v1) to (v2);
\draw (v1) to (v3);
\draw (v2) to (v3);
\draw (v3) to (v4);
\draw (v3) to (v5);
\draw (v3) to (v6);
\draw (v4) to (v5);
}

\visible<2,9>{
\draw[darkgreen, very thick] (v1) to (v2);
\draw (v1) to (v3);
\draw (v2) to (v3);
\draw (v3) to (v4);
\draw (v3) to (v5);
\draw (v3) to (v6);
\draw (v4) to (v5);
}

\visible<3>{
\draw[darkgreen, very thick] (v1) to (v2);
\draw[red, very thick] (v1) to (v3);
\draw[red, very thick] (v2) to (v3);
\draw (v3) to (v4);
\draw (v3) to (v5);
\draw (v3) to (v6);
\draw (v4) to (v5);
}

\visible<4>{
\draw (v1) to (v2);
\draw[red, very thick] (v1) to (v3);
\draw[red, very thick] (v2) to (v3);
\draw[darkgreen, very thick] (v3) to (v4);
\draw[darkgreen, very thick] (v3) to (v5);
\draw (v3) to (v6);
\draw[darkgreen, very thick] (v4) to (v5);
}

\visible<6,7,8>{
\draw (v1) to (v2);
\draw[red, very thick] (v1) to (v3);
\draw[red, very thick] (v2) to (v3);
\draw (v3) to (v4);
\draw (v3) to (v5);
\draw[red, very thick] (v3) to (v6);
\draw (v4) to (v5);
}

\visible<5>{
\draw (v1) to (v2);
\draw[red, very thick] (v1) to (v3);
\draw[red, very thick] (v2) to (v3);
\draw[darkgreen, very thick] (v3) to (v4);
\draw[darkgreen, very thick] (v3) to (v5);
\draw[red, very thick] (v3) to (v6);
\draw[darkgreen, very thick] (v4) to (v5);
}

\visible<10>{
\draw[darkgreen, very thick](v1) to (v2);
\draw[red, very thick] (v1) to (v3);
\draw[red, very thick] (v2) to (v3);
\draw (v3) to (v4);
\draw[red, very thick] (v3) to (v5);
\draw (v3) to (v6);
\draw[red, very thick] (v4) to (v5);
\draw[thickarrow,red] (v1) to (v5);
\draw[thickarrow,red] (v2) to (v5);
}

\visible<11>{
\draw (v1) to (v2);
\draw[red,very thick] (v1) to (v3);
\draw[red,very thick] (v2) to (v3);
\draw[darkgreen,very thick] (v3) to (v4);
\draw[red, very thick] (v3) to (v5);
\draw[darkgreen, very thick] (v3) to (v6);
\draw[red, very thick] (v4) to (v5);
\draw[thickarrow,red] (v1) to (v5);
\draw[thickarrow,red] (v2) to (v5);
}

\visible<12>{
\draw (v1) to (v2);
\draw[red,very thick] (v1) to (v3);
\draw[red,very thick] (v2) to (v3);
\draw[darkgreen,very thick] (v3) to (v4);
\draw[red,very thick] (v3) to (v5);
\draw[darkgreen,very thick] (v3) to (v6);
\draw[red,very thick] (v4) to (v5);
\draw[thickarrow,red] (v1) to (v5);
\draw[thickarrow,red] (v2) to (v5);
\draw[thickarrow,red] (v4) to (v6);
}

\visible<13>{
\draw (v1) to (v2);
\draw[red,very thick] (v1) to (v3);
\draw[red,very thick] (v2) to (v3);
\draw (v3) to (v4);
\draw[red,very thick] (v3) to (v5);
\draw (v3) to (v6);
\draw[red,very thick] (v4) to (v5);
\draw[thickarrow,red] (v1) to (v5);
\draw[thickarrow,red] (v2) to (v5);
\draw[thickarrow,red] (v4) to (v6);
}

\end{tikzpicture}
\nolinebreak\quad
\begin{minipage}[t]{5cm}
\begin{block}{}
$\{\txtcell<2,3>{\{1,2\}},\txtcell<4,5>{\{3,4,5\}},\txtcell<6,7>{\{6\}}\}$

$B=\visible<3->{0}\visible<5->{+0}\visible<7->{+0}\visible<8->{=0}$

$C=\visible<3->{2}\visible<5->{+1}
\visible<7->{+0}\visible<8->{=3}$

$B+2C=\visible<8->{0+2\cdot 3=6$}
\end{block}
\par\bigskip
\begin{block}{}
$\{\txtcell<9,10>{\{1,2,5\}},\txtcell<11,12>{\{3,4,6\}}\}$

$B=\visible<10->{2}\visible<12->{+1}\visible<13->{=3}$

$C=\visible<10->{4}\visible<12->{+0}\visible<13->{=4}$

$B+2C=\visible<13->{3+2\cdot 4=11$}
\end{block}
\end{minipage}

\end{frame}


\begin{frame}{Задача о составлении максимального числа комплектов}

\begin{myproblem}
\begin{description}
\item[Дано:] множество $X$ из $n$ элементов,\\
для каждого элемента $x\in X$ задано $m$ неотрицательных чисел 
$w_1(x)$, $w_2(x)$, $\ldots$, $w_m(x)$,\\
для каждого $j\in\{1,\ldots,m\}$ 
задано неотрицательное целое число $b_j$.
\item[Найти:] максимальное число 
попарно непересекающихся комплектов в $X$, т.~е. 
подмножеств $Y\subset X$, обладающих свойством:
\[
\sum_{x\in Y} w_j(x)=b_j,\quad \forall j\in\{1,\ldots,m\}.
\]
\end{description}
\end{myproblem}

\end{frame}

\begin{frame}{Параметры тестирования}

\begin{block}{Объекты тестирования}
Схемы УС, ТС, М, СП в генетических алгоритмах 
для задачи о наилучшем разбиении графа 
и задачи о комплектах.
\end{block}

\begin{block}{Параметры тестирования}
\begin{tabular}{@{}ccc@{}}
Размер популяции & Вер-ть скрещивания & Вер-ть мутации\\
$n+10$ & $0.6$ & $0.1$
\end{tabular}
\end{block}

\begin{block}{}
$n$~--- число вершин в графе или число элементов в 
множестве.
\end{block}

\begin{block}{}
Сравение проводилось так, чтобы число создаваемых особей 
в каждой из тестируемых эволюционных схем было примерно 
одинаковым.
\end{block}
\end{frame}

\begin{frame}{Результаты для задачи о наилучшем разбиении графа}

\begin{myproblem}
\begin{description}
\item[Дано:] неориентированный граф $G=(V,E)$.
\item[Найти:] разбиение $P$ вершин $V$: 
$B(V,E,P)+2C(V,E,P)\to\min$.
\end{description}
\end{myproblem}

\begin{block}{Таблица результатов}
\begin{tabular}{@{}c|c|c||c|c||c|c@{}}
Схема&$|V|=17$&Время&$|V|=20$&Время&$|V|=50$&Время\\
\hline
УС &73,6 (62)&0,18~с&65,9&0,28~c&612,8&3,76~c\\
ТС &82,2 (62)&0,16~с&67,8&0,24~c&622,7&4,37~c\\
М  &102,5 (62)&0,19~с&81,2&0,31~c&666,8&4,76~c\\
СП &79,8 (62)&0,05~с&80,8&0,09~c&672,3&2,47~c\\
\hline\hline
СП   &77,2 (62)&0,19~с&80,3&0,28~c&672,3&3,77~c
\end{tabular}
\end{block}

\end{frame}

\begin{frame}{Результаты для задачи о комплектах}
\begin{myproblem}
\begin{description}
\item[Дано:] $X$ из $n$ элементов,\\
$w_1(x),w_2(x),\ldots,w_m(x)\in\bZnonnegativ$ для каждого $x\in X$,\\
$b_1,b_2,\ldots,b_m\in\bZnonnegativ$.
\item[Найти:] максимальное число комплектов в $X$.
\end{description}
\end{myproblem}

\begin{block}{Таблица результатов}
\begin{tabular}{@{}c|c|c||c|c||c|c@{}}
Схема&$n=17$&Время&$n=20$&Время&$n=50$&Время\\
\hline
УС &4,5&0,18~с&5,8&0,28~c&12,2&2,79~c\\
ТС &4,3&0,18~с&5,6&0,27~c&9,9&2,95~c\\
М  &3&0,21~с&4,5&0,34~c&6,2&4,11~c\\
СП &3&0,23~с&3,2&0,35~c&3&2,98~c\\
\end{tabular}
\end{block}

\end{frame}

\begin{frame}{Источники}

\begin{thebibliography}{2}

\beamertemplatearticlebibitems
\bibitem{Wikipedia}
Википедия, свободная энциклопедия.\\
\url{http://en.wikipedia.org} и \url{http://ru.wikipedia.org}.


\beamertemplatebookbibitems
\bibitem{GareyJohnson}
\textsc{Гэри~М., Джонсон~Д.}
Вычислительные машины и труднорешаемые задачи.~---
М.: <<Мир>>, 1982.

\beamertemplatearticlebibitems
\bibitem{DenoeudGuenoche_DistancePartition}
\textsc{L.~Denoeud et A.~Guenoche},
Distance des transferts entre partitions.~--- 5~p.

\beamertemplatearticlebibitems
\bibitem{Denoeud_Comparison_distance_partition}
\textsc{L.~Denoeud, H.~Garreta and A.~Guenoche},
Comparison of distancce indices between partitions.~--- 9~p.

\beamertemplatearticlebibitems
\bibitem{SaipLucchesi}
\textsc{H.~A.~Baier~Saip, C.~L.~Lucchesi},
Matching algorithms for bipartite graphs.~---
Relat\'orio T\'ecnico DCC~---
03/93.
\end{thebibliography}

\end{frame}

\end{document}
