#LyX 1.6.1 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
\date{}
\end_preamble
\use_default_options false
\language czech
\inputencoding auto
\font_roman ae
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\float_placement H
\paperfontsize 12
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder false
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\pdf_quoted_options "unicode"
\papersize a4paper
\use_geometry true
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\leftmargin 3cm
\topmargin 2cm
\rightmargin 2cm
\bottommargin 2cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation skip
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 2
\paperpagestyle empty
\tracking_changes false
\output_changes false
\author "" 
\author "" 
\end_header

\begin_body

\begin_layout Standard
\noindent
\align center

\size large
České vysoké učení technické v Praze
\begin_inset Newline newline
\end_inset

Fakulta elektrotechnická
\end_layout

\begin_layout Standard
\noindent
\align center
\begin_inset Graphics
	filename logocvut.pdf
	scale 200

\end_inset


\end_layout

\begin_layout Standard
\noindent
\align center

\size large
Diplomová práce
\end_layout

\begin_layout Standard
\noindent
\align center

\size larger
Moderní metody řešení problému pokrytí
\end_layout

\begin_layout Standard
\noindent
\align center

\size large
Michael Kalouš
\end_layout

\begin_layout Standard
\begin_inset VSpace vfill*
\end_inset


\end_layout

\begin_layout Standard
\noindent
\align center

\size large
Vedoucí práce: Ing.
 Petr Fišer
\end_layout

\begin_layout Standard
\noindent
\align center

\size large
Studijní program: Elektrotechnika a informatika, dobíhající, magisterský
\begin_inset Newline newline
\end_inset

Obor: Výpočetní technika
\end_layout

\begin_layout Standard
\noindent
\align center

\size large
leden 2009
\end_layout

\begin_layout Standard
\noindent
\align center

\size large
\begin_inset VSpace 2cm*
\end_inset


\begin_inset Newpage newpage
\end_inset


\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset VSpace vfill*
\end_inset

Poděkování
\end_layout

\begin_layout Standard
Mé poděkování patří panu Ing.
 Petru Fišerovi za trpělivé vedení a veškerý čas, který mi věnoval při zpracován
í této diplomové práce.
\begin_inset Newpage newpage
\end_inset


\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset VSpace vfill*
\end_inset

Prohlášení
\begin_inset Newline newline
\end_inset

Prohlašuji, že jsem svou diplomovou práci vypracoval samostatně a použil
 jsem pouze podklady uvedené v přiloženém seznamu.
\begin_inset Newline newline
\end_inset

Nemám závažný důvod proti užití tohoto školního díla ve smyslu §
\begin_inset space ~
\end_inset

60 Zákona č.
 121/2000
\begin_inset space ~
\end_inset

Sb., o
\begin_inset space ~
\end_inset

právu autorském, o
\begin_inset space ~
\end_inset

právech souvisejících s právem autorským a
\begin_inset space ~
\end_inset

o změně některých zákonů (autorský zákon).
\end_layout

\begin_layout Standard
V Praze dne:
\begin_inset space \hspace*{}
\length 8cm
\end_inset

Michael Kalouš
\begin_inset VSpace 4cm
\end_inset


\end_layout

\begin_layout Standard
Declaration
\begin_inset Newline newline
\end_inset

I hereby declare that I have completed this master thesis independently
 and that I have listed all the literature and publications used.
 I have no objection to usage of this work in compliance with the act §
\begin_inset space ~
\end_inset

60 Zákona č.121/2000 Sb.
 (copyright law), and with the rights connected with the copyright act including
 the changes in the act.
 
\end_layout

\begin_layout Standard
V Praze dne
\begin_inset space \hspace*{}
\length 8cm
\end_inset

Michael Kalouš
\begin_inset VSpace 4cm
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset VSpace 1cm*
\end_inset


\series bold
Abstract
\end_layout

\begin_layout Standard
In this work is desribed and programmed one of exact algorithms for set
 covering problem, so called hybrid algorithm, that combines greedy algorithm,
 Lagrangian heuristic, non-binary genethic algorithm and L-class enumeration.
 Also alternative variant of the algorithm that replaces genethic algorithm
 by simulated annealing is programmed.
 Covering problem occurs in several fields of computer science, logic synthesis
 and reliability analysis.
 Solving the covering problem may be sometimes rather time-consuming.
 Performance of hybrid algorithm and its alternative variant is studied
 and compared to the AURA exact algorithm.
 Hybrid algorithm is incorporated to the program BOOM.
\begin_inset VSpace vfill*
\end_inset


\end_layout

\begin_layout Standard

\series bold
Anotace
\end_layout

\begin_layout Standard
V této diplomové práci je popsána a naprogramována jedna z exaktních metod
 pro řešení problému pokrytí - tzv.
 hybridní algoritmus, který kombinuje použití hladových algoritmů, Lagrangeovsko
u heuristiku, nebinární genetický algoritmus a výčet L-tříd.
 Naprogramována byla rovněž alternativní varianta hybridního algoritmu,
 kde je namísto nebinárního genetického algoritmu použito simulované ochlazování.
 Problém pokrytí se objevuje v množství oblastí počítačového výzkumu, syntéze
 logických obvodů a analýze spolehlivosti.
 Řešení problému pokrytí je výpočetně velmi náročné.
 Studována je výkonnost hybridního algoritmu a jeho alternativní varianty
 a výkonnost je srovnána s exaktním algoritmem AURA.
 Hybridní algoritmus je začleněn do programu BOOM.
\begin_inset VSpace 2cm*
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagestyle{plain}
\end_layout

\begin_layout Plain Layout


\backslash
linepenalty 1000
\end_layout

\end_inset


\end_layout

\begin_layout Section
Úvod
\end_layout

\begin_layout Standard
Problém pokrytí má použití v mnoha oblastech počítačového výzkumu, syntéze
 logických obvodů, dvouúrovňové minimalizaci logických obvodů, analýze spolehliv
osti a přesného kódování stavů sekvenčních logických obvodů.
\end_layout

\begin_layout Standard
Řešení problému pokrytí je obecně výpočetně velmi náročná záležitost.
 Pro řešení problému pokrytí byly navrženy algoritmy s různou složitostí
 a kvalitou řešení.
 Cílem algoritmů je nalézt co nejlepší řešení v přijatelném čase.
\end_layout

\begin_layout Standard
Řešení problému pokrytí může být dosaženo pomocí rekurzivního algoritmu,
 který zkouší přípustné kombinace prvků řešení, dokud není nalezeno minimální
 pokrytí.
 Řešení tímto způsobem je velmi časově náročné.
 Snížení výpočetního času může být dosaženo například ořezáváním stavového
 prostoru; neprohledávají se ty jeho části, o kterých je předem známo, že
 v nich optimální řešení není možné nalézt.
\end_layout

\begin_layout Standard
Při řešení rozsáhlých kombinatorických problémů a požadavku na optimalitu
 řešení se často používá technika kombinace aproximativních a exaktních
 algoritmů, kdy je nejprve aproximativním algoritmem nalezeno přípustné
 řešení, které slouží jako výchozí bod pro exaktní algoritmus.
\end_layout

\begin_layout Standard
Tato práce vychází z článku 
\begin_inset Quotes eld
\end_inset

A hybrid algorithm for set covering problem
\begin_inset Quotes erd
\end_inset

, jehož autory jsou od Anton V.
 Eremeev, Alexandr A.
 Kolokolov a Lidia A.
 Zaozerskaya, kde je popsán tzv.
 
\emph on
hybridní algoritmus
\emph default
 pro řešení problému pokrytí, založený na technice zmíněné v předchozím
 odstavci.
 Hybridní algoritmus kombinuje tři aproximativní a jeden exaktní algoritmus.
 Výsledkem činnosti hybridního algoritmu je optimální řešení problému pokrytí.
\end_layout

\begin_layout Standard
Cílem této práce je popsat (s ohledem na možnost implementace) a implementovat
 hybridní algoritmus pro problém pokrytí, implementovat alternativní variantu
 hybridního algoritmu, prostudovat výkonnost algoritmu a porovnat ji s jinými
 algoritmy.
 Dalším cílem práce je začlenit algoritmus do programu BOOM, tak aby mohl
 být využit pro minimalizaci logických funkcí jako alternativa k dosud začleněný
m algoritmům.
\end_layout

\begin_layout Standard
Hybridní algoritmus pro problém pokrytí, včetně alternativní varianty byl
 naprogramován ve formě knihovny v ANSI dialektu jazyka C a začleněn do
 programu BOOM, prozkoumána byla jeho efektivita na různých problémech pokrytí
 a porovnána s algoritmem AURA.
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section
Problém pokrytí
\end_layout

\begin_layout Standard
Problém pokrytí je kombinatorický optimalizační NP-těžký problém.
\end_layout

\begin_layout Standard
Neformálně lze problém pokrytí popsat takto: Na vstupu máme několik množin,
 které mají společné prvky.
 Naším úkolem je vybrat minimální sadu množin tak, aby tato sada obsahovala
 všechny prvky, které jsou obsaženy v kterékoliv množině ze vstupu.
\end_layout

\begin_layout Standard
Formálně lze popsat problém pokrytí několika způsoby, zde jsou uvedeny dva.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Problém-pokrytí-specifikovaný"

\end_inset

Problém pokrytí specifikovaný pojmy maticové algebry
\end_layout

\begin_layout Subsubsection
Definice
\end_layout

\begin_layout Standard
Nechť 
\begin_inset Formula $Y=\{y_{1},y_{2},...y_{m}\}$
\end_inset

 je množina řádků a 
\begin_inset Formula $X=\{x_{1},x_{2},...x_{n}\}$
\end_inset

 je množina sloupců matice 
\begin_inset Formula $A$
\end_inset

 o rozměrech 
\begin_inset Formula $m\times n$
\end_inset

 a CENA je funkce definovaná na množině 
\begin_inset Formula $X$
\end_inset

 taková, že přiřazuje každému prvku 
\begin_inset Formula $x_{j}\in X$
\end_inset

 reálné číslo.
 Prvek 
\begin_inset Formula $x_{j}\in X$
\end_inset

 pokrývá prvek 
\begin_inset Formula $y_{i}\in Y$
\end_inset

, pokud 
\begin_inset Formula $A[i,j]=1$
\end_inset

, jinak 
\begin_inset Formula $A[i,j]=0$
\end_inset

.
 Problém pokrytí 
\begin_inset Formula $<X,Y,CENA>$
\end_inset

 spočívá v nalezení podmnožiny 
\begin_inset Formula $S$
\end_inset

 množiny 
\begin_inset Formula $X$
\end_inset

, s nejmenší cenou, takové, že pro každý prvek 
\begin_inset Formula $y$
\end_inset

 z množiny 
\begin_inset Formula $Y$
\end_inset

 existuje prvek 
\begin_inset Formula $x$
\end_inset

 z množiny 
\begin_inset Formula $X$
\end_inset

 tak, že 
\begin_inset Formula $x$
\end_inset

 pokrývá 
\begin_inset Formula $y$
\end_inset

.
\end_layout

\begin_layout Subsubsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Řešení"

\end_inset

Řešení
\end_layout

\begin_layout Standard
Řešením je nalezení minimální podmnožiny sloupců z matice 
\begin_inset Formula $A$
\end_inset

 tak, že každý řádek matice 
\begin_inset Formula $A$
\end_inset

 je pokrytý alespoň jedním sloupcem podmnožiny.
 Hledání řešení spočívá ve výběru sloupců do řešení, tak dlouho, dokud nejsou
 pokryty všechny řádky.
\end_layout

\begin_layout Standard
Při hledání řešení je možné pracovat pouze s 
\emph on
cyklickým jádrem
\emph default
 matice 
\begin_inset Formula $A$
\end_inset

, které se získá tzv.
 
\emph on
odstraněním dominance;
\emph default
 tyto pojmy budou objasněny v příkladu.
\end_layout

\begin_layout Subsubsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Jednoduchý-příklad"

\end_inset

Jednoduchý příklad
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\noindent
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{3}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{4}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{3}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{4}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
c
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
5
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset

 
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:Jednoduchý-příklad"

\end_inset

Jednoduchý příklad
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Hledaná podmnožina 
\begin_inset Formula $S$
\end_inset

 je: 
\begin_inset Formula $\left\{ x_{2},x_{3}\right\} $
\end_inset

.
 Tato podmnožina sloupců pokrývá všechny řádky s cenou 4.
\end_layout

\begin_layout Subsubsection*
Dominance řádků
\end_layout

\begin_layout Standard
Říkáme, že řádek 
\begin_inset Formula $y'$
\end_inset

 z množiny řádků 
\begin_inset Formula $Y$
\end_inset

 dominuje řádku 
\begin_inset Formula $y$
\end_inset

 právě tehdy, když všechny prvky množiny sloupců 
\begin_inset Formula $X$
\end_inset

, které pokrývají řádek 
\begin_inset Formula $y'$
\end_inset

, pokrývají také řádek 
\begin_inset Formula $y$
\end_inset

.
\end_layout

\begin_layout Standard
V tabulce 
\begin_inset CommandInset ref
LatexCommand ref
reference "tab:Jednoduchý-příklad"

\end_inset

 snadno zjistíme, že řádek 
\begin_inset Formula $y_{3}$
\end_inset

 dominuje řádku 
\begin_inset Formula $y_{4}$
\end_inset

, protože řádek 
\begin_inset Formula $y_{3}$
\end_inset

 je pokryt sloupci 
\begin_inset Formula $x_{2}$
\end_inset

 a 
\begin_inset Formula $x_{4}$
\end_inset

 a oba tyto sloupce také pokrývají řádek 
\begin_inset Formula $y_{4}$
\end_inset

.
 Totéž platí i pro řádek 
\begin_inset Formula $y_{2}$
\end_inset

.
 To, že řádek 
\begin_inset Formula $y_{3}$
\end_inset

 dominuje řádkům 
\begin_inset Formula $y_{2}$
\end_inset

 a 
\begin_inset Formula $y_{4}$
\end_inset

, nám říká, že vybereme-li do řešení sloupec pokrývající řádek 
\begin_inset Formula $y_{3}$
\end_inset

, pak výběrem tohoto sloupce vždy pokryjeme i řádky 
\begin_inset Formula $y_{2}$
\end_inset

 a 
\begin_inset Formula $y_{4}$
\end_inset

.
 Proto můžeme řádky 
\begin_inset Formula $y_{2}$
\end_inset

 a 
\begin_inset Formula $y_{4}$
\end_inset

 vyloučit z matice.
 Snadno také nahlédneme, že řádek 
\begin_inset Formula $y_{1}$
\end_inset

 dominuje řádku 
\begin_inset Formula $y_{4}$
\end_inset

.
\end_layout

\begin_layout Subsubsection*
Dominance sloupců
\end_layout

\begin_layout Standard
Říkáme, že sloupec 
\begin_inset Formula $x'$
\end_inset

 dominuje sloupci 
\begin_inset Formula $x$
\end_inset

 právě tehdy, když všechny prvky množiny řádků 
\begin_inset Formula $Y$
\end_inset

 pokryté 
\begin_inset Formula $x$
\end_inset

 jsou také pokryté sloupcem 
\begin_inset Formula $x'$
\end_inset

.
 
\end_layout

\begin_layout Standard
V tabulce 
\begin_inset CommandInset ref
LatexCommand ref
reference "tab:Jednoduchý-příklad"

\end_inset

 vidíme, že sloupec 
\begin_inset Formula $x_{4}$
\end_inset

 dominuje sloupcům 
\begin_inset Formula $x_{2}$
\end_inset

 a 
\begin_inset Formula $x_{1}$
\end_inset

 a zároveň sloupec 
\begin_inset Formula $x_{2}$
\end_inset

 dominuje sloupcům 
\begin_inset Formula $x_{4}$
\end_inset

 a 
\begin_inset Formula $x_{1}$
\end_inset

.
 Nabízí se tedy možnost vyloučit z matice sloupce 
\begin_inset Formula $x_{4}$
\end_inset

 nebo 
\begin_inset Formula $x_{2}$
\end_inset

.
 Při vylučování sloupců se však musí dát pozor na to, aby se nepřišlo o
 minimální řešení; vyloučení je možné jen tehdy, pokud cena dominujícího
 sloupce je menší než cena sloupce, kterému sloupec dominuje.
 Nelze tedy vyloučit sloupec 
\begin_inset Formula $x_{2}$
\end_inset

, kterému dominuje sloupec 
\begin_inset Formula $x_{4}$
\end_inset

, protože jeho cena je menší než cena sloupce 
\begin_inset Formula $x_{4}$
\end_inset

.
\end_layout

\begin_layout Standard
Po odstranění dominancí sloupců mohou vzniknout nové dominance řádků a naopak,
 proto je potřeba postup odstraňování dominance opakovat.
 Případným opakovaným odstraňováním dominance získáme 
\emph on
cyklické jádro řešení
\emph default
.
\end_layout

\begin_layout Subsubsection*
Nezbytné sloupce
\end_layout

\begin_layout Standard
Existuje-li řádek, který je pokryt jen jedním jediným sloupcem, je zřejmé,
 že tento sloupec bude vždy patřit do řešení, proto jej můžeme z matice
 ihned odstranit a přidat jej nakonec k řešení vzniklému postupem v odstavci
 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Řešení"

\end_inset

.
 Sloupec s touto vlastností se označuje jako 
\emph on
nezbytný.

\emph default
 Příkladem takového sloupce je sloupec 
\begin_inset Formula $x_{3}$
\end_inset

, který jako jediný pokrývá řádek 
\begin_inset Formula $y_{1}$
\end_inset

.
\end_layout

\begin_layout Subsection
Problém pokrytí specifikovaný pojmy teorie množin
\end_layout

\begin_layout Subsubsection
Definice
\end_layout

\begin_layout Standard
Uvažujme množinu 
\begin_inset Formula $M=\left\{ 1,...,m\right\} $
\end_inset

 a podmnožiny 
\begin_inset Formula $M_{j}\subseteq M$
\end_inset

, kde 
\begin_inset Formula $J\in N=\left\{ 1,...,n\right\} $
\end_inset

.
 Podmnožina 
\begin_inset Formula $J\in N$
\end_inset

 je pokrytím množiny 
\begin_inset Formula $M$
\end_inset

 když 
\begin_inset Formula $\cup_{(j\in J)}M_{j}=M$
\end_inset

.
 Pro každou podmnožinu 
\begin_inset Formula $M_{j}$
\end_inset

 je stanovena kladná cena 
\begin_inset Formula $c_{j}$
\end_inset

.
 Problém pokrytí je pak nalezení pokrytí s minimální celkovou cenou.
\end_layout

\begin_layout Subsubsection
Příklad
\end_layout

\begin_layout Standard
Uvažujme množinu 
\begin_inset Formula $M=\left\{ a,b,c,d\right\} $
\end_inset

