203 lines
10 KiB
TeX
203 lines
10 KiB
TeX
\chapter{寻找最优}
|
||
\section{最小生成树}
|
||
\begin{definition}
|
||
设$G = (V,E)$是一连通图，$G$的每一条边有权$c(e)$，$G$的生成树$T$的权$c(T)$就是$T$的边的权和。
|
||
|
||
在$G$的所有生成树中，树权最小的那棵树称为$G$的最小生成树。
|
||
\end{definition}
|
||
|
||
\subsection{Borůvka-Kruskal算法}
|
||
\subsubsection{思路}
|
||
为了使得最后得到的生成树的边的权和最小，应该让生成树的每一条边的权值都尽可能地小。
|
||
|
||
\subsubsection{做法}
|
||
寻找没有被选中的权最小的边，如果添加它不会使得图中有圈，那么就加入它；如果添加它会使得图中形成圈，那么就考虑除它以外最小的；如此重复，直到选出了$n-1$条边。
|
||
|
||
\begin{theorem}
|
||
通过Borůvka-Kruskal算法得到的树是最小生成树。
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
\begin{figure}[htbp]
|
||
\centering
|
||
\begin{tikzpicture}
|
||
\node[draw=black, circle] (a) at (0,0) {};
|
||
\node[draw=black, circle] (b) at (0,-2) {};
|
||
\node[draw=black, circle] (c) at (2,0) {};
|
||
\node[draw=black, circle] (d) at (3,1) {};
|
||
\node[draw=black, circle] (e) at (1,2) {};
|
||
\node[draw=black, circle] (f) at (3,3) {};
|
||
\node[draw=black, circle] (g) at (-1,2) {};
|
||
\node[draw=black, circle] (h) at (-3,3) {};
|
||
\node[draw=black, circle] (i) at (-3,5) {};
|
||
\node[draw=black, circle] (j) at (-4,1) {};
|
||
\node[draw=black, circle] (k) at (-3,-1) {};
|
||
\node[draw=black, circle] (l) at (-6,0) {};
|
||
|
||
\draw[color=red] (b)--(a)--(g)--(e)--(f);
|
||
\draw[color=red] (a)--(c);
|
||
\draw[color=red] (e)--(d);
|
||
\draw[color=red] (i)--(h)--(j)--(l);
|
||
\draw[color=red] (h)--(g);
|
||
\draw[color=red] (j)--(k);
|
||
|
||
\draw[loosely dashed, color=blue, line width=2pt] (l)--(j)--(h)--(g)--(a)--(c)--(d)--(f);
|
||
\draw[loosely dashed, color=blue, line width=2pt] (k)--(a);
|
||
\draw[loosely dashed, color=blue, line width=2pt] (d)--(e);
|
||
\draw[loosely dashed, color=blue, line width=2pt] (i)--(h);
|
||
\draw[loosely dashed, color=blue, line width=2pt] (a)--(b);
|
||
|
||
\node[above, xshift=-5pt] at($(j)!0.4!(h)$) {1};
|
||
\node[above] at($(a)!0.5!(c)$) {2};
|
||
\node[left] at($(a)!0.5!(b)$) {3};
|
||
\node[above] at($(g)!0.5!(e)$) {4};
|
||
\node[above] at($(g)!0.65!(e)$) {e};
|
||
\node[above] at($(e)!0.4!(f)$) {5};
|
||
\node[above] at($(d)!0.4!(e)$) {6};
|
||
\node[below] at($(c)!0.6!(d)$) {f};
|
||
\node[above] at($(g)!0.4!(h)$) {7};
|
||
\node[above, xshift=5pt] at($(a)!0.4!(g)$) {8};
|
||
\node[above] at($(j)!0.5!(l)$) {9};
|
||
\node[above, xshift=5pt] at($(j)!0.6!(k)$) {10};
|
||
\node[left] at($(h)!0.5!(i)$) {11};
|
||
\end{tikzpicture}
|
||
\caption{一张图由Borůvka-Kruskal算法得到的最小生成树（红线）与任意一个生成树（蓝线）。图中的数字代表的是B-K算法中取边的顺序。}
|
||
\end{figure}
|
||
|
||
设算法得到的树为$F$，其它的任意一棵生成树为$T$。从一号边开始依次检查这条边是否属于$T$。如果属于，则检查下一条边；如果不属于（如4号），设这条边为$e$。
|
||
|
||
因为$T$是一棵树，因此我们将$e$加到$T$中一定会产生唯一的一个圈。而需要注意到$F$中没有圈，因此这个产生的圈中一定至少有一条异于$e$的边$f$不属于$F$。
|
||
|
||
令$H = T + e - f$，那么$H$仍是一棵生成树。现在我们需要考虑为什么B-K算法没有选择$f$而选择了$e$。如果$c(f) < c(e)$但是$f$却没被选，这说明$f$的加入会使得$f$与之前已经选中的边形成圈；而$T$中在$f$之前的边和$F$都是一样的，因此$f$也会让$T$中出现圈，可是$T$是一棵树，它不包含圈，矛盾！因此算法没有选择$f$的唯一可能原因是$c(f) \geq c(e)$。那么$c(H) \leq c(T)$。
|
||
|
||
那么我们将$H$代替$T$的位置，可以继续检查后面的边与$F$的不同。因此我们最后总能把任意图优化为$F$，即，$F$是最优解。
|
||
\end{proof}
|
||
|
||
\subsection{Jarník-Prim算法}
|
||
\subsubsection{思路}
|
||
以图中任意一点为根，生长出一棵树。
|
||
|
||
\subsubsection{做法}
|
||
找出和根相连的所有点长出的、与未在树上的点相连的边中权重最小的生长，直到长出了$n-1$条边，即连接了所有$n$个点。
|
||
|
||
\begin{theorem}
|
||
通过Jarník-Prim算法得到的树是最小生成树。
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
对$\vert V \vert$做数学归纳。
|
||
|
||
当$\vert V \vert = 1$时，显然成立；
|
||
|
||
设当$\vert V \vert = k-1$时，结论成立。那么对于$\vert V \vert = k$，设$T$是这个$k$个顶点图$G$的以$r$为根的J-P树。设$e$是生成$T$时选取的第一条边，即对所有与$r$相连的边$f$，有$c(e) \leq c(f)$。
|
||
|
||
那么我们收缩$e$得到$G \setminus e$：
|
||
\begin{figure}[H]
|
||
\centering
|
||
\subfloat[收缩前的$T$的局部]{
|
||
\begin{tikzpicture}
|
||
\node[fill=black, circle] (a) at (0,0) {};
|
||
\node[draw=black, circle] (b) at (-2,0) {};
|
||
\node[draw=black, circle] (c) at (-1,1) {};
|
||
\node[draw=black, circle] (d) at (-1,-1) {};
|
||
\node[draw=black, circle] (e) at (2,0) {};
|
||
\node[draw=black, circle] (f) at (3,1) {};
|
||
\node[draw=black, circle] (g) at (3,-1) {};
|
||
\draw (b)--(a)--(e)--(f);
|
||
\draw (c)--(a)--(d);
|
||
\draw (e)--(g);
|
||
\node[above] at ($(a)!0.5!(e)$) {$e$};
|
||
\node[yshift=10pt] at (a) {$r$};
|
||
\end{tikzpicture}
|
||
}
|
||
\hspace{1cm}
|
||
\subfloat[收缩后的$T\setminus e$的局部]{
|
||
\begin{tikzpicture}
|
||
\node[fill=black, circle] (a) at (0,0) {};
|
||
\node[draw=black, circle] (b) at (-2,0) {};
|
||
\node[draw=black, circle] (c) at (-1,1) {};
|
||
\node[draw=black, circle] (d) at (-1,-1) {};
|
||
\node[draw=black, circle] (f) at (1,1) {};
|
||
\node[draw=black, circle] (g) at (1,-1) {};
|
||
\draw (b)--(a)--(f);
|
||
\draw (c)--(a)--(d);
|
||
\draw (a)--(g);
|
||
\end{tikzpicture}
|
||
}
|
||
\end{figure}
|
||
当我们在$G$上做J-P算法做了第一步之后（即连接了$e$之后），我们一直在将$e$两端的两个端点看成一个顶点来寻找后续的边；因此，在$G \setminus e$上做J-P算法选出的第$n$个边就是在$G$中做J-P算法第$n+1$步选出的边。这也就是说，我们在$G\setminus e$上做J-P算法会得到$T\setminus e$。
|
||
|
||
根据归纳假设，$T\setminus e$是$G \setminus e$的最小生成树。
|
||
|
||
在这里，我们需要先证明另一个结论才能继续：一定存在包含$e$的$G$的最小生成树。
|
||
|
||
假设$T^\ast$是一个最小生成树，而$e \notin T^\ast$，那么$T^\ast + e$包含唯一一个圈$C$。那么可设$f$是与$r$相连的包含在$C$中的边。有$c(e) \leq c(f)$。那么$T^\prime := T^\ast + e - f$也是$G$的一个生成树且$c(T^\prime) = c(T^\ast) + c(e) - c(f) \leq c(T^\ast)$。从而一定有最小生成树$T^\prime$包含$e$。
|
||
|
||
有了$T^\prime$，我们可以得到$T^\prime \setminus e$也是$G \setminus e$的一个最小生成树。那么
|
||
\[c(T) = c(e) + c(T \setminus e) = c(e) + c(T^\prime \setminus e) = c(T^\prime)\]
|
||
|
||
即$T$是$G$的一个最小生成树。
|
||
\end{proof}
|
||
|
||
\section{货郎问题The Traveling Salesman Problem}
|
||
问题：在一个完全图中如何寻找权最小的Hamilton圈？
|
||
|
||
Hamitlton圈问题可以被转化为TSP：将原本图中存在的边赋权1，将不相邻的两点用一条新边相连，并赋权2，则哈密顿圈是否存在的问题就转化为了在此完全图中权最小的Hamilton圈是否权和为$n$的问题。
|
||
|
||
TSP问题没有满意解。
|
||
|
||
我们引入一个近似算法Tree Shortcut Algorithm：
|
||
|
||
第一步，寻找图中的一个最小生成树；
|
||
|
||
第二步，用与上一张中在Planar code中运用的方法一样遍历这棵树，得到一个closed walk；
|
||
|
||
第三步，找一些``捷径''：如果从$i$到$k$需要经过$j$，而$j$在这之前已经到达过，那么我们就直接从$i$连接至$k$，如此重复直到我们不能再简化。
|
||
|
||
\setcounter{subfigure}{0}
|
||
\begin{figure}[H]
|
||
\centering
|
||
\subfloat[在closed walk中的走法]{
|
||
\begin{tikzpicture}
|
||
\node (a) at (-2,0) {};
|
||
\node[draw=black, circle, minimum height=25pt] (j) at (0,0) {$j$};
|
||
\node[draw=black, circle, minimum height=25pt] (k) at (2,0) {$k$};
|
||
\node[draw=black, circle, minimum height=25pt] (i) at (0,-2) {$i$};
|
||
\node (b) at (4,0) {};
|
||
\draw[-{Stealth[width=5pt]}] (a)--(j);
|
||
\draw[-{Stealth[width=5pt]}] (j)..controls (-0.7,-0.5) and (-0.7,-1.5)..(i);
|
||
\draw[-{Stealth[width=5pt]}] (i)..controls (0.7,-1.5) and (0.7,-0.5)..(j);
|
||
\draw[-{Stealth[width=5pt]}] (j)--(k);
|
||
\draw[-{Stealth[width=5pt]}] (k)--(b);
|
||
\end{tikzpicture}
|
||
}
|
||
\hspace{1cm}
|
||
\subfloat[修改后的路径]{
|
||
\begin{tikzpicture}
|
||
\node (a) at (-2,0) {};
|
||
\node[draw=black, circle, minimum height=25pt] (j) at (0,0) {$j$};
|
||
\node[draw=black, circle, minimum height=25pt] (k) at (2,0) {$k$};
|
||
\node[draw=black, circle, minimum height=25pt] (i) at (0,-2) {$i$};
|
||
\node (b) at (4,0) {};
|
||
\draw[-{Stealth[width=5pt]}] (a)--(j);
|
||
\draw[-{Stealth[width=5pt]}] (j)--(i);
|
||
\draw[-{Stealth[width=5pt]}] (i)--(k);
|
||
\draw[-{Stealth[width=5pt]}] (k)--(b);
|
||
\end{tikzpicture}
|
||
}
|
||
\end{figure}
|
||
|
||
\begin{theorem}
|
||
设在TSP中每个边都满足三角不等式$c(ij) + c(jk) \geq c(ik)$，那么由Tree Shortcut Algorithm得到的圈权值不超过最小圈权值的两倍。
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
设得到的圈的权和为$c(\mathrm{tour})$，算法中closed walk的权和为$c(\mathrm{walk})$。那么由条件中的三角不等式有$c(\mathrm{tour}) \leq c(\mathrm{walk})$。
|
||
|
||
再设图中图中最小生成树的权和为$c(T)$，考虑到closed walk经过了每个边两次，因此$c(\mathrm{walk}) = 2c(T)$。
|
||
|
||
最后设最小圈的权和为$c^\ast$，且将这个圈去掉一个边后得到一个树，这个树的权和不小于最小生成树的权和，因此$c(T) \leq c^\ast$。
|
||
|
||
将几个不等式和等式合起来得到
|
||
\[c(\mathrm{tour}) \leq c(\mathrm{walk}) = 2c(T) \leq 2c^\ast \eqper \qedhere\]
|
||
\end{proof} |