a podmnožiny z následující tabulky:
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Podmnožina 
\begin_inset Formula $M_{j}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cena 
\begin_inset Formula $c_{j}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $M_{1}=\left\{ b\right\} $
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
2
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $M_{2}=\left\{ b,c,d\right\} $
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $M_{3}=\left\{ a,d\right\} $
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $M_{4}=\left\{ b,c,d\right\} $
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
5
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Řešením je pak podmnožina 
\begin_inset Formula $J=\left\{ 2,3\right\} $
\end_inset

.
 Sjednocení podmnožin 
\begin_inset Formula $M_{2}$
\end_inset

 a 
\begin_inset Formula $M_{3}$
\end_inset

 je pokrytím s minimální celkovou cenou.
 Příklad je vlastně převedením výše uvedeného příkladu do pojmů teorie množin.
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section
Exaktní algoritmy pro řešení problému pokrytí
\end_layout

\begin_layout Subsection
Základní rekurzivní algoritmus
\end_layout

\begin_layout Standard
Rekurzivní algoritmus vybírá prvek 
\begin_inset Formula $x$
\end_inset

 z množiny 
\begin_inset Formula $X$
\end_inset

 a generuje dva podproblémy.
 Jeden podproblém spočívá v zařazení prvku 
\begin_inset Formula $x$
\end_inset

 do minimálního řešení, druhý podproblém spočívá ve vyjmutí vyjmutí 
\begin_inset Formula $x$
\end_inset

 z minimálního řešení.
 Algoritmus je pak aplikován na cyklická jádra těchto dvou podproblémů.
 Časová složitost algoritmu je exponenciální 
\begin_inset Formula $O(2^{n})$
\end_inset

, kde 
\begin_inset Formula $n$
\end_inset

 značí počet sloupců matice.
\end_layout

\begin_layout Standard
Na obrázku je znázorněn postup rekurzivních volání pro matici o velikosti
 3
\begin_inset space ~
\end_inset

x
\begin_inset space ~
\end_inset

3 v nejhorším možném případě.
 Vyhledávací prostor je binární strom.
 Uzly představují vybraný sloupec 
\begin_inset Formula $x$
\end_inset

, ohodnocení hran pak označuje, zda byl sloupec 
\begin_inset Formula $x$
\end_inset

 přidán do minimálního řešení (1), nebo odebrán z minimálního řešení (0).
 Listy pak představují pokrytí.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\noindent
\align center
\begin_inset Graphics
	filename space1.png

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Rekurzivní volání pro matici 3
\begin_inset space ~
\end_inset

x
\begin_inset space ~
\end_inset

3
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Metoda větví a hranic (Branch and Bound)
\end_layout

\begin_layout Subsubsection
Základní varianta
\end_layout

\begin_layout Standard
Metoda větví a hranic představuje vylepšení základního rekurzivního algoritmu,
 vyhledávací prostor je ořezáván.
 Jsou ořezána místa, kde cena zatím nalezeného částečného pokrytí je větší
 než cena nejlepšího dosud nalezeného pokrytí.
 V těchto místech nemá smysl v rekurzi pokračovat, protože rekurze nemůže
 vést k lepšímu řešení.
\end_layout

\begin_layout Standard
Vyhledávací prostor je binárním stromem s kořenem, který představuje vstupní
 problém.
 Hrany reprezentují rekurzivní volání a jsou ohodnoceny 0 nebo 1 podle toho,
 zda je sloupec uvažovaný v rodičovském uzlu do řešení přidán nebo z něj
 odebrán.
 Vnitřní uzly stromu reprezentují částečné řešení.
 Listy stromu představují nalezená pokrytí.
\end_layout

\begin_layout Standard
Algoritmus se rekurzivně aplikuje na cyklická jádra podproblémů.
 Vždy se vybere sloupec 
\begin_inset Formula $x$
\end_inset

 do řešení a vyškrtne se společně s řádky, které pokrývá.
 Odebráním sloupce mohou vzniknout dominantní řádky, proto se při větvení
 provede odstranění dominance.
 Je-li matice prázdná, pak bylo nalezeno řešení.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout LyX-Code
Branch_and_bound(Matrix,Solution) {
\end_layout

\begin_layout LyX-Code
  vyřeš_dominance(Matrix,Sol)
\end_layout

\begin_layout LyX-Code
  if (matrix==
\begin_inset Formula $\varnothing$
\end_inset

) {
\end_layout

\begin_layout LyX-Code
    if cena(Solution)<cena(best) return newBest
\begin_inset Newline newline
\end_inset

    else return 
\begin_inset Formula $\varnothing$
\end_inset


\end_layout

\begin_layout LyX-Code
  }
\end_layout

\begin_layout LyX-Code
  else {
\end_layout

\begin_layout LyX-Code
    vyber do řešení sloupec j
\end_layout

\begin_layout LyX-Code
     if ( cena(cesta(j))+cena(j) < cena(best) )
\end_layout

\begin_layout LyX-Code
       Branch_and_bound(Matrix,Sol1)
\end_layout

\begin_layout LyX-Code
     vyškrtni sloupec j
\end_layout

\begin_layout LyX-Code
     if ( cena(cesta(j)) < cena(best) )
\end_layout

\begin_layout LyX-Code
       Branch_and_bound(Matrix,Sol2)
\end_layout

\begin_layout LyX-Code
     return min (Sol1,Sol2)
\end_layout

\begin_layout LyX-Code
  }
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Branch and Bound
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout Subsubsection
Vylepšená varianta
\end_layout

\begin_layout Standard
Metodu větví a hranic je možné ještě dále vylepšovat.
 Cílem vylepšení je stanovit takové podmínky pro ořezání, které vedou k
 zachování správnosti řešení a zároveň k ořezání více větví vyhledávacího
 prostoru.
\end_layout

\begin_layout Standard
Podmínka 
\begin_inset Formula $cena(cesta(j))+cena(j)<cena(best)$
\end_inset

 slouží k ořezání těch větví stromu, kde cena řešení přesahuje cenu již
 nalezeného řešení.
 Hodnota na levé straně nerovnosti se označuje jako 
\emph on
spodní hranice řešení.
 
\emph default
Je-li známa spodní hranice, může se při splnění podmínky rekurze ukončovat.
 Otázkou zůstává, zda není možné hodnotu na levé straně bezpečným způsobem
 zvýšit.
\end_layout

\begin_layout Standard
Předpokládejme, že řešení problému pokrytí není menší než nějaké číslo 
\begin_inset Formula $K$
\end_inset

.
 Pak cena částečného řešení, kterému odpovídá uzel 
\begin_inset Formula $u$
\end_inset

 je rovna hodnotě 
\begin_inset Formula $c=cesta(u)+K$
\end_inset

.
 Známe-li cenu řešení 
\begin_inset Formula $best$
\end_inset

, pak lze rekurzi ukončit za podmínky, že 
\begin_inset Formula $cena(cesta(u))+K\geqq best$
\end_inset

.
\end_layout

\begin_layout Standard
Existuje možnost, jak takové číslo K nalézt.
\end_layout

\begin_layout Paragraph*
Nezávislá podmnožina řádků.
\end_layout

\begin_layout Standard
Nechť 
\begin_inset Formula $<X,Y,CENA>$
\end_inset

 je problém pokrytí a 
\begin_inset Formula $Y'$
\end_inset

 je podmnožina 
\begin_inset Formula $Y$
\end_inset

 taková, že pro dva různé libovolné prvky 
\begin_inset Formula $y_{1}$
\end_inset

 a 
\begin_inset Formula $y_{2}$
\end_inset

 z množiny 
\begin_inset Formula $Y'$
\end_inset

, všechny prvky 
\begin_inset Formula $x$
\end_inset

, které pokrývají 
\begin_inset Formula $y_{1}$
\end_inset

 nepokrývají 
\begin_inset Formula $y_{2}$
\end_inset

 a naopak.
 Množina 
\begin_inset Formula $Y'$
\end_inset

 je pak 
\emph on
nezávislou podmnožinou
\emph default
 
\begin_inset Formula $Y$
\end_inset

 a poskytuje spodní hranici řešení.
\end_layout

\begin_layout Standard
Neformálně řečeno, v matici A se nachází množiny řádků takové, že žádný
 sloupec pokrývající řádek z jedné množiny nepokrývá ani jeden řádek z jiné
 množiny.
 V tabulce 
\begin_inset CommandInset ref
LatexCommand ref
reference "tab:K-nezávislé-podmnožině"

\end_inset

 je nezávislou podmnožinou řádků podmnožina 
\begin_inset Formula $Y'=\left\{ y_{1},y_{2}\right\} $
\end_inset

, neboť 
\begin_inset Formula $y_{1}$
\end_inset

 je pokryt právě sloupci 
\begin_inset Formula $x_{1}$
\end_inset

 a 
\begin_inset Formula $x_{2}$
\end_inset

 a 
\begin_inset Formula $y_{2}$
\end_inset

 je pokryt právě sloupci 
\begin_inset Formula $x_{3}$
\end_inset

a 
\begin_inset Formula $x_{4}$
\end_inset

.
 Z toho lze vyvodit, že pro pokrytí bude třeba vybrat jeden sloupec z podmnožiny
 
\begin_inset Formula $\left\{ x_{1},x_{2}\right\} $
\end_inset

 a jeden sloupec z podmnožiny 
\begin_inset Formula $\left\{ x_{3},x_{4}\right\} $
\end_inset

.
 Vybereme-li 
\begin_inset Quotes eld
\end_inset

nejlevnější
\begin_inset Quotes erd
\end_inset

 sloupce, dostáváme minimální cenu pokrytí 
\begin_inset Formula $2+2=4$
\end_inset

.
\end_layout

\begin_layout Standard
\noindent
\align left
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\noindent
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{3}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $y_{4}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{3}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{4}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
c
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
4
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:K-nezávislé-podmnožině"

\end_inset

K nezávislé podmnožině řádků
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Formálněji.
 Máme-li 
\begin_inset Formula $K$
\end_inset

 nezávislých podmnožin řádků, pak je pro pokrytí třeba vybrat minimálně
 
\begin_inset Formula $|K|$
\end_inset

 sloupců.
 Určíme-li maximální počet nezávislých podmnožin řádků (označme MSIR), dostaneme
 tak také mohutnost množiny 
\begin_inset Formula $Y'$
\end_inset

.
\end_layout

\begin_layout Standard
Chceme-li pokrýt řádek 
\begin_inset Formula $y_{1}\in Y'$
\end_inset

, pak je nutné pro jeho pokrytí vybrat sloupec 
\begin_inset Formula $x$
\end_inset

 s cenou 
\begin_inset Formula $cena(x)$
\end_inset

.
 Vybereme sloupec, který pokrývá řádek s nejnižší cenou a přičteme k MSIR.
 Takto upravená hodnota MSIR je spodní hranice řešení problému pokrytí.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout LyX-Code
Branch_and_bound_MSIR(Matrix,Solution) {
\end_layout

\begin_layout LyX-Code
  vyřeš_dominance(Matrix,Sol)
\end_layout

\begin_layout LyX-Code
  if (matrix==
\begin_inset Formula $\varnothing$
\end_inset

) {
\end_layout

\begin_layout LyX-Code
    if cena(Solution)<cena(best) return newBest
\begin_inset Newline newline
\end_inset

    else return 
\begin_inset Formula $\varnothing$
\end_inset


\end_layout

\begin_layout LyX-Code
  }
\end_layout

\begin_layout LyX-Code
  else {
\end_layout

\begin_layout LyX-Code
    vyber do řešení sloupec j
\end_layout

\begin_layout LyX-Code
    najdi MSIR pro podproblém
\end_layout

\begin_layout LyX-Code
     if ( cena(cesta(j)) + cena(j) + MSIR < cena(best) )
\end_layout

\begin_layout LyX-Code
       Branch_and_bound(Matrix,Sol1)
\end_layout

\begin_layout LyX-Code
     vyškrtni sloupec j
\end_layout

\begin_layout LyX-Code
     najdi MSIR pro podproblém
\end_layout

\begin_layout LyX-Code
     if ( cena(cesta(j)) + MSIR < cena(best) )
\end_layout

\begin_layout LyX-Code
       Branch_and_bound(Matrix,Sol2)
\end_layout

\begin_layout LyX-Code
     return min (Sol1,Sol2)
\end_layout

\begin_layout LyX-Code
  }
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Metoda větví a hranic doplněná o MSIR
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Nalezení MSIR je však problém, který je stejně složitý jako problém pokrytí,
 proto se k
\begin_inset space ~
\end_inset

nalezení MSIR používá heuristika.
 Její použití pouze sníží hodnotu MSIR a zvětší část stavového prostoru,
 který je třeba prohledat.
 Řešení zůstává řešením exaktním.
\end_layout

\begin_layout Standard
Algoritmus lze ještě dále zlepšit 
\emph on
zvýšením spodní hranice
\emph default
.
\end_layout

\begin_layout Standard
Mějme 
\begin_inset Formula $Y'$
\end_inset

 nezávislou podmnožinu 
\begin_inset Formula $Y$
\end_inset

.
 Nechť 
\begin_inset Formula $lBound$
\end_inset

 je spodní hranice nutná k pokrytí 
\begin_inset Formula $Y$
\end_inset

 získaná z 
\begin_inset Formula $Y'$
\end_inset

 a 
\begin_inset Formula $uBound$
\end_inset

 je horní hranice.
\begin_inset Newline newline
\end_inset

Označme 
\begin_inset Formula $X'=\left\{ x\in X|x\cap Y'=\varnothing,cena(cesta\, k\, uzlu)+lbound+cena(y)>=uBound\right\} $
\end_inset

.
 Pak problém může být zredukován na problém
\begin_inset Formula $<X-X',Y,CENA>$
\end_inset


\end_layout

\begin_layout Standard
Srozumitelněji řečeno, nalezneme-li při hledání řešení sloupce, které nepokrývaj
í maximální množinu nezávislých řádků a zároveň splňují danou nerovnost,
 můžeme je z matice vyškrtnout a přepočítat MSIR (v
\begin_inset space ~
\end_inset

důsledku vyškrtnutí sloupců se může změnit).
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section
Základní aproximativní algoritmy
\end_layout

\begin_layout Subsection
Přirozená heuristika
\end_layout

\begin_layout Standard
Princip přirozené heuristiky spočívá ve výběru prvku 
\begin_inset Formula $x$
\end_inset

, který pokrývá největší počet prvků 
\begin_inset Formula $Y$
\end_inset

.
 Pracuje se s funkcí NAT_HEURISTIC(
\emph on
Matrix
\emph default
,
\emph on
Solution
\emph default
), která z matice vybere sloupec pokrývající nejvíce řádků, společně s pokrytými
 řádky vybraný sloupec z matice vyjme a tak pokračuje dokud není matice
 prázdná.
 Současně se plní seznam sloupců 
\emph on
Solution
\emph default
 vybraných do řešení.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout LyX-Code
1.Zjisti počty jedniček ve sloupcích
\end_layout

\begin_layout LyX-Code
2.Vyber sloupec s největším počtem jedniček, vyjmi
\begin_inset Newline newline
\end_inset

sloupec a vyjmi řádky pokryté sloupcem
\end_layout

\begin_layout LyX-Code
3.Není-li Matrix==
\begin_inset Formula $\varnothing$
\end_inset

,jdi na 1
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Přirozená heuristika
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Přirozená heuristika představuje velmi rychlý algoritmus, ale také algoritmus,
 který nedává příliš dobré výsledky; odchylky od exaktního řešení jsou příliš
 velké.
\end_layout

\begin_layout Subsection
Contrib-Add heuristika
\end_layout

\begin_layout Standard
Tato heuristika je založena na výpočtu příspěvků jednotlivých sloupců k
 ceně.
 Heuristika pracuje se dvěma veličinami: Síla pokrytí řádku (CF) a sloupcový
 příspěvek (CC).
\end_layout

\begin_layout Standard
\begin_inset Formula \[
CF(y_{i})=\frac{1}{\overset{m}{\underset{j=1}{\sum}}A[i,j]}\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula \[
CC(x_{i})=\overset{n}{\underset{i=1}{\sum}}A[i,j]\cdot CF(y_{i})\]

\end_inset


\end_layout

\begin_layout Standard
Ze vzorců vyplývá, že síla pokrytí řádků se zmenšuje s počtem sloupců, které
 řádek pokrývají (je-li řádek pokryt mnoha sloupci, jeho síla pokrytí je
 malá).
 Sloupcový příspěvek se s počtem pokrytých řádek zvyšuje (pokrývá-li sloupec
 mnoho řádků, jeho sloupcový příspěvek je velký).
\end_layout

\begin_layout Standard
Heuristika upřednostňuje sloupce, které pokrývají mnoho řádků s velkou silou
 pokrytí.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout LyX-Code
1.Když Matrix==
\begin_inset Formula $\varnothing$
\end_inset

, skonči
\end_layout

\begin_layout LyX-Code
2.Spočítej pro všechna 
\begin_inset Formula $x_{j}$
\end_inset

 hodnotu veličiny 
\begin_inset Formula $CC(x_{j})$
\end_inset


\end_layout

\begin_layout LyX-Code
3.Vyber sloupec s největší hodnotou 
\begin_inset Formula $CC(x_{j})$
\end_inset

 a vyjmi ho společně s řádky, které pokrývá
\end_layout

\begin_layout LyX-Code
4.Jdi na 1
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Contrib-Add heuristika
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Contrib-Add heuristika dává výsledky, které se více blíží výsledkům exaktních
 algoritmů.
 Složitost algoritmu je 
\begin_inset Formula $O(n^{2})$
\end_inset

, kde 
\begin_inset Formula $n$
\end_inset


\begin_inset space ~
\end_inset

je počet sloupců.
\end_layout

\begin_layout Standard
U obou heuristik může nastat situace, kdy na vyjmutí z matice budou existovat
 dva kandidáti.
 Při implementaci je třeba vždy vybrat pouze jednoho kandidáta (například
 náhodným výběrem).
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Hladový-algoritmus-dle"

\end_inset

Hladový algoritmus dle Chvátala
\end_layout

\begin_layout Standard
Algoritmus je popsán v článku 
\begin_inset CommandInset citation
LatexCommand cite
key "key-6"

\end_inset

.
\end_layout

\begin_layout Enumerate
Ze sloupců, které nejsou součástí pokrytí, vyber sloupec 
\begin_inset Formula $i$
\end_inset

 takový, že poměr
\begin_inset Newline newline
\end_inset

ceny sloupce 
\begin_inset Formula $c$
\end_inset

 a počtu nově pokrytých řádků při zařazení sloupce 
\begin_inset Formula $c$
\end_inset

 do pokrytí je minimální
\end_layout

\begin_layout Enumerate
Nejsou-li pokryty všechny řádky, pokračuj krokem 1
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Hladový-balasho"

\end_inset

Hladový algoritmus dle Balase a Hoa
\end_layout

\begin_layout Standard
Algoritmus je popsán například v článku 
\begin_inset CommandInset citation
LatexCommand cite
key "key-9"

\end_inset

.
\end_layout

\begin_layout Standard
Algoritmus pracuje tak, že je náhodně vybrán řádek, který dosud není pokryt
 žádným ze sloupců.
 Pro každý sloupec, kterým je možné náhodně vybraný řádek pokrýt, je vypočten
 poměr počtu řádků, které by tímto sloupcem byly nově pokryty a ceny sloupce.
 Sloupec s maximálním poměrem se stane součástí řešení.
 
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section
Hybridní algoritmus pro problém pokrytí
\end_layout

\begin_layout Subsection
Úvod
\end_layout

\begin_layout Standard
Hybridní algoritmus pro problém pokrytí popsaný v článku 
\begin_inset CommandInset citation
LatexCommand cite
key "key-1"

\end_inset

 si klade za cíl nalézt optimální řešení problému pokrytí v přijatelném
 čase.
 Tohoto cíle se snaží dosáhnout vhodnou kombinací aproximativních algoritmů,
 které navazujíce jeden na druhý, postupně vylepšují přípustné řešení problému
 pokrytí.
\end_layout

\begin_layout Standard
Přípustné řešení nalezené aproximativními algoritmy je pak použito jako
 vstup pro finální exaktní algoritmus, kterým se získá řešení optimální.
 Exaktní algoritmus je urychlován vnitřními aproximativními kroky.
\end_layout

\begin_layout Standard
V hybridním algoritmu se používají následující techniky:
\end_layout

\begin_layout Itemize
Hladový algoritmus pro problém pokrytí dle Chvátala popsaný v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Hladový-algoritmus-dle"

\end_inset


\end_layout

\begin_layout Itemize
Lagrangeovská heuristika pro problém pokrytí, která je popsána v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Lagrangeovská-heuristika-(LH)"

\end_inset


\end_layout

\begin_layout Itemize
Nebinární genetický algoritmus rozebraný v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Genetický-algoritmus"

\end_inset


\end_layout

\begin_layout Itemize
Exaktní výčet L-tříd (LCE) urychlovaný použitím Lagrangeovské heuristiky
\end_layout

\begin_layout Subsection
Specifikace problému pokrytí pro potřeby hybridního algoritmu
\end_layout

\begin_layout Standard
Pro potřeby hybridního algoritmu specifikujeme problém pokrytí jako
\emph on
 
\emph default
problém
\emph on
 celočíselného
\emph default
 
\emph on
lineárního programování (CLP problém):
\end_layout

\begin_layout Standard
\begin_inset Formula \[
min\left\{ c\mathbf{x}:A\mathbf{x}\geq\mathbf{e},\mathbf{x}\in\left\{ 0,1\right\} ^{n}\right\} \]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $A$
\end_inset

 je matice nul a jedniček o velikosti 
\begin_inset Formula $m\times n$
\end_inset

.
 Prvky matice nabývají hodnoty: 
\begin_inset Formula $A_{ij}=1$
\end_inset

 právě tehdy když sloupec 
\begin_inset Formula $j$
\end_inset

 pokrývá řádek 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Standard
Dále 
\begin_inset Formula $\mathbf{c}$
\end_inset

 je vektor cen, který má 
\begin_inset Formula $n$
\end_inset

 prvků a 
\begin_inset Formula $\mathbf{e}$
\end_inset

 je vektor jedniček o 
\begin_inset Formula $m$
\end_inset

 prvcích.
 Předpokládáme také, že 
\emph on
sloupce matice
\emph default
 
\begin_inset Formula $A$
\end_inset

 
\emph on
jsou seřazeny do posloupnosti s neklesající cenou
\emph default
.
\end_layout

\begin_layout Standard
Řešení si můžeme představit jako bod v části n-rozměrného prostoru.
 Část prostoru je určena omezujícími podmínkami a má tvar polyhedronu, který
 vznikne jako průnik poloprostorů.
\end_layout

\begin_layout Standard
Pro ilustraci si převedeme zadání příkladu z odstavce 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Jednoduchý-příklad"

\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset Formula \[
A=\left[\begin{array}{cccc}
0 & 0 & 1 & 0\\
1 & 1 & 0 & 1\\
1 & 0 & 0 & 1\\
1 & 0 & 1 & 1\end{array}\right],\mathbf{c}=\left(1,2,3,5\right),\mathbf{e}=\left(1,1,1,1\right)\]

\end_inset


\end_layout

\begin_layout Standard
Co vlastně zadání CLP problému říká ? Hledáme vektor 
\begin_inset Formula $\mathbf{x}=\left(x_{1},...,x_{n}\right)$
\end_inset

, 
\begin_inset Formula $\mathbf{x}\in\left\{ 0,1\right\} ^{n}$
\end_inset

 takový, že jsou splněny následující podmínky:
\end_layout

\begin_layout Standard
Součet 
\begin_inset Formula $x_{1}.c_{1}+x_{2}.c_{2}+x_{3}.c_{3}+x_{4}.c_{4}$
\end_inset

 je minimální
\end_layout

\begin_layout Standard
\begin_inset Formula $a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}+a_{14}x_{4}\geq e_{1}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $a_{21}x_{1}+a_{22}x_{2}+a_{23}x_{3}+a_{24}x_{4}\geq e_{2}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $a_{31}x_{1}+a_{32}x_{2}+a_{33}x_{3}+a_{34}x_{4}\geq e_{3}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $a_{41}x_{1}+a_{42}x_{2}+a_{43}x_{3}+a_{44}x_{4}\geq e_{4}$
\end_inset


\end_layout

\begin_layout Subsection
Celkové schéma hybridního algoritmu
\end_layout

\begin_layout Enumerate
Algoritmus začne nalezením přibližného řešení problému pokrytí hladovým
 algoritmem.
 Cenu tohoto řešení označme jako 
\begin_inset Formula $c(gd^{0})$
\end_inset

.
 
\end_layout

\begin_layout Enumerate
Dále je řešení problému nalezeno pomocí Lagrangeovské heuristiky.
 Tím se získá nejvyšší dolní mez ceny řešení 
\begin_inset Formula $LB$
\end_inset

 a nějaké (ne nutně optimální, ale pokud možno kvalitní) řešení problému
 pokrytí, jehož cenu označíme
\begin_inset Formula $c(lg^{0})$
\end_inset

.
\end_layout

\begin_layout Enumerate
Hybridní algoritmus končí, jestliže 
\begin_inset Formula $c(gd^{0})=LB$
\end_inset

, nebo 
\begin_inset Formula $c(lg^{0})=LB$
\end_inset

.
 Při splnění jedné z těchto podmínek bylo nalezeno optimální řešení hladovým
 algoritmem nebo přímo Lagrangeovskou heuristikou.
\end_layout

\begin_layout Enumerate
Pro další kroky algoritmu máme k
\begin_inset space ~
\end_inset

dispozici informaci, že cena řešení nepřekročí horní mez 
\begin_inset Formula $UB=min\{c(lg^{0}),c(gd^{0})\}$
\end_inset

.
 
\end_layout

\begin_layout Enumerate
Horní mez se ještě může snížit nebinárním genetickým algoritmem GAH, jehož
 úkolem je simulovat evoluci přípustných řešení.
 Cenu řešení nalezeného genetickým algoritmem označme 
\begin_inset Formula $c(ga^{0})$
\end_inset

.
\begin_inset Newline newline
\end_inset

Hybridní algoritmus skončí, jestliže 
\begin_inset Formula $c(ga^{0})=LB$
\end_inset

.
 Při splnění této podmínky bylo algoritmem GAH nalezeno optimální řešení.
\end_layout

\begin_layout Enumerate
Následuje algoritmus výčet L-tříd, který je jako jediný exaktní.
 Základem algoritmu LCE je hledání řešení 
\emph on
speciálně formulovaných LP problémů
\emph default
, které jsou řešeny simplexovou metodou.
 Simplexová metoda je výpočetně velice náročná, proto se v algoritmu používají
 dva vnitřní aproximativní kroky, kterými jsou Lagrangeovská heuristika
 pro problém pokrytí a jednoduchá heuristika pro testování skupin L-tříd.
\end_layout

\begin_layout Standard
V dalším textu jsou jednotlivé části hybridního algoritmu podrobněji rozebrány
 a popsány.
\end_layout

\begin_layout Subsection
Lagrangeovská heuristika pro problém pokrytí
\end_layout

\begin_layout Subsubsection
Principy Lagrangeovské relaxace
\end_layout

\begin_layout Standard
Lagrangeovská relaxace optimalizačních problémů s omezujícími podmínkami
 je velmi často používanou technikou pro jejich řešení.
\end_layout

\begin_layout Standard
Lagrangeovská relaxace optimalizačních problémů je vytvořena:
\end_layout

\begin_layout Itemize
Odstraněním množiny omezujících podmínek
\end_layout

\begin_layout Itemize
Převedením těchto podmínek do optimalizační funkce ve formě tzv.
 trestných koeficientů, které se nazývají 
\emph on
Lagrangeovské multiplikátory
\emph default
.
\end_layout

\begin_layout Subsubsection
Relaxace problému pokrytí
\end_layout

\begin_layout Standard
Mějme problém pokrytí:
\end_layout

\begin_layout Standard
\begin_inset Formula $min\left\{ c\mathbf{x}:A\mathbf{x}\geq\mathbf{1},\mathbf{x}\in\left\{ 0,1\right\} ^{n}\right\} $
\end_inset


\end_layout

\begin_layout Standard
Omezující podmínku, kterou lze zapsat také jako: 
\begin_inset Formula $\overset{n}{\underset{j=1}{\sum}}a_{ij}x_{j}\geq1$
\end_inset

 relaxujeme a definujeme Lagrangeovské multiplikátory 
\begin_inset Formula $t_{i}\in(0,\infty)$
\end_inset

 pro každý řádek matice 
\begin_inset Formula $A$
\end_inset

, která má 
\begin_inset Formula $m$
\end_inset

 řádků a 
\begin_inset Formula $n$
\end_inset

 sloupců.
 Po relaxaci dostaneme 
\emph on
problém lagrangeovské relaxace
\emph default
 (dále bude označován jako PLR) odpovídající následujícímu předpisu:
\end_layout

\begin_layout Standard
\begin_inset Formula \begin{equation}
min\,\overset{n}{\underset{j=1}{\sum}}(c_{j}-\overset{m}{\underset{j=1}{\sum}}(t_{i}a_{ij})x_{j}+\overset{m}{\underset{j=1}{\sum}}t_{i},\, x_{j}\in\{0,1\}\label{eq:plr}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Dále zavedeme tzv.
 
\emph on
redukovanou cenu sloupce
\emph default
 
\end_layout

\begin_layout Standard
\begin_inset Formula \[
\overline{c}_{j}=(c_{j}-\overset{m}{\underset{j=1}{\sum}}t_{i}a_{ij})\]

\end_inset


\end_layout

\begin_layout Standard
Lagrangeovské multiplikátory definované pro každý řádek matice 
\begin_inset Formula $A$
\end_inset

 charakterizují 
\emph on
míru neplnění původních omezujících podmínek
\emph default
 aktuálním řešením pro jednotlivé řádky.
 Ze vzorce pro redukovanou cenu sloupce vyplývá to, že bude-li sloupec pokrývat
 řádky s větší mírou neplnění omezujících podmínek, jeho redukovaná cena
 bude nižší a jeho zařazení do řešení je tudíž žádoucí.
\end_layout

\begin_layout Standard
Řešíme-li PLR, plnění předpisu (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:plr"

\end_inset

) (minimalizace) můžeme dosáhnout pouze vhodnou volbou sloupců.
 Vybíráme do řešení sloupce, jejichž redukovaná cena je záporná - podle
 předchozího odstavce tak pokryjeme právě ty řádky, které mají velkou míru
 neplnění omezujících podmínek.
\end_layout

\begin_layout Standard
Řešení PLR nemusí být přípustným řešením problému pokrytí, avšak modifikace
 řešení PLR přidáváním nebo odebíráním sloupců může vést k dobrým řešením.
 Heuristický algoritmus, který používá řešení PLR a Lagrangeovské multiplikátory
 se nazývá 
\emph on
Lagrangeovskou heuristikou
\emph default
.
\end_layout

\begin_layout Standard
Lagrangeovské heuristiky pro problém pokrytí pracují tak, že začnou s řešením
 PLR, přidají do řešení sloupce tak, aby upravené řešení bylo řešením problému
 pokrytí a případně odeberou z řešení sloupce nadbytečné.
 Pravidla pro přidávání či odebírání sloupců mohou být určena různě, vznikne
 tak několik variant lagrangeovské heuristiky.
 Pravidla jsou převzata z 
\begin_inset CommandInset citation
LatexCommand cite
key "key-7"

\end_inset

.
\end_layout

\begin_layout Subsubsection
Výstupy lagrangeovské heuristiky
\end_layout

\begin_layout Standard
Lagrangeovská heuristika poskytuje dva výstupy:
\end_layout

\begin_layout Itemize
Dolní mez řešení původního problému.
 Získaná dolní mez se používá v průběhu algoritmu LCE
\begin_inset space ~
\end_inset

-
\begin_inset space ~
\end_inset

viz sekce 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Výčet-L-tříd-(LCE"

\end_inset

 k omezení počtu spuštění simplexové metody k řešení speciálních LP problémů
 - viz sekce 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Krok-2-algoritmu"

\end_inset

.
\end_layout

\begin_layout Itemize
Řešení (ne nutně optimální) problému pokrytí.
 Cena tohoto řešení se rovněž využívá v algoritmu LCE, viz opět 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Krok-2-algoritmu"

\end_inset

.
\end_layout

\begin_layout Subsubsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Lagrangeovská-heuristika-(LH)"

\end_inset

Postup při řešení problému pokrytí
\end_layout

\begin_layout Standard
Lagrangeovskou heuristiku budeme z úsporných důvodů označovat jako LH.
 LH zavádí proměnné, jejichž význam je uveden v tabulce 
\begin_inset CommandInset ref
LatexCommand ref
reference "tab:Proměnné-LH"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="2">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="left" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Proměnná
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Význam
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $ZLB$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Optimální hodnota optimalizační funkce PLR
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $ZUB$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cena nejlepšího dosud nalezeného přípustného řešení problému pokrytí
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $LB$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nejvyšší dosud nalezená dolní mez
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $P_{k}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Dolní meze při zařazení sloupců k do řešení
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{i}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Lagrangeovské multiplikátory
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:lhvars"

\end_inset


\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:Proměnné-LH"

\end_inset

Proměnné LH
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection*
Krok 0.
 Předzpracování
\end_layout

\begin_layout Enumerate
Sloupce se seřadí podle vzrůstající ceny.
 Je-li cena sloupců stejná, pak preferován je ten sloupec, který pokryje
 více řádků.
\end_layout

\begin_layout Enumerate
Řádky se seřadí tak, aby první byly řádky pokryté nejméně sloupci
\end_layout

\begin_layout Subsubsection*
Krok 1 Inicializace
\end_layout

\begin_layout Standard
\begin_inset Formula $LB=-\infty,\, ZUB=\infty$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $P_{j}=c_{j}\,(j=1,...,n),\, t_{i}=min(c_{j}:a_{ij}=1)\,(i=1,...m)$
\end_inset


\end_layout

\begin_layout Subsubsection*
Krok 2 Řešení PLR
\end_layout

\begin_layout Standard
Vyřeší se PLR se současnou množinou lagrangeovských multiplikátorů.
 Řešení označme 
\begin_inset Formula $\mathbf{x}$
\end_inset

 a cenu řešení 
\begin_inset Formula $ZLB$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $ZLB=\overset{m}{\underset{j=1}{\sum}}\overline{C}_{j}x_{j}+\overset{m}{\underset{j=1}{\sum}}t_{i}$
\end_inset


\end_layout

\begin_layout Standard
Aktualizuje se 
\begin_inset Formula $LB=max\{LB,ZLB\}$
\end_inset

.
 Sloupec je součástí řešení právě tehdy když jeho redukovaná cena je záporná.
 Řešení PLR nemusí být přípustným řešením problému pokrytí, avšak při konstrukci
 řešení problému pokrytí se z řešení PLR vychází.
\end_layout

\begin_layout Subsubsection*
Krok 3 Konstrukce řešení problému pokrytí
\end_layout

\begin_layout Paragraph*
Varianta 1
\end_layout

\begin_layout Enumerate
Nechť 
\begin_inset Formula $S=\left\{ j|x_{j}=1,j=1,...,n\right\} $
\end_inset

 je řešení PLR.
 
\begin_inset Formula $S$
\end_inset

 je množina 
\emph on
indexů sloupců
\emph default
.
\end_layout

\begin_layout Enumerate
Vybereme řádek, který není pokryt žádným sloupcem z množiny 
\begin_inset Formula $S$
\end_inset

, index tohoto řádku označme 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Přidáme do množiny 
\begin_inset Formula $S$
\end_inset

 sloupec s minimálním indexem, který pokrývá řádek s indexem 
\begin_inset Formula $i$
\end_inset

.
 Jdeme na
\begin_inset space ~
\end_inset

2.
\end_layout

\begin_layout Enumerate
Procházíme množinu 
\begin_inset Formula $S$
\end_inset

 od nejvyššího indexu sloupce k nejnižšímu.
 Můžeme-li sloupec vyjmout z množiny při zachování pokrytí, vyjmeme jej
 z množiny 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Enumerate
Aktualizujeme proměnnou 
\begin_inset Formula $ZUB$
\end_inset

.
 
\begin_inset Formula $ZUB=min(ZUB,\underset{j\in S}{\sum}c_{j})$
\end_inset

.
\end_layout

\begin_layout Standard
Tato varianta představuje původní řešení navržené Beasleym a nevyužívá informace
 z vypočtených lagrangeovských multiplikátorů.
 Ostatní varianty tyto informace různým způsobem využívají.
\end_layout

\begin_layout Paragraph*
Varianta 2
\end_layout

\begin_layout Enumerate
Nechť 
\begin_inset Formula $S=\left\{ j|x_{j}=1,j=1,...,n\right\} $
\end_inset

 je řešení PLR.
 
\begin_inset Formula $S$
\end_inset

 je množina 
\emph on
indexů sloupců
\emph default
.
\end_layout

\begin_layout Enumerate
Vybereme řádek, který není pokryt žádným sloupcem z množiny 
\begin_inset Formula $S$
\end_inset

, index tohoto řádku označme 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Projdeme 
\begin_inset Formula $q$
\end_inset

 nejlevnějších 
\begin_inset Quotes eld
\end_inset

kandidátských
\begin_inset Quotes erd
\end_inset

 sloupců, které pokrývají řádek s indexem 
\begin_inset Formula $i$
\end_inset

 a vybereme sloupec, který má nejnižší 
\emph on
redukovanou
\emph default
 cenu.
 Konstanta 
\begin_inset Formula $q$
\end_inset

 je předem dána.
 Menší hodnota konstanty 
\begin_inset Formula $q$
\end_inset

 vede k úspoře výpočetního času za cenu horší kvality zkonstruovaného řešení.
\end_layout

\begin_layout Enumerate
Procházíme množinu 
\begin_inset Formula $S$
\end_inset

 od nejvyššího indexu sloupce k nejnižšímu.
 Můžeme-li sloupec vyjmout z množiny při zachování pokrytí, vyjmeme jej
 z množiny 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Enumerate
Aktualizujeme proměnnou 
\begin_inset Formula $ZUB$
\end_inset

.
 
\begin_inset Formula $ZUB=min(ZUB,\underset{j\in S}{\sum}c_{j})$
\end_inset

.
\end_layout

\begin_layout Paragraph*
Varianta 3
\end_layout

\begin_layout Enumerate
Nechť 
\begin_inset Formula $S=\left\{ j|x_{j}=1,j=1,...,n\right\} $
\end_inset

 je řešení PLR.
 
\begin_inset Formula $S$
\end_inset

 je množina 
\emph on
indexů sloupců
\emph default
.
\end_layout

\begin_layout Enumerate
Vybereme řádek, který není pokryt žádným sloupcem z množiny 
\begin_inset Formula $S$
\end_inset

, index tohoto řádku označme 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Projdeme 
\begin_inset Formula $q$
\end_inset

 nejlevnějších 
\begin_inset Quotes eld
\end_inset

kandidátských
\begin_inset Quotes erd
\end_inset

 sloupců, které pokrývají řádek s indexem 
\begin_inset Formula $i$
\end_inset

 a vybereme sloupec, který má nejnižší 
\emph on
modifikovanou redukovanou
\emph default
 cenu.
 Konstanta 
\begin_inset Formula $q$
\end_inset

 je předem dána.
 Menší hodnota konstanty 
\begin_inset Formula $q$
\end_inset

 vede k ušetření výpočetního času za cenu horší kvality zkonstruovaného
 řešení.
\begin_inset Newline newline
\end_inset

Při výpočtu modifikované redukované ceny se Lagrangeovské multiplikátory,
 příslušející již pokrytým řádkům, položí rovny nule.
\end_layout

\begin_layout Enumerate
Procházíme množinu 
\begin_inset Formula $S$
\end_inset

 od nejvyššího indexu sloupce k nejnižšímu.
 Můžeme-li sloupec vyjmout z množiny při zachování pokrytí, vyjmeme jej
 z množiny 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Enumerate
Aktualizujeme proměnnou 
\begin_inset Formula $ZUB$
\end_inset

.
 
\begin_inset Formula $ZUB=min(ZUB,\underset{j\in S}{\sum}c_{j})$
\end_inset

.
\end_layout

\begin_layout Paragraph*
Varianta 4
\end_layout

\begin_layout Enumerate
Nechť 
\begin_inset Formula $S=\left\{ j|x_{j}=1,j=1,...,n\right\} $
\end_inset

 je řešení PLR.
 
\begin_inset Formula $S$
\end_inset

 je množina 
\emph on
indexů sloupců
\emph default
.
\end_layout

\begin_layout Enumerate
Vybereme řádek, který není pokryt žádným sloupcem z množiny 
\begin_inset Formula $S$
\end_inset

, index tohoto řádku označme 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Projdeme 
\begin_inset Formula $q$
\end_inset

 nejlevnějších 
\begin_inset Quotes eld
\end_inset

kandidátských
\begin_inset Quotes erd
\end_inset

 sloupců, které pokrývají řádek s indexem 
\begin_inset Formula $i$
\end_inset

 a vybereme sloupec, který má nejnižší 
\emph on
redukovanou
\emph default
 cenu.
 Konstanta 
\begin_inset Formula $q$
\end_inset

 je předem dána.
 Menší hodnota konstanty 
\begin_inset Formula $q$
\end_inset

 vede k úspoře výpočetního času za cenu horší kvality zkonstruovaného řešení
\end_layout

\begin_layout Enumerate
Seřadíme sloupce z množiny 
\begin_inset Formula $S$
\end_inset

 podle redukované ceny
\end_layout

\begin_layout Enumerate
Procházíme množinu 
\begin_inset Formula $S$
\end_inset

 od sloupce s nejvyšší redukovanou cenou ke sloupci s nejnižší redukovanou
 cenou.
 Můžeme-li sloupec vyjmout z množiny při zachování pokrytí, vyjmeme jej
 z množiny 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Enumerate
Aktualizujeme proměnnou 
\begin_inset Formula $ZUB$
\end_inset

.
 
\begin_inset Formula $ZUB=min(ZUB,\underset{j\in S}{\sum}c_{j})$
\end_inset

.
\end_layout

\begin_layout Paragraph*
Varianta 5
\end_layout

\begin_layout Enumerate
Nechť 
\begin_inset Formula $S=\left\{ j|x_{j}=1,j=1,...,n\right\} $
\end_inset

 je řešení PLR.
 
\begin_inset Formula $S$
\end_inset

 je množina 
\emph on
indexů sloupců
\emph default
.
\end_layout

\begin_layout Enumerate
Vybereme řádek, který není pokryt žádným sloupcem z množiny 
\begin_inset Formula $S$
\end_inset

, index tohoto řádku označme 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Projdeme 
\begin_inset Formula $q$
\end_inset

 nejlevnějších 
\begin_inset Quotes eld
\end_inset

kandidátských
\begin_inset Quotes erd
\end_inset

 sloupců, které pokrývají řádek s indexem 
\begin_inset Formula $i$
\end_inset

 a vybereme sloupec, který má nejnižší 
\emph on
modifikovanou redukovanou
\emph default
 cenu.
 Konstanta 
\begin_inset Formula $q$
\end_inset

 je předem dána.
 Menší hodnota konstanty 
\begin_inset Formula $q$
\end_inset

 vede k úspoře výpočetního času za cenu horší kvality zkonstruovaného řešení.
\begin_inset Newline newline
\end_inset

Při výpočtu modifikované redukované ceny se Lagrangeovské multiplikátory,
 příslušející již pokrytým řádkům, položí rovny nule.
\end_layout

\begin_layout Enumerate
Seřadíme sloupce z množiny 
\begin_inset Formula $S$
\end_inset

 podle modifikované redukované ceny.
\end_layout

\begin_layout Enumerate
Procházíme množinu 
\begin_inset Formula $S$
\end_inset

 od sloupce s nejvyšší redukovanou cenou ke sloupci s nejnižší redukovanou
 cenou.
 Můžeme-li sloupec vyjmout z množiny při zachování pokrytí, vyjmeme jej
 z množiny 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Enumerate
Aktualizujeme proměnnou 
\begin_inset Formula $ZUB$
\end_inset

.
 
\begin_inset Formula $ZUB=min(ZUB,\underset{j\in S}{\sum}c_{j})$
\end_inset

.
\end_layout

\begin_layout Subsubsection*
Krok 4 Možnost zastavení
\end_layout

\begin_layout Standard
Jestliže 
\begin_inset Formula $\left\lceil LB\right\rceil =ZUB$
\end_inset

, pak je LH ukončena.
 Operace nad proměnnou 
\begin_inset Formula $LB$
\end_inset

 je nalezení nejbližší vyšší nebo rovné celočíselné hodnoty.
\end_layout

\begin_layout Subsubsection*
Krok 5 Aktualizace 
\begin_inset Formula $P_{k}$
\end_inset

, vyloučení sloupců
\end_layout

\begin_layout Standard
Uvážíme-li, že pokud k zadání problému pokrytí přidáme omezující podmínku
 spočívající ve vnucení určitého sloupce do řešení, dostaneme nový problém
 pokrytí, pro jehož dolní mez 
\begin_inset Formula $NLB$
\end_inset

 platí:
\begin_inset Newline newline
\end_inset


\begin_inset Formula $NLB=ZLB+\overline{c}_{k}$
\end_inset

, pokud sloupec není v řešení PLR.
\begin_inset Newline newline
\end_inset


\begin_inset Formula $NLB=ZLB$
\end_inset

, pokud sloupec je v řešení PLR.
\end_layout

\begin_layout Standard
Aktualizace 
\begin_inset Formula $P_{k}$
\end_inset


\end_layout

\begin_layout Standard
Jestliže 
\begin_inset Formula $x_{k}=0$
\end_inset

, pak 
\begin_inset Formula $P_{k}=max(P_{k},ZLB+\overline{c_{k}})$
\end_inset


\end_layout

\begin_layout Standard
Jestliže 
\begin_inset Formula $x_{k}=1$
\end_inset

, pak 
\begin_inset Formula $P_{k}=max(P_{k},ZLB)$
\end_inset


\end_layout

\begin_layout Standard
Z dalších úvah můžeme vyloučit sloupce, pro které platí, že 
\begin_inset Formula $P_{k}\geq ZUB$
\end_inset

 tak, že položíme 
\begin_inset Formula $c_{k}=\infty$
\end_inset

.
 Je-li dolní mez řešení při zařazení daného sloupce větší než nejlepší dosud
 nalezená dolní mez, nemůže zařazení sloupce vést ke zlepšení řešení.
\end_layout

\begin_layout Standard
Vzhledem k tomu, že práce s hodnotou nekonečno může při použití výpočetní
 techniky činit potíže, při implementaci algoritmu je vhodnější použít masku
 sloupců, nebo jejich spojový seznam.
\end_layout

\begin_layout Subsubsection*
Krok 6 Výpočet subgradientu
\end_layout

\begin_layout Standard
\begin_inset Formula $G_{i}=1-\overset{n}{\underset{j=1}{\sum}}a_{ij}x_{j}$
\end_inset


\end_layout

\begin_layout Standard
Podobně jako gradient udává směr nejvyššího spádu funkce, subgradient je
 vektor, který udává směr dalšího postupu při řešení.
 Jak vyplývá ze vzorce, složky subgradientu pro dosud nepokryté řádky jsou
 kladné, pro ostatní jsou nulové nebo záporné.
 Podle vypočteného subgradientu se modifikují Lagrangeovské multiplikátory
 tak, aby indukovaly nižší redukované ceny sloupců pokrývajících řádky,
 jež dosud nebyly pokryty.
 Složky subgradientu náležející k těmto řádkům jsou rovny 1.
\end_layout

\begin_layout Standard
Podle 
\begin_inset CommandInset citation
LatexCommand cite
key "key-7"

\end_inset

 je užitečné subgradient upravit, tak že 
\begin_inset Formula $G_{i}=0$
\end_inset

, jestliže 
\begin_inset Formula $t_{i}=0$
\end_inset

 a zároveň 
\begin_inset Formula $G_{i}<0$
\end_inset

.
\end_layout

\begin_layout Standard
Jestliže 
\begin_inset Formula $\overset{m}{\underset{j=1}{\sum}}(G_{i})^{2}=0$
\end_inset

, nelze určit směr dalšího postupu a Lagrangeovská heuristika končí.
\end_layout

\begin_layout Subsubsection*
Krok 7 Velikost kroku
\end_layout

\begin_layout Standard
Modifikace lagrangeovských multiplikátorů probíhá v krocích.
 Velikost kroku je definována následujícím vzorcem.
\end_layout

\begin_layout Standard
\begin_inset Formula \[
T=\frac{f(1.05\, ZUB-ZLB)}{\overset{m}{\underset{j=1}{\sum}}(G_{i})^{2}}\]

\end_inset


\end_layout

\begin_layout Standard
Velikost kroku se odvíjí od rozdílu mezi cenou nejlepšího nalezeného řešení
 a naposledy nalezenou dolní mezí.
 Je-li rozdíl malý, postupuje při modifikaci lagrangeovských multiplikátorů
 v jemných krocích.
 Je-li rozdíl velký, může se postupovat po větších krocích, ovšem pouze
 pokud je kvadratická norma subgradientu malá, tj.
 omezující podmínky jsou v plněny v dostatečné míře.
 Takto škálovatelná velikost kroku je motivována snahou o konvergenci proměnných
 
\begin_inset Formula $ZUB$
\end_inset

 a 
\begin_inset Formula $ZLB$
\end_inset

.
\end_layout

\begin_layout Standard
Počáteční hodnota proměnné 
\begin_inset Formula $f$
\end_inset

 je 2.
 Jestliže se proměnná 
\begin_inset Formula $LB$
\end_inset

 nezvýšila za posledních 30 iterací, hodnota proměnné 
\begin_inset Formula $f$
\end_inset

 je vydělena dvěma a postupuje se v jemnějších krocích
\begin_inset space ~
\end_inset

-
\begin_inset space ~
\end_inset

viz
\begin_inset space ~
\end_inset


\begin_inset CommandInset citation
LatexCommand cite
key "key-7"

\end_inset

.
\end_layout

\begin_layout Subsubsection*
Krok 8 Pokračování algoritmu, aktualizace lagrangeovských multiplikátorů
\end_layout

\begin_layout Standard
Jestliže bylo provedeno více než dané maximální množství iterací, Lagrangeovská
 heuristika končí.
 Jinou podmínkou pro ukončení může být pokles hodnoty proměnné 
\begin_inset Formula $f$
\end_inset

 pod 0,005, nebo překročení nějaké předem dané horní meze optimalizační
 funkce.
\end_layout

\begin_layout Standard
Lagrangeovské multiplikátory jsou aktualizovány podle vzorce
\begin_inset Newline newline
\end_inset


\begin_inset Formula $t_{i}=max(0,t_{i}+TG_{i}),i=1,...,m$
\end_inset

.
 Subgradient tedy Lagrangeovské multiplikátory směruje tak, aby vedly k
 volbě sloupců pokrývajících řádky neplnící omezující podmínky.
\end_layout

\begin_layout Standard
Pokračuje se krokem 2.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Genetický-algoritmus"

\end_inset

Genetický algoritmus
\end_layout

\begin_layout Standard
Genetický algoritmus představuje jednu z variant evolučních algoritmů.
\end_layout

\begin_layout Subsubsection
Obecně k evolučním algoritmům
\end_layout

\begin_layout Standard
Evoluční algoritmy jsou založeny na simulaci evoluce v přírodě a řídí se
 třemi základními principy, kterými se evoluce v přírodě vyznačuje.
\end_layout

\begin_layout Paragraph*
Reprezentace řešení problému.
\end_layout

\begin_layout Standard
Jednotlivá řešení problému (přípustná, ale ne nutně optimální) jsou reprezentová
na jako jedinci.
\end_layout

\begin_layout Paragraph*
Princip přirozeného výběru.
\end_layout

\begin_layout Standard
Přirozený výběr je proces, který vede k tomu, že někteří jedinci jsou schopni
 vyprodukovat více potomků než jiní jedinci.
 Pravděpodobnost předání genetického materiálu potomkovi je označována jako
 
\emph on
zdatnost
\emph default
.
 Zatímco v přírodě je obtížné určit, který jedinec je zdatnější, evoluční
 algoritmy často využívají deterministickou funkci zdatnosti, která přiřadí
 jedinci reálné číslo.
 Při určování zdatnosti nerozhodují jen vlastnosti jedince, ale i vlastnosti
 prostředí.
 Jedinec zdatný v jednom prostředí nemusí být zdatný v jiném prostředí.
\end_layout

\begin_layout Paragraph*
Princip variace a iterativního vyhodnocování.
\end_layout

\begin_layout Standard
V jedné iteraci (generaci jedinců) je na populaci aplikováno množství operací.
 Cílem těchto operací je zajistit drobné změny v populaci.
 Dvě nejpoužívanější operace jsou 
\emph on
křížení
\emph default
 a 
\emph on
mutace
\emph default
.
\end_layout

\begin_layout Subsubsection
Principy genetických algoritmů
\end_layout

\begin_layout Standard
Genetické algoritmy jsou nejpopulárnější variantou evolučních algoritmů.
 Genetické algoritmy pracují s obvykle ustálenou 
\emph on
populací
\emph default
.
 Populace se skládá z 
\emph on
jedinců
\emph default
 představujících řešení optimalizačního problému.
 Každý jedinec je reprezentován dvojicí 
\emph on
genotypu
\emph default
 
\emph on
g
\emph default
 (což je soubor genů daného jedince)
\emph on
 
\emph default
a
\emph on
 fenotypu f(g)
\emph default
.
 Fenotyp představuje kvalitativní vlastnosti jedince a funkce 
\begin_inset Formula $x(g)$
\end_inset

 mapuje genotyp na fenotyp.
\end_layout

\begin_layout Standard
Evoluční jevy (zdroje změn) genetické algoritmy reprezentují pomocí operátorů:
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
SELEKCE je výběr jedinců, kteří se stanou rodiči nového jedince.
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
KŘÍŽENÍ je proces, kdy část genů jednoho rodiče je nahrazena částí genů
 druhého rodiče
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
MUTACE reprezentuje náhodné jevy (např.
 působení radiace, změny podnebí trvalejšího charakteru aj.)
\end_layout

\begin_layout Standard
Selekce je řízena vyšetřením funkce zdatnosti 
\begin_inset Formula $\phi(g)$
\end_inset

 u každého genotypu.
 Funkce zdatnosti udává, nakolik je řešení reprezentované daným genotypem
 
\begin_inset Quotes eld
\end_inset

dobré
\begin_inset Quotes erd
\end_inset

 (analogie 
\begin_inset Quotes eld
\end_inset

životaschopnosti
\begin_inset Quotes erd
\end_inset

 ve skutečné přírodě).
 V přírodě mívají zdatnější jedinci více potomků, toto se v genetických
 algoritmech zajistí tak, že zdatnější jedinci budou vybíráni jako rodiče
 potomků častěji.
\end_layout

\begin_layout Standard
Genetický algoritmus probíhá v mnoha iteracích, součásti každé iterace jsou
 znázorněny na obrázku 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Obecné-schéma-genetických"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\noindent
\align center
\begin_inset Graphics
	filename ga1.png
	lyxscale 75
	scale 75

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Obecné-schéma-genetických"

\end_inset

Obecné schéma genetických algoritmů
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Genetický algoritmus, který je součástí hybridního algoritmu (GAH)
\end_layout

\begin_layout Standard
GAH začíná vygenerováním 
\emph on
počáteční populace, 
\emph default
podle předem daného rozložení pravděpodobnosti
\emph on
.
\end_layout

\begin_layout Standard
Počet jedinců se v průběhu algoritmu nemění, GAH je tedy genetický algoritmus
 s 
\emph on
ustálenou populací
\emph default
.
 V
\begin_inset space ~
\end_inset

průběhu každé iterace je vygenerován jeden nový jedinec, který nahradí nejméně
 zdatného jedince.
\end_layout

\begin_layout Standard
Při generování nového jedince se nejprve vyberou dva jedinci, kteří jsou
 kříženi.
 Nový jedinec je pak podroben mutaci.
 V GAH je pravděpodobnost mutace konstantní 
\begin_inset Formula $p_{m}$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Reprezentace jedince
\end_layout

\begin_layout Standard
Nejprve připomeňme, jak vypadá matice 
\begin_inset Formula $A$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $A=\left[\begin{array}{cccc}
0 & 0 & 1 & 0\\
1 & 1 & 0 & 1\\
1 & 0 & 0 & 1\\
1 & 0 & 1 & 1\end{array}\right]$
\end_inset


\end_layout

\begin_layout Standard
Označme množinu sloupců, která pokrývá daný řádek 
\begin_inset Formula $i$
\end_inset

 jako 
\emph on

\begin_inset Formula $N_{i}=\left\{ j\in N:a_{ij}=1\right\} $
\end_inset

.

\emph default
 Genotyp se skládá z m genů 
\begin_inset Formula $g^{(1)},...,g^{(m)}$
\end_inset

 takových, že 
\begin_inset Formula $g(i)\in N_{i}$
\end_inset

.
 Každý gen tedy obsahuje index sloupce, který je přiřazen k pokrytí řádku.
\end_layout

\begin_layout Standard
Z
\begin_inset space ~
\end_inset

matice nahlédneme, že:
\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{1}=\left\{ 3\right\} $
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{2}=\left\{ 1,2,4\right\} $
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{3}=\left\{ 1,4\right\} $
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{4}=\left\{ 1,3,4\right\} $
\end_inset


\end_layout

\begin_layout Standard
Například genotyp 
\begin_inset Formula $<3,1,1,1>$
\end_inset

 znamená, že jedinec představuje řešení, které se snaží pokrýt první řádek
 třetím sloupcem a zbývající řádky prvním sloupcem.
 Dále se bude tato skutečnost popisovat tak, že daný jedinec používá k pokrytí
 určité sloupce.
 Při této reprezentaci 
\begin_inset Formula $x(g)$
\end_inset

 mapuje genotyp 
\begin_inset Formula $g$
\end_inset

 na fenotyp 
\begin_inset Formula $x(g)\in\left\{ 0,1\right\} ^{n}$
\end_inset

, kde jedničky odpovídají přítomnosti sloupce v genech genotypu 
\begin_inset Formula $g$
\end_inset

.
 Například 
\begin_inset Formula $x(<3,1,1,1>)=(1,0,1,0)$
\end_inset

.
\end_layout

\begin_layout Standard
Protože geny mohou nabývat i jiných hodnot než jen 0 a 1 je tento genetický
 algoritmus 
\emph on
nebinárním genetickým algoritmem.
\end_layout

\begin_layout Standard
Kvůli efektivní implementaci algoritmu je potřeba rozšířit množinu operátorů
 ještě o procedury, které eliminují redundantní sloupce.
 Podrobnosti jsou uvedeny níže.
 Musíme totiž vzít v úvahu, že různé genotypy může mapovat funkce 
\begin_inset Formula $x(g)$
\end_inset

 na stejné fenotypy.
 Například 
\begin_inset Formula $x(<1,1,1,3>)=x(<1,3,3,3>)=(1,0,1,0)$
\end_inset

.
 V populaci však chceme mít pouze různé fenotypy.
\end_layout

\begin_layout Subsubsection
Selekce a funkce zdatnosti
\end_layout

\begin_layout Standard
Funkce zdatnosti je pro jedince s genotypem 
\begin_inset Formula $g$
\end_inset

 definována takto: 
\begin_inset Formula $\phi_{t}(g)=c[x(g_{l(t)})]-c[x(g)]+c_{n}$
\end_inset

, kde 
\begin_inset Formula $l(t)$
\end_inset

 je index jedince s nejvyšší cenou pokrytí v dané iteraci.
 Od ceny jedince s nejvyšší cenou pokrytí odečteme cenu pokrytí představovaného
 jedincem jehož zdatnost vyšetřujeme a přičteme cenu posledního (nejlevnějšího)
 sloupce.
\end_layout

\begin_layout Subsubsection
Schéma GAH
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1 Dokud není počáteční populace hotova:
\end_layout

\begin_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1.1 Generuj náhodný genotyp 
\begin_inset Formula $g$
\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1.2 Proveď proceduru Prime(
\begin_inset Formula $g$
\end_inset

)
\begin_inset space ~
\end_inset

-
\begin_inset space ~
\end_inset

viz
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Implementace-procedur-pro"

\end_inset

 a
\begin_inset space ~
\end_inset

přidej genotyp do populace
\end_layout

\end_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2 V každé iteraci proveď následující:
\end_layout

\begin_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2.1 Operátorem SELEKCE vyber dva genotypy 
\begin_inset Formula $g_{u}$
\end_inset

 a 
\begin_inset Formula $g_{v}$
\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2.2 Vytvoř nového jedince operátorem KŘÍŽENÍ
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2.3 Proveď MUTACI každého genu s pravděpodobností 
\begin_inset Formula $p_{m}$
\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2.4 Nechť 
\begin_inset Formula $g'$
\end_inset

 je nejlepším výsledkem procedur Greedy(
\begin_inset Formula $g$
\end_inset

) a DualGreedy(
\begin_inset Formula $g$
\end_inset

)
\begin_inset space ~
\end_inset

-
\begin_inset space ~
\end_inset

viz
\begin_inset space ~
\end_inset

 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Implementace-procedur-pro"

\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2.5 Nejsou-li v populaci jedinci s fenotypem 
\begin_inset Formula $x(g')$
\end_inset

, pak 
\begin_inset Formula $g'$
\end_inset

 nahradí nejméně zdatného jedince, jinak nejméně zdatného jedince nahradí
\begin_inset space ~
\end_inset


\begin_inset Formula $g$
\end_inset


\end_layout

\end_deeper
\begin_layout Subsubsection
Implementace operátorů
\end_layout

\begin_layout Paragraph*
SELEKCE
\end_layout

\begin_layout Standard
Operátor implementuje proporcionální schéma selekce, pravděpodobnost výběru
 k-tého jedince je dána následujícím vztahem:
\end_layout

\begin_layout Standard
\begin_inset Formula \[
P(k)=\frac{\phi_{t}(g_{k})}{\sum_{l=1}^{s}\phi_{t}(g_{l(t)})}\]

\end_inset


\end_layout

\begin_layout Standard
Pravděpodobnost výběru zdatnějšího jedince je větší než pravděpodobnost
 výběru jedince méně zdatného.
 Tím dosáhneme toho, že zdatnější jedinci budou mít více potomků.
\end_layout

\begin_layout Paragraph*
KŘÍŽENÍ
\end_layout

\begin_layout Standard
V tomto případě se jedná o tzv.
 LP-křížení, tedy křížení při kterém je řešen LP problém.
 Operátor je implementován tak, aby našel nejlepší možnou kombinaci rodičovských
 genotypů 
\begin_inset Formula $g_{u}$
\end_inset

 a 
\begin_inset Formula $g_{v}$
\end_inset

, pokud je to možné bez příliš náročných výpočtů.
\end_layout

\begin_layout Standard
Uvažujme problém optimálního křížení 
\begin_inset Formula $P_{oc}$
\end_inset

, což je vlastně redukovaná verze problému počátečního pokrytí množiny,
 kde pokrývající podmnožiny jsou omezeny množinou indexů 
\begin_inset Formula $N'=\left\{ j:x(g_{u})_{j}=1\right\} \cup\left\{ j:x(g_{v})_{j}=1\right\} $
\end_inset

.
 
\end_layout

\begin_layout Standard
Srozumitelněji řečeno, pro pokrytí množiny řádků máme k dispozici sloupce,
 které používají k pokrytí křížení jedinci.
\end_layout

\begin_layout Standard
Nejprve je na 
\begin_inset Formula $P_{oc}$
\end_inset

 aplikována jednoduchá redukce.
 Označme 
\begin_inset Formula $S=\left\{ i\in M:\left|N_{i}\cap N'\right|=1\right\} $
\end_inset

.
 Každý řádek 
\begin_inset Formula $i\in S$
\end_inset

 může být pokryt právě jedním sloupcem 
\begin_inset Formula $j(i)$
\end_inset

.
 Pojmenujme
\begin_inset Newline newline
\end_inset


\begin_inset Formula $Q=\left\{ j:j(i),i\in S\right\} $
\end_inset

 množinu 
\begin_inset Quotes eld
\end_inset

upevněných
\begin_inset Quotes erd
\end_inset

 sloupců.
 Pak pro každý řádek 
\begin_inset Formula $i\in\cup_{j\in Q}M_{j}$
\end_inset

 je přiřazen jeden ze sloupců, který pokrývá gen 
\begin_inset Formula $g^{(i)}$
\end_inset

.
 Tyto geny považujme také za 
\begin_inset Quotes eld
\end_inset

upevněné
\begin_inset Quotes erd
\end_inset

.
\end_layout

\begin_layout Standard
Srozumitelněji řečeno, při dalším výpočtu nebudeme uvažovat řádky, které
 je možné pokrýt jen jedním sloupcem, ani sloupce, které tyto řádky pokrývají.
\end_layout

\begin_layout Standard
Jako výsledek této redukce dostaneme podproblém
\begin_inset space ~
\end_inset


\begin_inset Formula $P_{r}$
\end_inset

, který se skládá ze sloupců a řádků, které nebyly 
\begin_inset Quotes eld
\end_inset

upevněny
\begin_inset Quotes erd
\end_inset

.
 K vyřešení lineární relaxace podproblému
\begin_inset space ~
\end_inset


\begin_inset Formula $P_{r}$
\end_inset

 se použije simplexová metoda - viz např.
\begin_inset space ~
\end_inset


\begin_inset CommandInset citation
LatexCommand cite
key "key-10,key-8"

\end_inset

.
 Jestliže řešení
\begin_inset space ~
\end_inset


\begin_inset Formula $\mathbf{x}'$
\end_inset

, které poskytne simplexová metoda je celočíselné, pak je toto řešení použito
 k doplnění genotypu
\begin_inset space ~
\end_inset


\begin_inset Formula $g$
\end_inset

.
\end_layout

\begin_layout Standard
Aby se eliminovaly zdlouhavé výpočty, simplexovou metodu nespouštíme v případě,
 že počet řádků redukovaného problému přesahuje určitou předem danou hranici,
 nebo je překročen určitý počet iterací simplexové metody (implementace
 simplexové metody tedy musí podporovat možnost zastavení po určitém počtu
 iterací).
 V případě neceločíselného řešení
\begin_inset space ~
\end_inset


\begin_inset Formula $\mathbf{x}'$
\end_inset

 operátor KŘÍŽENÍ vrátí nezměněný genotyp
\begin_inset space ~
\end_inset


\begin_inset Formula $g_{u}$
\end_inset

.
\end_layout

\begin_layout Standard
Příklad křížení:
\end_layout

\begin_layout Standard
\begin_inset Formula $A=\left[\begin{array}{cccc}
0 & 0 & 1 & 0\\
1 & 1 & 0 & 1\\
1 & 0 & 0 & 1\\
1 & 0 & 1 & 1\end{array}\right]$
\end_inset


\end_layout

\begin_layout Standard
Mějme genotypy 
\begin_inset Formula $<3,1,1,1>$
\end_inset


\begin_inset space ~
\end_inset

a
\begin_inset space ~
\end_inset


\begin_inset Formula $<3,4,4,4>$
\end_inset

.
 Pak 
\begin_inset Formula $N'=\left\{ 3,1\right\} \cup\left\{ 3,4\right\} =\left\{ 1,3,4\right\} $
\end_inset

.
\end_layout

\begin_layout Standard
Z
\begin_inset space ~
\end_inset

matice nahlédneme, že:
\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{1}=\left\{ 3\right\} $
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{2}=\left\{ 1,2,4\right\} $
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{3}=\left\{ 1,4\right\} $
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $N_{4}=\left\{ 1,3,4\right\} $
\end_inset


\end_layout

\begin_layout Standard
\noindent
\align left
Určíme, že:
\begin_inset Newline newline
\end_inset

 
\begin_inset Formula $\left|N_{1}\cap N'\right|=1$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $\left|N_{2,3}\cap N'\right|=2$
\end_inset


\begin_inset Newline newline
\end_inset

 
\begin_inset Formula $\left|N_{4}\cap N'\right|=3$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $S=\left\{ 1\right\} $
\end_inset

 
\end_layout

\begin_layout Standard
Řádek 1 může být pokryt jedině sloupcem 3.
 Dostaneme tedy podproblém s maticí 
\begin_inset Formula $A^{1}$
\end_inset

:
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\begin_inset Formula $A^{1}=\left[\begin{array}{ccc}
1 & 1 & 1\\
1 & 0 & 1\end{array}\right]$
\end_inset


\end_layout

\begin_layout Standard
Simplexová metoda pokryje zbývající řádky třetím sloupcem matice 
\begin_inset Formula $A^{1}$
\end_inset

 (připomeňme, že sloupce jsou seřazeny do posloupnosti s nerostoucí cenou).
 V původní matici 
\begin_inset Formula $A$
\end_inset

 to byl sloupec 4.
 Výsledný fenotyp bude 
\begin_inset Formula $x(g)=(0,0,1,1)$
\end_inset

.
 Fenotyp je nutné převést zpět na genotyp.
 Řádky samozřejmě pokrýváme pouze sloupci, které jsou přítomny ve výsledném
 fenotypu.
 Nový jedinec bude mít genotyp 
\begin_inset Formula $<3,4,4,3>$
\end_inset

nebo 
\begin_inset Formula $<3,4,4,4>$
\end_inset

.
\end_layout

\begin_layout Paragraph*
MUTACE
\end_layout

\begin_layout Standard
Pokud má být gen 
\begin_inset Formula $g^{(i)}$
\end_inset

 daného jedince mutován, pak pravděpodobnost, že mu bude přiřazen sloupec
 
\begin_inset Formula $j\in N_{i}$
\end_inset

 je dána vztahem: 
\begin_inset Formula $p_{i}(j)=\frac{\frac{1}{c_{j}}}{\sum_{k\in N_{i}}\frac{1}{c_{k}}}$
\end_inset


\end_layout

\begin_layout Subsubsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Implementace-procedur-pro"

\end_inset

Implementace procedur pro odstranění redundantních sloupců
\end_layout

\begin_layout Paragraph
Greedy(Genotyp g).
\end_layout

\begin_layout Standard
Vyřeší problém pokrytí hladovým algoritmem popsaným v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Hladový-algoritmus-dle"

\end_inset

.
\end_layout

\begin_layout Paragraph*
DualGreedy(Genotyp g).
\end_layout

\begin_layout Standard
Kombinace postupného odstraňování sloupců a jejich adaptivního oceňování.
\end_layout

\begin_layout Standard
Označme množinu sloupců, která pokrývá daný řádek 
\begin_inset Formula $i$
\end_inset

 jako 
\emph on

\begin_inset Formula $N_{i}=\left\{ j\in N:a_{ij}=1\right\} $
\end_inset


\emph default
a dále 
\begin_inset Formula $N'=\{j\in N:x(g)_{j}=1\}$
\end_inset

, množinu indexů sloupců, které jedinec používá k pokrytí.
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1 Nastav 
\begin_inset Formula $N_{i}'=N_{i}\cap N',i=1,...,m;M'=M,J'=N^{'},J=\textrm{Ø}$
\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2 Dokud 
\begin_inset Formula $J'\neq\textrm{Ø}$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2.1 Existuje-li 
\begin_inset Formula $i\in M'$
\end_inset

 takové, že 
\begin_inset Formula $\left|N'_{i}\right|=1$
\end_inset

, pak 
\begin_inset Formula $J=J\cup\left\{ j\right\} ,M=M'\setminus M_{j},j\in N'_{i}$
\end_inset

, jinak vyber 
\begin_inset Formula $j\in J'$
\end_inset

 takové, že 
\begin_inset Formula $j=argmax_{k\in J'}\frac{c_{k}}{\left|M_{k}\cap M'\right|}$
\end_inset


\begin_inset Newline newline
\end_inset

Existuje-li dosud nepokrytý řádek, který je pokryt jen jedním sloupcem,
 pak tento sloupec použij k jeho pokrytí.
 Jinak vyber z
\begin_inset space ~
\end_inset

dostupných sloupců takový, že poměr uvedený je maximální.
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2.2 Nastav 
\begin_inset Formula $J'=J'\setminus\left\{ j\right\} ,N'_{i}=N'_{i}\setminus\left\{ j\right\} $
\end_inset

pro všechna 
\begin_inset Formula $i\in M_{j}$
\end_inset


\begin_inset Newline newline
\end_inset

Použitý sloupec odeber z množiny dostupných sloupců.
\end_layout

\end_deeper
\begin_layout Paragraph
Prime(Genotyp g).
\end_layout

\begin_layout Standard
Jednoduché postupné odstranění sloupců se vzrůstajícími indexy (připomeňme,
 že sloupce jsou seřazeny do posloupnosti s nerostoucí cenou).
 Sloupec je odstraněn, pokud zbývající řešení zůstává pokrytím.
 Výstupem je pokrytí bez redundantních sloupců.
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Výčet-L-tříd-(LCE"

\end_inset

Výčet L-tříd 
\end_layout

\begin_layout Standard
Pro výčet L-tříd se bude používat zkratka LCE.
\end_layout

\begin_layout Subsubsection*
Principy
\end_layout

\begin_layout Standard
Jedním z možných přístupů k řešení LP problémů je použití zvláštních 
\emph on
dělení
\emph default
 prostoru 
\begin_inset Formula $R^{n}$
\end_inset

.
 Jedním z takových dělení je L-dělení, které rozdělí body v prostoru do
 L-tříd 
\begin_inset CommandInset citation
LatexCommand cite
key "key-1"

\end_inset

.
\end_layout

\begin_layout Standard
Uvažujme, že 
\begin_inset Formula $\Omega=\left\{ \mathbf{x}\in R^{n}:A\mathbf{x}\geq\mathbf{e},0\leq\mathbf{x}\leq\mathbf{e}\right\} $
\end_inset

 je relaxační množina problému pokrytí.
 Je to vlastně mnohostěn v prostoru 
\begin_inset Formula $R^{n}$
\end_inset

.
 Výčet L-tříd pracuje následujícím způsobem: Mnohostěn 
\begin_inset Formula $\Omega$
\end_inset

 může být rozdělen na 
\emph on
lexikograficky uspořádané
\emph default
 podmnožiny a optimální řešení může být nalezeno ověřením některých z těchto
 podmnožin.
\end_layout

\begin_layout Standard
Pro vyjádření lexikografického uspořádání budou v následujícím textu použity
 symboly 
\begin_inset Formula $\prec\preceq\succeq\succ$
\end_inset

.
 Například platí, že 
\begin_inset Formula $(0,0,0)\prec(0,0,1)\prec(0,1,0)\prec(0,1,1)$
\end_inset

.
\end_layout

\begin_layout Standard
Jak L-dělení rozděluje body do L-tříd? Dva body 
\begin_inset Formula $\mathbf{x},\mathbf{y}\in R^{n}$
\end_inset

 náleží do stejné třídy L-dělení právě tehdy, když neexistuje žádný celočíselný
 vektor 
\begin_inset Formula $\mathbf{z}$
\end_inset

 takový, že 
\begin_inset Formula $\mathbf{x}\succeq\mathbf{z}\succeq\mathbf{y}$
\end_inset

.
 
\end_layout

\begin_layout Standard
Každý bod 
\begin_inset Formula $\mathbf{z}\in Z^{n}$
\end_inset

, tedy každý bod s celočíselnými souřadnicemi formuje oddělenou třídu L-dělení.
 Ostatní třídy, které obsahují pouze neceločíselné body jsou třídy 
\emph on
zlomkové
\emph default
.
\end_layout

\begin_layout Standard
L-dělení množiny 
\begin_inset Formula $X\in R^{n}$
\end_inset

 indukuje množinu L-tříd, která bude dále označována jako 
\begin_inset Formula $X/L$
\end_inset

.
 Tato množina má zajímavé vlastnosti.
\end_layout

\begin_layout Enumerate
Je-li množina 
\begin_inset Formula $X$
\end_inset

 ohraničená, pak je množina 
\begin_inset Formula $X/L$
\end_inset

 konečná.
\end_layout

\begin_layout Enumerate
Pro 
\begin_inset Formula $X/L$
\end_inset

 může být definováno lineární uspořádání: pro neprázdné 
\begin_inset Formula $V^{'},V^{''}\in X/L$
\end_inset

 můžeme psát, že 
\begin_inset Formula $V^{'}\succ V^{''}$
\end_inset

, právě tehdy když pro libovolná 
\begin_inset Formula $\mathbf{x}'\in V'$
\end_inset

 a 
\begin_inset Formula $\mathbf{x}''\in V''$
\end_inset

 platí, že 
\begin_inset Formula $\mathbf{x}'\succ\mathbf{x}''$
\end_inset

.
\end_layout

\begin_layout Standard
Nechť 
\begin_inset Formula $\Omega_{0}$
\end_inset

 je množina optimálních řešení pro problém pokrytí.
 Algoritmus LCE generuje sekvenci aktuálních bodů 
\begin_inset Formula $\sigma=\left\{ \mathbf{x}\left(t\right)\right\} $
\end_inset

 z množiny 
\begin_inset Formula $\Omega$
\end_inset

 a 
\begin_inset Formula $t=1,...,\theta_{L}$
\end_inset

.
 Sekvence bodů má následující vlastnosti:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\mathbf{x}(t)\prec\mathbf{x}(t+1)$
\end_inset

pro 
\begin_inset Formula $t=1,...,\theta_{L}-1$
\end_inset

, tedy každý další bod v sekvenci je lexikograficky větší než bod předchozí.
\end_layout

\begin_layout Enumerate
Body v sekvenci patří do rozdílných L-tříd.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\sigma$
\end_inset

 obsahuje celočíselnou pod-sekvenci 
\begin_inset Formula $\sigma'=\left\{ \mathbf{x}(t_{k})\right\} ,k=1,...,q$
\end_inset

 takovou, že 
\begin_inset Formula $z*\in\sigma'$
\end_inset

 a když 
\begin_inset Formula $t>t_{k}$
\end_inset

, tak (
\begin_inset Formula $c,\mathbf{x}(t))<(c,\mathbf{x}(t_{k}))$
\end_inset

.
\end_layout

\begin_layout Standard
Z bodu jedna lze odvodit, že mohutnost sekvence 
\begin_inset Formula $\sigma$
\end_inset

 je menší nebo stejná jako mohutnost 
\begin_inset Formula $X/L$
\end_inset

.
 Jednotlivé body sekvence 
\emph on

\begin_inset Formula $\mathbf{x}(t)$
\end_inset

 
\emph default
se získají řešením 
\emph on
speciálně formulovaných LP problémů
\emph default
.
 Tak je řešení CLP problému, který patří do skupiny NP těžkých problémů
 převedeno na řešení sekvence polynomiálních problémů.
\end_layout

\begin_layout Standard
Cílem algoritmu LCE je najít celočíselné optimum v množině 
\begin_inset Formula $\Omega/L=\left\{ V_{1},...,V_{p}\right\} $
\end_inset

.
 Není nutné navštívit všechny L-třídy, dodatečná podmínka, jako podmínka
\begin_inset Newline newline
\end_inset


\begin_inset Formula $(c,\mathbf{x})\leq(c,\xi)-1$
\end_inset

,kde 
\begin_inset Formula $\xi=\mathbf{x}(t_{k})$
\end_inset

 je dosud nejlepší nalezené 
\emph on
celočíselné
\emph default
 řešení, může vyloučit některé nepotřebné L-třídy.
 Hodnota optimalizační funkce 
\begin_inset Formula $r=(c,\xi)$
\end_inset

 se označuje jako 
\emph on
záznam
\emph default
 aktuálního kroku.
 Tato hodnota může být při inicializaci algoritmu nastavena na 
\begin_inset Formula $\infty$
\end_inset

, případně může být její počáteční hodnota určena nějakým aproximativním
 algoritmem (nebo algoritmy).
 V průběhu algoritmu je pak postupně snižována.
\end_layout

\begin_layout Standard
Aproximativní algoritmy spuštěné před algoritmem LCE mají za cíl snížit
 počáteční hodnotu záznamu co nejvíce je to možné, aby při výčtu L-tříd
 bylo co nejvíce těchto L-tříd vyloučeno podmínkou
\begin_inset space ~
\end_inset


\begin_inset Formula $(c,\mathbf{x})\leq(c,\xi)-1$
\end_inset

.
\end_layout

\begin_layout Subsubsection*
\begin_inset Newpage newpage
\end_inset

Obecné schéma algoritmu LCE
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

0 
\begin_inset CommandInset label
LatexCommand label
name "lyx:Krok0:-Najdi-nějaké"

\end_inset

Najdi nějaké přibližné řešení 
\begin_inset Formula $\mathbf{\xi}^{0}\in Z^{n}$
\end_inset


\end_layout

\begin_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

0.1 Najdi 
\begin_inset Formula $\mathbf{x}'$
\end_inset

 jako 
\begin_inset Formula $lexmin(\Omega)$
\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

0.2 Nastav 
\begin_inset Formula $r=min\left\{ (c,\mathbf{x}'),(c,\mathbf{\xi}^{0})\right\} $
\end_inset


\begin_inset Newline newline
\end_inset

Záznam 
\begin_inset Formula $r$
\end_inset

 nastav na na menší hodnotu z ceny přibližného řešení a ceny řešení představovan
ého lexikografickým minimem množiny 
\begin_inset Formula $\Omega$
\end_inset

.
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

0.3 Nastav 
\begin_inset Formula $p=max\left\{ j:x'_{j}=1,j=1,...,n-1\right\} $
\end_inset


\end_layout

\end_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1 Najdi 
\begin_inset Formula $\varphi=max\left\{ j:x'_{j}=0,j=1,...,p-1\right\} $
\end_inset


\end_layout

\begin_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1.1 Jestliže takové 
\begin_inset Formula $\varphi$
\end_inset

 neexistuje, výčet L-tříd je ukončen.
\end_layout

\end_deeper
\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2 Nastav 
\begin_inset Formula $\mathbf{x}''=\mathbf{x}'$
\end_inset

.
 Najdi další L-třídu řešením následujícího problému:
\begin_inset Newline newline
\end_inset

 
\begin_inset Formula $\mathbf{x}'=lexmin\left\{ \mathbf{x}\in\Omega:(c,\mathbf{x})\leq r-1,x_{1}=x_{1}'',...,x_{\varphi-1}=x''_{\varphi-1},x_{\varphi}=1\right\} $
\end_inset


\begin_inset Newline newline
\end_inset

Podrobnosti k tomuto kroku jsou podrobně rozpracovány v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Ke-krokům-algoritmu"

\end_inset

.
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

3 Krok 2 může poskytnout následující výsledky:
\begin_inset Newline newline
\end_inset

1.
 Nalezena celočíselná L-třída:
\begin_inset Newline newline
\end_inset

Nastav 
\begin_inset Formula $p=max\{j:x_{j}'=1,j\leq n-1\}$
\end_inset

.
 Pokračuj
\begin_inset space ~
\end_inset

krokem
\begin_inset space ~
\end_inset

1.
\begin_inset Newline newline
\end_inset

2.
 Nalezena zlomková L-třída.
\begin_inset Newline newline
\end_inset

Nastav 
\begin_inset Formula $\varphi=min\{j:x_{j}'\neq\left\lfloor x_{j}'\right\rfloor ,j=1,...,n\}$
\end_inset

.
 Pokračuj
\begin_inset space ~
\end_inset

krokem
\begin_inset space ~
\end_inset

2.
\begin_inset Newline newline
\end_inset

3.
 Nenalezena žádná L-třída:
\begin_inset Newline newline
\end_inset

Nastav 
\begin_inset Formula $p=\varphi$
\end_inset

.
 Pokračuj
\begin_inset space ~
\end_inset

krokem
\begin_inset space ~
\end_inset

2.
\begin_inset Newline newline
\end_inset

4.
 Ukonči algoritmus.
\begin_inset Newline newline
\end_inset

Při tomto výsledku je algoritmus ukončen.
 Řešením problému pokrytí je naposledy nalezená celočíselná L-třída.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Ke-krokům-algoritmu"

\end_inset

Ke krokům algoritmu LCE
\end_layout

\begin_layout Standard
Na úvod je třeba připomenout, že algoritmus LCE pracuje s 
\emph on
relaxací
\emph default
 původního CLP problému.
 To znamená, že původní podmínka pro vektor 
\begin_inset Formula $\mathbf{x}$
\end_inset

 je 
\emph on
oslabena 
\emph default
podle následujícího vzorce: 
\begin_inset Formula \begin{equation}
min\left\{ \mathbf{c}\mathbf{x\,}:A\mathbf{x}\geq\mathbf{e},\, x_{1...n}\in<0,1>\right\} \label{eq:relaxlinpro}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Oslabení původní podmínky vede k přechodu od CLP problému k LP problému.
\end_layout

\begin_layout Subsubsection
Lexikografické minimum relaxační množiny
\end_layout

\begin_layout Standard
\begin_inset Formula $\mathbf{x}=lexmin(\Omega):\, A\mathbf{x}\geq1,\, x_{n}\in<0,1>$
\end_inset


\end_layout

\begin_layout Standard
Procházejí se jednotlivé sloupce od prvního k poslednímu (připomeňme, že
 jsou seřazeny do posloupnosti s neklesající cenou).
 Sloupec je z pokrytí vyjmut, jestliže zbývající sloupce stále tvoří pokrytí.
 Lexikografické minimum je vždy celočíselné 
\begin_inset CommandInset citation
LatexCommand cite
key "key-1"

\end_inset

.
\end_layout

\begin_layout Subsubsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Krok-2-algoritmu"

\end_inset

Krok 2 algoritmu LCE
\end_layout

\begin_layout Standard
V kroku 2 se řeší následující problém:
\end_layout

\begin_layout Standard
\begin_inset Formula \begin{equation}
\mathbf{x}'=lexmin\left\{ \mathbf{x}\in\Omega:(c,\mathbf{x})\leq r-1,x_{1}=x_{1}'',...,x_{\varphi-1}=x''_{\varphi-1},x_{\varphi}=1\right\} \label{eq:lce2sp}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Hledání lexikografického minima představuje sekvenci řešení LP problémů
 s postupným zmrazováním jednotlivých proměnných.
 Zde jsou symbolicky naznačeny první tři LP problémy ze sekvence:
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="1" columns="3">
<features>
<column alignment="left" valignment="top" width="5cm">
<column alignment="left" valignment="top" width="5cm">
<column alignment="left" valignment="top" width="5cm">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $k_{1}=min\, x_{1}$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $A\mathbf{x}\geq1$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}\leq r-1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $k_{2}=min\, x_{2}$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $A\mathbf{x}\geq1$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}\leq r-1$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $x_{1}=k_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $k_{3}=min\, x_{3}$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $A\mathbf{x}\geq1$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}\leq r-1$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $x_{1}=k_{1}$
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $x_{2}=k_{2}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Na vstupu máme vektor 
\begin_inset Formula $\mathbf{x}$
\end_inset

 a proměnné 
\begin_inset Formula $\varphi$
\end_inset

 a 
\begin_inset Formula $p$
\end_inset

 a záznam 
\begin_inset Formula $r$
\end_inset

.
 Vektor 
\begin_inset Formula $\mathbf{x}$
\end_inset

 můžeme rozdělit na upevněnou část a volnou část, tak jako je to naznačeno
 v následujícím předpisu.
 Volná část vektoru 
\begin_inset Formula $\mathbf{x}$
\end_inset

 je naznačena otazníky.
 V upevněné části se mohou vyskytovat pouze celá čísla, což lze snadno odvodit
 z kroku
\begin_inset space ~
\end_inset

3 algoritmu LCE.
\end_layout

\begin_layout Standard
\begin_inset Formula \[
\mathbf{x}=(x_{1},x_{2},x_{3},...,x_{\varphi-1},\mathbf{1},?,?,?,..,?)\]

\end_inset


\end_layout

\begin_layout Paragraph*
Kontrola upevněné části.
\end_layout

\begin_layout Standard
Nejprve zkontrolujeme upevněnou část - představuje sloupce, o kterých jistě
 víme, že budou či nebudou součástí pokrytí.
 Jestliže pro cenu 
\begin_inset Formula $c(f)=(c_{1}x_{1}+c_{2}x_{2}+...+c_{\varphi}x_{\varphi})$
\end_inset

 platí 
\begin_inset Formula $c(f)>r-1$
\end_inset

, pak LP problém jistě nemá řešení a pokračuje se heuristikou pro testování
 skupin L-tříd popsanou v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Heuristika-pro-testování"

\end_inset

.
\end_layout

\begin_layout Standard
Jestliže upevněné sloupce představují pokrytí (nerovnosti jsou již splněny),
 pak řešením problému je vektor
\begin_inset Newline newline
\end_inset


\begin_inset Formula $\mathbf{x}=(x_{1},x_{2},x_{3},...,x_{\varphi-1},\mathbf{1},0,0,0,..,0)$
\end_inset

, který je zřejmě celočíselný a lexikograficky minimální.
 Byla tedy nalezena celočíselná L-třída, která je zapamatována.
 Aktualizuje se záznam: 
\begin_inset Formula $r=c(\mathbf{x})$
\end_inset

.
 Krok 2 je ukončen a vrátí výsledek 
\emph on
Nalezena celočíselná L-třída
\emph default
.
\end_layout

\begin_layout Standard
Při provádění dalších operací se pracuje pouze s 
\emph on
podproblémem
\emph default
, který vznikne odstraněním sloupců upevněné části a řádků pokrytých těmito
 sloupci.
\end_layout

\begin_layout Paragraph*
\begin_inset CommandInset label
LatexCommand label
name "par:Lagrangeovská-heuristika."

\end_inset

Lagrangeovská heuristika.
\end_layout

\begin_layout Standard
Pokus o nalezení celočíselné L-třídy se provede aplikací lagrangeovské heuristik
y popsané v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Lagrangeovská-heuristika-(LH)"

\end_inset

 na podproblém.
\end_layout

\begin_layout Standard
Jestliže aplikací lagrangeovské heuristiky obdržíme řešení 
\begin_inset Formula $\mathbf{x},$
\end_inset

 pro jehož cenu platí 
\begin_inset Formula $c(\mathbf{x})+c(f)<=r-1$
\end_inset

, pak se tato cena stane 
\emph on
horní mezí
\emph default
 pro simplexovou metodu.
 Rovněž obdržíme 
\emph on
dolní mez
\emph default
 
\begin_inset Formula $LB$
\end_inset

 ceny řešení, kterou porovnáme se záznamem.
 Simplexová metoda se nespustí, je-li 
\begin_inset Formula $LB+c(f)>r-1$
\end_inset

.
 V tom případě se pokračuje heuristikou pro testování skupin L-tříd.
\end_layout

\begin_layout Paragraph*
Simplexová metoda.
\end_layout

\begin_layout Standard
Další pokus o nalezení L-třídy se provede řešením výše uvedené sekvence
 LP problémů.
\end_layout

\begin_layout Standard
Nalezne-li simplexová metoda celočíselné řešení 
\begin_inset Formula $\mathbf{x}$
\end_inset

, je nalezena nová celočíselná L-třída a aktualizován záznam: 
\begin_inset Formula $r=c(f)+c(\mathbf{x})$
\end_inset

.
 Krok
\begin_inset space ~
\end_inset

2 je ukončen a vrátí výsledek 
\emph on
Nalezena celočíselná L-třída
\emph default
.
 Není-li nalezené řešení celočíselné, krok 2 je rovněž ukončen a vrátí výsledek
 
\emph on
Nalezena zlomková L-třída
\emph default
.
\end_layout

\begin_layout Standard
Není-li nalezena žádná L-třída a je-li 
\begin_inset Formula $\varphi=1$
\end_inset

, krok 2 vrátí výsledek 
\emph on
Ukonči algoritmus
\emph default
.
 Jinak se pokračuje heuristikou pro testování skupin L-tříd.
\end_layout

\begin_layout Subsubsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Heuristika-pro-testování"

\end_inset

Heuristika pro testování skupin L-tříd
\end_layout

\begin_layout Standard
To, že není nalezeno řešení problému se stává poměrně často.
 Úspory výpočetního výkonu se dosahuje heuristikou pro testování skupin
 L-tříd.
 Řešíme následující problém:
\end_layout

\begin_layout Standard
\begin_inset Formula \begin{alignat*}{1}
 & \mathbf{x}'=lexmin\left\{ \mathbf{x}\in\Omega:(c,\mathbf{x})\leq r-1,x_{1}=x_{1}'',...,x_{\varphi-1}=x''_{\varphi-1},x_{\varphi}=1\right\} \\
 & \sum_{j=j_{0}}^{j_{o}+n_{o}+1}x_{j}\geq1\end{alignat*}

\end_inset


\end_layout

\begin_layout Standard
Pro proměnné 
\begin_inset Formula $j_{0}$
\end_inset

 a 
\begin_inset Formula $n_{0}$
\end_inset

 platí: 
\begin_inset Formula $j_{0}=min\{j<\varphi:x_{j}=x_{j+1}=...=x_{j_{o}+n_{o}-1}=0\}$
\end_inset

 a neexistuje 
\begin_inset Formula $k$
\end_inset

 takové, že 
\begin_inset Formula $k\in<j+n_{o},\varphi-1>$
\end_inset


\end_layout

\begin_layout Standard
Na vstupu máme vektor 
\begin_inset Formula $\mathbf{x}$
\end_inset

 a proměnné 
\begin_inset Formula $j_{0}$
\end_inset

,
\begin_inset Formula $n_{0}$
\end_inset

,
\begin_inset Formula $\varphi$
\end_inset

.
 Jestliže hodnoty proměnných 
\begin_inset Formula $j_{0}$
\end_inset

 a 
\begin_inset Formula $n_{0}$
\end_inset

 odpovídající uvedeným podmínkám nelze najít, krok 2 vrátí výsledek 
\emph on
Nenalezena žádná L-třída
\emph default
.
\end_layout

\begin_layout Standard
Vektor 
\begin_inset Formula $\mathbf{x}$
\end_inset

 lze rozdělit na tři části.
 Na upevněnou část
\begin_inset Formula $(x_{1},...x_{j_{0}-1})$
\end_inset

, část kde musí být alespoň jedna jednička 
\begin_inset Formula $(x_{j_{0}},...,x_{j_{0}+n_{0}-1})$
\end_inset

 (označeno tučnými nulami) a volnou část (označeno otazníky).
\end_layout

\begin_layout Standard
\begin_inset Formula \[
\mathbf{x}=(x_{1},x_{2},x_{3},...,x_{j_{0}-1},\mathbf{0},\mathbf{0},...,\mathbf{0},\mathbf{0},?,?,...,?)\]

\end_inset


\end_layout

\begin_layout Paragraph*
Kontrola upevněné části.
\end_layout

\begin_layout Standard
Nejprve zkontrolujeme upevněnou část - představuje sloupce, o kterých jistě
 víme, že budou či nebudou součástí pokrytí.
 Jestliže pro cenu upevněné části 
\begin_inset Formula $c(f)=(c_{1}x_{1}+c_{2}x_{2}+...+c_{j_{0}-1}x_{j_{0}-1})$
\end_inset

 platí 
\begin_inset Formula $c(f)>r-1$
\end_inset

, pak problém jistě nemá řešení a krok 2 vrátí výsledek 
\emph on
Nenalezena žádná L-Třída
\emph default
.
\end_layout

\begin_layout Standard
Jestliže upevněné sloupce představují pokrytí, pak řešením problému je vektor
\begin_inset Newline newline
\end_inset


\begin_inset Formula $\mathbf{x}=(x_{1},x_{2},x_{3},...,x_{j_{0}-1},\mathbf{0},\mathbf{0},...,\mathbf{0},\mathbf{1},0,...,0)$
\end_inset

, který je zřejmě celočíselný.
 Byla tedy nalezena celočíselná L-třída, která je zapamatována.
 Aktualizuje se záznam: 
\begin_inset Formula $r=c(\mathbf{x})+c_{j_{0}+n_{0}-1}$
\end_inset

.
 Krok 2 je ukončen a vrátí výsledek 
\emph on
Nalezena celočíselná L-třída
\emph default
.
\end_layout

\begin_layout Standard
Při provádění dalších operací se pracuje pouze s 
\emph on
podproblémem
\emph default
, který vznikne odstraněním sloupců upevněné části a řádků pokrytých těmito
 sloupci.
\end_layout

\begin_layout Paragraph*
Lagrangeovská heuristika.
\end_layout

\begin_layout Standard
Pokus o nalezení celočíselné L-třídy se provede aplikací lagrangeovské heuristik
y popsané v sekci 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Lagrangeovská-heuristika-(LH)"

\end_inset

 na podproblém.
\end_layout

\begin_layout Standard
Jestliže aplikací lagrangeovské heuristiky obdržíme řešení 
\begin_inset Formula $\mathbf{x},$
\end_inset

 pro jehož cenu platí 
\begin_inset Formula $c(\mathbf{x})+c(f)<=r-1$
\end_inset

, pak se tato cena stane 
\emph on
horní mezí 
\emph default
pro simplexovou metodu.
 Rovněž obdržíme 
\emph on
dolní mez
\emph default
 
\begin_inset Formula $LB$
\end_inset

 ceny řešení, kterou porovnáme se záznamem.
 Simplexová metoda se nespustí, je-li 
\begin_inset Formula $LB>r-1$
\end_inset

.
\end_layout

\begin_layout Paragraph*
Simplexová metoda.
\end_layout

\begin_layout Standard
Další pokus o nalezení L-třídy se provede řešením výše uvedené sekvence
 LP problémů.
\end_layout

\begin_layout Standard
Nalezne-li simplexová metoda celočíselné řešení 
\begin_inset Formula $\mathbf{x}$
\end_inset

, je nalezena nová celočíselná L-třída a aktualizován záznam: 
\begin_inset Formula $r=c(f)+c(\mathbf{x})$
\end_inset

.
 Krok
\begin_inset space ~
\end_inset

2 je ukončen a vrátí výsledek 
\emph on
Nalezena celočíselná L-třída
\emph default
.
 Není-li nalezené řešení celočíselné, krok 2 je rovněž ukončen a vrátí výsledek
 
\emph on
Nalezena zlomková L-třída
\emph default
.
\end_layout

\begin_layout Standard
Není-li nalezena žádná L-třída, krok 2 vrátí výsledek 
\emph on
Nenalezena žádná L-třída
\emph default
.
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section
Alternativní varianta hybridního algoritmu
\end_layout

\begin_layout Standard
Alternativní varianta hybridního algoritmu se liší od původní tím, že místo
 genetického algoritmu využívá algoritmus simulovaného ochlazování.
\end_layout

\begin_layout Standard
Použitý genetický algoritmus má v sobě zabudované použití simplexové metody
 pro řešení LP problému při operaci křížení.
 Simplexová metoda je obecně výpočetně náročná.
 Vzhledem k tomu, že je nutné spolehlivě ověřit, že nalezené řešení je celočísel
né, musí se provádět alespoň část kroků simplexové metody v oboru přesně
 reprezentovaných racionálních čísel, která s sebou nesou další nároky na
 výpočetní výkon a paměťový prostor.
\end_layout

\begin_layout Standard
Simulované ochlazování je založeno na principech podobných genetickému algoritmu
 (lokální heuristika s možností překonávat lokální minima) a skládá se z
 velkého počtu opakování poměrně jednoduchých kroků (na rozdíl od genetického
 algoritmu).
\end_layout

\begin_layout Standard
Alternativní varianta hybridního algoritmu si klade za cíl dosáhnout stejných
 nebo podobných výsledků jako původní varianta prováděním většího množství
 jednodušších operací.
\end_layout

\begin_layout Standard
Algoritmy simulovaného ochlazování používají pro překonání lokálních minim
 stejně jako genetické algoritmy náhodné změny.
 Základnímu algoritmu simulovaného ochlazování chybí analogie ke křížení,
 proto byl pro alternativní variantu hybridního algoritmu vybrán algoritmus
 simulovaného ochlazování doplněný o určitou analogii křížení - morfing.
 Tento algoritmus je popsán v 
\begin_inset CommandInset citation
LatexCommand cite
key "key-9"

\end_inset

.
\end_layout

\begin_layout Subsection
Principy simulovaného ochlazování
\end_layout

\begin_layout Subsubsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Fyzikální-pohled-na"

\end_inset

Fyzikální pohled na ochlazování
\end_layout

\begin_layout Standard
Proces simulovaného ochlazování lze ilustrovat na příkladu kovu, který je
 zahřátý na vysokou teplotu a po zahřátí je volně ponechán k pomalému vychladnut
í.
\end_layout

\begin_layout Standard
V průběhu ochlazování se stav kovu mění.
 Je možné v něm pozorovat domény, jejichž atributem je energie atomů potřebná
 k vstupu do domény.
 Chladne-li kov pomalu, potřebná energie se v doménách příliš neliší a atomy
 mohou volně procházet mezi doménami a zaujímat pozice s nízkou energií.
 Chladne-li kov rychle, může se stát, že potřebná energie se v jednotlivých
 doménách bude lišit natolik, že rozdíl povede k vytvoření pro atomy nepřekonate
lné hranice.
\end_layout

\begin_layout Standard
Nepřekonatelné hranice se pak mohou stát zlomovými čarami, podél kterých
 může kov praskat, pokud je ohýbán.
 Z tohoto důvodu (praskání je obvykle nežádoucí) se kov ochlazuje pomalu,
 tak aby se atomy mohly přemísťovat.
 Po celém kovu je pak rozložení minimální energie stejné.
 Celá masa kovu je pak tvořena jedinou pravidelně uspořádanou doménou.
\end_layout

\begin_layout Standard
Představme si atom, který má možnost ze stavu charakterizovaného energií
 
\begin_inset Formula $E1$
\end_inset

 přejít do jiného stavu charakterizovaném energií 
\begin_inset Formula $E2$
\end_inset

.
 Pak pravděpodobnost přechodu do stavu 
\begin_inset Formula $E2$
\end_inset

 je dána vzorcem:
\end_layout

\begin_layout Standard
\begin_inset Formula \[
p(\rightarrow E2)=min\{1,e^{-\frac{E2-E1}{kT}}\}\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $T$
\end_inset

 je teplota, 
\begin_inset Formula $k$
\end_inset

 je daná konstanta.
 Nabízí se například Bolzmannova konstanta.
 Ze vzorce lze vyčíst, že pravděpodobnost přechodu do stavu s nižší energií
 je velká.
 Pravděpodobnost přechodu do stavu s vyšší energií je však nenulová.
 S klesající teplotou se pravděpodobnost přechodu do stavu s vyšší energií
 zmenšuje.
\end_layout

\begin_layout Subsubsection
Pohled z hlediska kombinatorických optimalizačních problémů
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="2">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="left" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Fyzikální pohled
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
KOP
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Stav systému
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Řešení
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Změna stavu
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Přechod k sousednímu řešení
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Energie systému
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Optimalizační kritérium
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Kinetická energie částic
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ochota přejít od lepšího řešení k horšímu
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Teplota
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Parametr pro řízení algoritmu
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Subsubsection
Algoritmus simulovaného ochlazování
\end_layout

\begin_layout Standard
Simulované ochlazování (SA) je lokální heuristika, která simuluje proces
 ochlazování pomocí prostředků výpočetní techniky.
 Než může být tento proces simulován, je třeba rozhodnout následující otázky:
\end_layout

\begin_layout Enumerate
Jak budou kódovány jednotlivé stavy?
\end_layout

\begin_layout Enumerate
Jak je definováno optimalizační kritérium?
\end_layout

\begin_layout Enumerate
Jaký bude mechanismus náhodných změn systému?
\end_layout

\begin_layout Enumerate
Jak bude definován řídící parametr 
\begin_inset Formula $T$
\end_inset

 analogický k teplotě?
\end_layout

\begin_layout Enumerate
Jaký bude 
\emph on
plán
\emph default
 ochlazování, tedy jak se bude snižovat řídící parametr
\begin_inset Formula $T$
\end_inset

?
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sub:Algoritmus-simulovaného-ochlazování"

\end_inset

Algoritmus simulovaného ochlazování pro problém pokrytí (SASCP)
\end_layout

\begin_layout Subsubsection
Kódování stavů a optimalizační kritérium
\end_layout

\begin_layout Standard
Algoritmus SASCP kóduje jednotlivé stavy jako vektory jedniček a nul (binární
 vektory).
 Optimalizačním kritériem je cena pokrytí.
\end_layout

\begin_layout Subsubsection
Celkové schéma algoritmu SASCP
\end_layout

\begin_layout Standard
Nechť 
\begin_inset Formula $\mathbf{x}_{b}$
\end_inset

 je nejlepší dosud nalezené řešení a 
\begin_inset Formula $(c,\mathbf{x}_{b})$
\end_inset

 jeho cena.
 Nechť 
\begin_inset Formula $\mathbf{x}$
\end_inset

 je řešení a 
\begin_inset Formula $(c,\mathbf{x})$
\end_inset

 jeho cena.
 
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

0 Získej počáteční řešení problému pokrytí 
\begin_inset Formula $\mathbf{x}$
\end_inset

.
 a dolní mez 
\begin_inset Formula $LB$
\end_inset


\begin_inset Newline newline
\end_inset

Proveď počáteční nastavení: 
\begin_inset Formula $\mathbf{x}_{b}=x$
\end_inset

, 
\begin_inset Formula $(c,\mathbf{x}_{b})=(c,\mathbf{x})$
\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1 Vyhledej souseda 
\begin_inset Formula $\mathbf{x'}$
\end_inset

 řešení 
\begin_inset Formula $\mathbf{x}$
\end_inset

 pomocí procedury SEARCH
\begin_inset Newline newline
\end_inset


\begin_inset Formula $\delta=(c,\mathbf{x}')$
\end_inset

, 
\begin_inset Formula $\omega=rand<0,1)$
\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2 Rozhodni o přijetí souseda
\begin_inset Newline newline
\end_inset

Jestliže 
\begin_inset Formula $\delta\leq0$
\end_inset

 nebo 
\begin_inset Formula $\omega<e^{-\frac{\delta}{T}}$
\end_inset

, nastav 
\begin_inset Formula $\mathbf{x}=\mathbf{x}'$
\end_inset

 a jestliže 
\begin_inset Formula $(c,\mathbf{x})<(c,\mathbf{x}_{b})$
\end_inset

, nastav 
\begin_inset Formula $(c,\mathbf{x}_{b})=(c,\mathbf{x})$
\end_inset

 a 
\begin_inset Formula $(\mathbf{x}_{b}=\mathbf{x})$
\end_inset


\begin_inset Newline newline
\end_inset

Je-li splněna nerovnost 
\begin_inset Formula $ZMAX\geq(c,\mathbf{x}_{b})$
\end_inset

, algoritmus je ukončen
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

3 Nebylo-li dosaženo daného počtu iterací, pokračuj krokem 1
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

4 Sniž teplotu.
 
\begin_inset Formula $T=T\cdot constant$
\end_inset


\begin_inset Newline newline
\end_inset

Byla-li dosažena koncová teplota, algoritmus je ukončen
\end_layout

\begin_layout Subsubsection
Procedura SEARCH (hledání sousedního stavu)
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1 Odstraň sloupec z řešení pomocí procedury DEFLECT
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2 Proveď morfing pomocí procedury MORPH
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

3 Vytvoř řešení problému pokrytí pomocí procedury CONSTRUCT
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

4 Odstraň nadbytečné sloupce z řešení pomocí procedury REDUND
\end_layout

\begin_layout Subsubsection
Procedura DEFLECT
\end_layout

\begin_layout Standard
Procedura DEFLECT simuluje náhodné změny v systému tím, že odstraňuje sloupce
 z řešení.
 Počet volání procedury DEFLECT se zaznamenává.
 Je-li počet volání dělitelný třemi, z řešení se odstraní sloupec, který
 poskytuje nejméně unikátních pokrytí řádků.
 Není-li počet volání dělitelný třemi, z řešení je odstraněn náhodně vybraný
 sloupec.
 Výsledkem procedury DEFLECT je částečné řešení problému pokrytí.
\end_layout

\begin_layout Subsubsection
Procedura CONSTRUCT
\end_layout

\begin_layout Standard
Vzhledem k tomu, že procedura DEFLECT poskytuje částečné řešení problému
 pokrytí, je třeba k tomuto řešení přidat vhodně vybrané sloupce.
\end_layout

\begin_layout Standard
K doplnění se využívají dva hladové algoritmy popsané v sekcích 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Hladový-algoritmus-dle"

\end_inset

 a 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Hladový-balasho"

\end_inset

.
 Po přidání každého čtvrtého sloupce do pokrytí je na částečné řešení aplikována
 procedura MORPH.
 Hladové algoritmy se střídají.
\end_layout

\begin_layout Subsubsection
Procedura REDUND
\end_layout

\begin_layout Standard
Procedura slouží k odstranění nadbytečných sloupců z řešení vytvořeného
 procedurou CONSTRUCT.
 Jednotlivé sloupce se probírají od nejdražšího k nejlevnějšímu a testuje
 se zda je možné odstranit je z řešení.
\end_layout

\begin_layout Subsubsection
Procedura MORPH
\end_layout

\begin_layout Standard
Procedura MORPH slouží k provádění 
\emph on
morfování
\emph default
.
 Morfování, podobně jako křížení v genetických algoritmech, představuje
 prostředek, který má zajistit pokud možno rychlou konvergenci k optimálnímu
 řešení.
 
\end_layout

\begin_layout Standard
Tak jako se křížení v genetických algoritmech snaží přenést nejlepší vlastnosti
 rodičů k jejich potomkům, morfování si klade za cíl provádět to samé v
 algoritmu simulovaného ochlazování 
\begin_inset CommandInset citation
LatexCommand cite
key "key-9"

\end_inset

.
\end_layout

\begin_layout Standard
Pro každý sloupec, který se stal součástí řešení, je vytvořen seznam omezeného
 počtu 
\begin_inset Quotes eld
\end_inset

podobných sloupců
\begin_inset Quotes erd
\end_inset

, tzv.
 
\emph on
morfů
\emph default
.
\begin_inset Newline newline
\end_inset

Podobnost dvou sloupců 
\begin_inset Formula $p$
\end_inset

 a 
\begin_inset Formula $q$
\end_inset

 je definována vzorcem:
\end_layout

\begin_layout Standard
\begin_inset Formula \[
m(p,q)=\frac{V_{p}^{T}V_{q}}{V^{1}V_{q}}\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $V^{1}$
\end_inset

 je řádkový vektor jedniček, 
\begin_inset Formula $V_{p}$
\end_inset

 je sloupcový vektor matice problému pokrytí 
\begin_inset Formula $(a_{1p},a_{2p},...,a_{mp})$
\end_inset

 a 
\begin_inset Formula $V_{q}$
\end_inset

 je sloupcový vektor 
\begin_inset Formula $(a_{1q},a_{2q},...,a_{mq})$
\end_inset

 matice problému pokrytí.
\end_layout

\begin_layout Standard
Do seznamu morfů jsou přidány pouze morfy, pro něž platí nerovnost 
\begin_inset Formula $m(a,b)\geq0,6$
\end_inset

.
 Každý sloupec může mít v seznamu až 30 morfů.
\end_layout

\begin_layout Standard
Vlastní morfování probíhá následovně:
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

1 Vyber sloupec, který je součástí řešení
\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

2 Pro všechny morfy (existují-li) vybraného sloupce vypočítej poměr:
\begin_inset Newline newline
\end_inset


\begin_inset Formula \[
\frac{cena\,částečného\,řešení}{počet\, pokrytých\,řádků}\]

\end_inset


\end_layout

\begin_layout List
\labelwidthstring 00.00.0000
Krok
\begin_inset space ~
\end_inset

3 Vyber morf s nejvyšším poměrem (existuje-li) a nahraď jím vybraný sloupec.
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section
Implementace
\end_layout

\begin_layout Standard
Hybridní algoritmus pro problém pokrytí je implementován ve formě knihovny
 napsané v ANSI dialektu jazyka C s využitím techniky modulárního programování.
 Jazyk C byl zvolen zejména kvůli rychlosti provádění přeloženého programu.
\end_layout

\begin_layout Standard
Vzhledem k tomu, že překladače jazyka C jsou dostupné již od druhé poloviny
 sedmdesátých let 20.
 století a jsou dodnes velmi často používány, tvůrci překladačů měli dostatek
 času na vylepšování efektivity generovaného strojového kódu.
 Nezanedbatelnou výhodou je také množství platforem, pro které je překladač
 ANSI dialektu jazyka C k dispozici.
\end_layout

\begin_layout Subsection
Moduly
\end_layout

\begin_layout Subsubsection*
Hlavní moduly
\end_layout

\begin_layout Standard
Vlastní knihovna se skládá z dále stručně popsaných modulů:
\end_layout

\begin_layout Subparagraph*
Modul hybridního algoritmu.
\end_layout

\begin_layout Standard
Modul poskytující rozhraní pro aplikace využívající knihovnu.
 Umožňuje předat vstupní problém, nastavit parametry algoritmu a předat
 zpět výsledné řešení.
\end_layout

\begin_layout Subparagraph*
Modul hladových algoritmů.
\end_layout

\begin_layout Standard
Implementace dvou druhů hladových algoritmů pro problém pokrytí.
 První algoritmus je hladový algoritmus pro problém pokrytí dle Chvátala,
 druhý je algoritmus podle Balase a Hoa - viz sekce 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Hladový-algoritmus-dle"

\end_inset

 a 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Hladový-balasho"

\end_inset

.
 Modul je schopen spolupráce s modulem simulovaného ochlazování při morfování.
\end_layout

\begin_layout Subparagraph*
Modul lagrangeovské heuristiky.
\end_layout

\begin_layout Standard
Implementace pěti variant Lagrangeovské heuristiky pro problém pokrytí.
\end_layout

\begin_layout Subparagraph*
Modul genetického algoritmu.
\end_layout

\begin_layout Standard
Implementace nebinárního genetického algoritmu s nastavitelnými parametry.
 Modul spolupracuje s modulem hladových algoritmů a
\begin_inset space ~
\end_inset

také s
\begin_inset space ~
\end_inset

modulem pro spolupráci s externí implementací simplexové metody.
\end_layout

\begin_layout Subparagraph*
Modul simulovaného ochlazování.
\end_layout

\begin_layout Standard
Implementace simulovaného ochlazování s morfováním.
 Modul spolupracuje s modulem hladových algoritmů.
\end_layout

\begin_layout Subparagraph*
Modul pro spolupráci s externí implementací simplexové metody.
\end_layout

\begin_layout Standard
Modul zajišťuje spolupráci s knihovnou GLPK, která je určena pro řešení
 problémů lineárního programování simplexovou metodou.
 
\end_layout

\begin_layout Subparagraph*
Modul výčtu L-tříd.
\end_layout

\begin_layout Standard
Implementace algoritmu 
\begin_inset Quotes eld
\end_inset

Výčet L-tříd
\begin_inset Quotes erd
\end_inset

, modul spolupracuje s modulem lagrangeovské heuristiky a s modulem pro
 spolupráci s externí implementací simplexové metody.
\end_layout

\begin_layout Subparagraph
Modul pohledu na problém pokrytí.
\end_layout

\begin_layout Standard
Implementace pohledu na problém pokrytí.
 Nad pohledy na problém pokrytí je definováno množství operací.
\end_layout

\begin_layout Subsubsection*
Pomocné moduly
\end_layout

\begin_layout Standard
Pomocné moduly jsou široce využívány v různých částech knihovny, jejich
 význam je zřejmý z jejich názvů.
\end_layout

\begin_layout Itemize
Modul pro reprezentaci problému pokrytí
\end_layout

\begin_layout Itemize
Pomocný modul pro řazení metodou QuickSort
\end_layout

\begin_layout Itemize
Pomocný modul pro načítání problémů pokrytí z textových souborů
\end_layout

\begin_layout Itemize
Modul poskytující implementaci spojového seznamu celých čísel
\end_layout

\begin_layout Subsection
Datové struktury
\end_layout

\begin_layout Standard
V knihovně jsou většinou používány velmi jednoduché datové struktury.
\end_layout

\begin_layout Subsubsection*
Problém pokrytí
\end_layout

\begin_layout Standard
K reprezentaci problému pokrytí se používá dvourozměrné pole, k reprezentaci
 vektoru cen pole jednorozměrné.
\end_layout

\begin_layout Standard
Vzhledem k tomu, že matice problému pokrytí může obsahovat velké množství
 prvků, je nepřijatelné, aby bylo při běhu programu vytvářeno mnoho jejích
 kopií.
 Dále je nepřijatelné, aby se prováděly přesuny sloupců nebo řádků (například
 při řazení metodou QuickSort).
 Z tohoto důvody jsou zavedeny různé 
\emph on
pohledy na problém pokrytí
\emph default
.
\end_layout

\begin_layout Subsubsection*
Masky
\end_layout

\begin_layout Standard
V modulech se často používá jednoduchá datová struktura - binární vektor
 či 
\emph on
maska
\emph default
, která je vstupem nebo výstupem různých operací.
 
\end_layout

\begin_layout Subsubsection*
Pohledy na problém pokrytí
\end_layout

\begin_layout Standard
Hlavním cílem pohledů na problém pokrytí je šetření paměťového prostoru.
 Pohledy obsahují odkaz na reprezentaci problému pokrytí a zejména 
\emph on
mapovací pole
\emph default
, která mapují souřadnice řádků a sloupců matice pohledu na souřadnice řádků
 a sloupců matice problému pokrytí.
 Navíc jsou uchovávána pole pro mapování na rodičovský pohled.
 Lze tedy vytvořit určitou hierarchii spolupracujících pohledů.
\end_layout

\begin_layout Standard
Při řazení a odstraňování sloupců či řádků jsou měněna pouze mapovací pole;
 přesunuje se tedy relativně malé množství dat.
 Tak se ušetří paměťový prostor, ale i výpočetní výkon.
 Pohled je datová struktura o velikosti: 
\end_layout

\begin_layout Standard
\begin_inset Formula \[
V=2m*sizeof(int)+2n*sizeof(int)+2*sizeof(int)+PTR\]

\end_inset

kde 
\begin_inset Formula $m$
\end_inset

 je počet řádků, 
\begin_inset Formula $n$
\end_inset

 počet sloupců matice problému pokrytí a 
\begin_inset Formula $PTR$
\end_inset

 velikost datového typu ukazatel.
\end_layout

\begin_layout Standard
Nad pohledy pokrytí je možné provádět množství operací, jako například odstraněn
í dominancí, tvorba podpohledů definovaných maskami sloupců či řádků, odstranění
 nezbytných sloupců s vrácením jejich seznamu, detekce zda je nějaká maska
 řešením problému pokrytí, klonování pohledů.
\end_layout

\begin_layout Subsection
Simplexová metoda
\end_layout

\begin_layout Standard
Pro řešení LP problémů v kroku 2 algoritmu LCE se používá simplexová metoda
 implementovaná v knihovně GLPK.
 Původní rozhodnutí pro vlastní implementaci bylo zavrženo, protože tvorba
 kvalitní implementace simplexové metody s sebou přináší množství úskalí
 - hlavními problémy jsou numerická stabilita a zejména degenerace - viz
 
\begin_inset CommandInset citation
LatexCommand cite
key "key-10"

\end_inset

.
\end_layout

\begin_layout Standard
Vzhledem k tomu, že v algoritmu LCE je naprosto klíčové rozpoznávání celočíselný
ch a neceločíselných řešení, je vyloučeno spoléhat se na nepřesně reprezentovaná
 reálná čísla odpovídající datovým typům 
\emph on
float
\emph default
 a 
\emph on
double
\emph default
 jazyka C.
\end_layout

\begin_layout Standard
Na druhou stranu práce s přesnými racionálními čísly je výpočetně a paměťově
 náročná, protože po každé aritmetické operaci definované nad těmito čísly
 se musí provádět jejich normalizace (například euklidovský algoritmus pro
 hledání společného jmenovatele).
 Při užití simplexové metody se provádí mnoho operací dělení, z čehož plyne,
 že jmenovatelé racionálních čísel mohou značně narůstat.
\end_layout

\begin_layout Standard
Z popsaných důvodů je použit kombinovaný postup.
 Nejprve se nalezne optimální báze řešení pomocí operací v prostoru nepřesných
 reálných čísel a dále se pak pokračuje operacemi v prostoru přesných racionální
ch čísel.
 Takový postup je přímo doporučen v dokumentaci knihovny GLPK.
\end_layout

\begin_layout Standard
Modul pro spolupráci s externí implementací simplexové metody lze snadno
 upravit tak, aby využíval i jiné externí implementace, například knihovnu
 lp_solve.
\end_layout

\begin_layout Subsection
Kontrolní mechanismy
\end_layout

\begin_layout Standard
V případě potřeby lze knihovnu přeložit se začleněním mechanismu vynucených
 podmínek (assertions).
 Při ladění knihovny byla intenzivně používána sada nástrojů VALGRIND.
 Knihovna je prosta paměťových úniků a chyb vyplývajících ze značné volnosti
 přístupu k paměti v jazyce C.
\end_layout

\begin_layout Subsection
Začlenění do programu BOOM
\end_layout

\begin_layout Standard
Při začleňování knihovny do program BOOM byl kladen důraz na to, aby nebylo
 nutné měnit kód knihovny samotné.
 Z tohoto důvodu byla podle pokynů vedoucího práce do programu BOOM přidána
 přizpůsobovací třída 
\family typewriter
HybridCover
\family default
 s přesně definovaným rozhraním, která má dva úkoly - zajistit volání funkcí
 poskytovaných knihovnou a konvertovat reprezentace problému pokrytí a jeho
 řešení.
\end_layout

\begin_layout Standard
Vzhledem k tomu, že program BOOM používá odlišnou reprezentaci problému
 pokrytí (spojové seznamy proti matici), byl přidán krátký kód provádějící
 převod jedné reprezentace do druhé.
 Totéž platí i pro reprezentaci řešení problému pokrytí, které musí být
 převedeno z formy masky do formy spojového seznamu indexů sloupců.
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagestyle{empty}
\end_layout

\end_inset


\end_layout

\begin_layout Section
Výpočetní experimenty
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagestyle{empty}
\end_layout

\end_inset


\end_layout

\begin_layout Section
Závěr
\end_layout

\begin_layout Standard
Hybridní algoritmus pro problém pokrytí byl podrobně popsán pro potřeby
 implementace a
\begin_inset space ~
\end_inset

společně s
\begin_inset space ~
\end_inset

jeho alternativní variantou implementován ve formě knihovny psané v
\begin_inset space ~
\end_inset

ANSI dialektu jazyka C
\begin_inset space ~
\end_inset

a
\begin_inset space ~
\end_inset

s pomocí jednoduché adaptační třídy začleněn do programu BOOM.
 Srovnáním výsledků s algoritmem AURA bylo ověřeno, že hybridní algoritmus
 pracuje 
\emph on
korektně
\emph default
 a jeho výsledkem je optimální řešení problému pokrytí.
 Algoritmus je schopen řešit problémy pokrytí i s nejednotkovými cenami
 sloupců.
 Ve srovnání s algoritmem AURA je hybridní algoritmus velmi pomalý.
\end_layout

\begin_layout Standard
Základní výpočetní experimenty ukázaly nepříjemnou skutečnost.
 Lagrangeovská heuristika určená pro urychlování výčtu L-tříd neplní dobře
 svoji funkci, protože jen výjimečně zabrání spuštění simplexové metody,
 nebo sníží hodnotu záznamu
\begin_inset space ~
\end_inset

-
\begin_inset space ~
\end_inset

viz
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Výčet-L-tříd-(LCE"

\end_inset

.
 Z tohoto důvodu byla Lagrangeovská heuristika z výčtu L-tříd při dalších
 experimentech vyřazena.
\end_layout

\begin_layout Standard
Z provedených výpočetních experimentů vyplývá, že je třeba nejprve najít
 výkonnostní rezervy v mé implementaci hybridního algoritmu - zjištěné chování
 Lagrangeovské určené pro urychlování výčtu L-tříd heuristiky naznačuje,
 že by takové rezervy mohly existovat.
 Teprve v případě, že by tyto rezervy byly nedostatečné, hybridní algoritmus
 pro problém pokrytí nepočítat k dnes moderním metodám jeho řešení.
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagestyle{empty}
\end_layout

\end_inset


\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-1"

\end_inset

A.
 V.
 Eremeev, A.
 A.
 Kolokolov, L.
 A.
 Zaozerskaya: A hybrid algorithm for set covering problem.
 In Proc.
 of International Workshop ”Discrete Optimization Methods in Scheduling
 and Computer-Aided Design, pp.
 123—129
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-2"

\end_inset

http://www.wikipedia.org, leden 2008
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-3"

\end_inset

Demel: Grafy a jejich aplikace, Academia 2002
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-4"

\end_inset

Krejčík: Moderní metody řešení problému pokrytí, bakalářská práce, 2005.
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-5"

\end_inset

Schmidt: Problémy a algoritmy, přednáškové slidy
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-6"

\end_inset

Chvátal: V.
 A Greedy Heuristic for the Set Covering Problem, Mathematics of Operations
 Research, vol.
 4, No 3, 1979
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-7"

\end_inset

Techapichetvanich, Bricker: INVESTIGATION OF LAGRANGIAN HEURISTICS FOR SET
 COVERING PROBLEMS, Department of Industrial Engineering, The University
 of Iowa,Iowa City, IA 52242,USA,May 1993
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-8"

\end_inset

Dudorkin: Operační výzkum, Praha 1991
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-9"

\end_inset

Brusco, Jacobs, Thompson: A morphing procedure to supplement a simulated
 annealing heuristic for cost and coverage correlated set-covering problems,
 Annals of Operations research 86, 1999
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-10"

\end_inset

Koberstein: The Dual simplex method, techniques for fast and stable implementati
on, disertační práce, 2005
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-11"

\end_inset

GNU Linear programming kit, Reference manual version 4.35, 2009
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-12"

\end_inset

Krejčík: Moderní metody řešení problému pokrytí, diplomová práce, 2007
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-13"

\end_inset

E.
 I.
 Goldberg, L.
 P.
 Carloni, T.
 Villa , R.
 K.
 Brayton: Negative thinking by incremental problem solving: application
 to unate covering.
 Proceedings of IEEE International Conference on Computer Aided Design (ICCAD,
 San Jose, CA, USA, 9-13 Nov.
 1997).
 Los Alamitos, CA, USA:IEEE Comput.
 Soc, 1997.
 pp.
 91—99
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "key-14"

\end_inset

L.
 P.
 Carloni, E.
 I.
 Goldberg, T.
 Villa, R.
 K.
 Brayton and A.
 L.
 Sangiovanni-Vincentelli: Aura II: Combining Negative Thinking and Branch-and-Bo
und in Unate Covering Problems.
 In "VLSI: Systems on a Chip" (L.M.
 Silveira, R.
 Reis, S.
 Devadas editors), Kluwer 1999 
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\start_of_appendix
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagestyle{empty}
\end_layout

\end_inset


\end_layout

\begin_layout Section
Příklad použití knihovny hybridscp
\end_layout

\begin_layout Standard
Použití knihovny hybridscp v programech je přímočaré, spočívá v provedení
 následujících kroků:
\end_layout

\begin_layout Enumerate
Ke zdrojovým textům je třeba připojit hlavičkový soubor 
\family typewriter
hybrid.h
\end_layout

\begin_layout Enumerate
Vytvoří se instance problému pokrytí a naplní se daty
\end_layout

\begin_layout Enumerate
Vytvoří se instance hybridního algoritmu, předat se jí problém pokrytí,
 a spustí výpočet
\end_layout

\begin_layout Enumerate
Po dokončení výpočtu se vyzvedne řešení ve formě masky
\end_layout

\begin_layout LyX-Code
#include <hybrid.h>
\end_layout

\begin_layout LyX-Code
#define REMOVE DOMINANCES 1
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code
int main(int argc,char* argv) {
\end_layout

\begin_deeper
\begin_layout LyX-Code
SCProblem* problem=NULL;
\end_layout

\begin_layout LyX-Code
Hybrid* hybrid=NULL;
\end_layout

\begin_layout LyX-Code
unsigned char* solution;
\end_layout

\begin_layout LyX-Code
int result=0;
\end_layout

\begin_layout LyX-Code
problem=scproblem_new(20,10);
\end_layout

\begin_layout LyX-Code
scproblem_set(problem,2,4,1);
\end_layout

\begin_layout LyX-Code
...
\end_layout

\begin_layout LyX-Code
scproblem_set_cost(problem,1,2);
\end_layout

\begin_layout LyX-Code
...
\end_layout

\begin_layout LyX-Code
hybrid=hybrid_new(problem);
\end_layout

\begin_layout LyX-Code
hybrid_set_parameters(hybrid,...);
\end_layout

\begin_layout LyX-Code
hybrid_set_sa_parameters(hybrid,...);
\end_layout

\begin_layout LyX-Code
...
\end_layout

\begin_layout LyX-Code
result=hybrid_solve(hybrid,REMOVE_DOMINANCES);
\end_layout

\begin_layout LyX-Code
switch (result)
\end_layout

\begin_deeper
\begin_layout LyX-Code
case HYBRID_OK : {
\end_layout

\begin_deeper
\begin_layout LyX-Code
solution=hybrid_get_solution(hybrid);
\end_layout

\begin_layout LyX-Code
break;
\end_layout

\end_deeper
\begin_layout LyX-Code
}
\end_layout

\begin_layout LyX-Code
case HYBRID_NOTSOLVABLE: {
\end_layout

\begin_deeper
\begin_layout LyX-Code
printf("Problem not solvable");
\end_layout

\end_deeper
\begin_layout LyX-Code
}
\end_layout

\begin_layout LyX-Code
case HYBRID_IMPLICIT: {
\end_layout

\begin_deeper
\begin_layout LyX-Code
printf("Not necessary to solve");
\end_layout

\end_deeper
\begin_layout LyX-Code
}
\end_layout

\end_deeper
\begin_layout LyX-Code
}
\end_layout

\begin_layout LyX-Code
return (EXIT_SUCCESS)
\end_layout

\end_deeper
\begin_layout LyX-Code
}
\end_layout

\begin_deeper
\begin_layout LyX-Code

\end_layout

\end_deeper
\end_body
\end_document
