Homework09-2.tex

\section{0416}\label{sec:0416}
\begin{questions}\label{qset:0416}

    \question 求$n \times m$棋盘上任意两点之间马能够走的最短路径长度

    \begin{solution}
        构造图$G=(E,V)$\begin{itemize}
            \item $E$为棋盘上所有格点
            \item 若“马”能从棋盘上的点$v$经过一步走到$w$，则$(v,w) \in V$
        \end{itemize}

        对上图进行广度优先搜索即可找出最短路径长度。
        进一步地，构图和广度优先搜索可以同时进行。

        {
        \color{red}
        因为是任意两点，所以应该应用Floyd算法求出所有点对之间的最短距离。
        }

    \end{solution}

    \question 设计线性时间算法求树的最大匹配

    \begin{solution}
        树中一个非叶子节点连向其子节点的若干条边及连向其父节点的边中，至多只有一条边属于匹配。

        记函数$f(v, b)$为以$v$为根节点的子树中最大匹配的边数，其中$b$为布尔值\begin{itemize}
            \item 当$b=1$时，存在一条与$v$直接相连的边在最大匹配中
            \item 当$b=0$时，与$v$直接相连的边都不在最大匹配中
        \end{itemize}

        对于树的根节点$v$，假设其有3个子节点$w_1,w_2,w_3$并有相应地与之相连的三条边$e_1, e_2, e_3$，则
        \[
            f(v) = \max_b {f(v,b)} = \max \begin{cases}
                f(w_1,1) + f(w_2,1) + f(w_3,1) & (b=0) \\
                \max \begin{cases}
                    f(w_1,0) + f(w_2,1) + f(w_3,1) + 1 \\
                    f(w_1,1) + f(w_2,0) + f(w_3,1) + 1 \\
                    f(w_1,1) + f(w_2,1) + f(w_3,0) + 1 \\
                \end{cases} & (b=1)
            \end{cases}
        \]

        观察可知对于每一棵子树，只需考察$b=1$和$b=0$两种情况；且$b=0$当且仅当对于其所有子树$b=1$。
        当$v$是叶子节点时，$f(v) = f(v) = 0$；
        所以当$v$的所有子节点都是叶子节点时，$f(v) = f(v, 1) = 1$。
        对树做一次后序遍历，并按照上述规则计算出所有节点的$f(v,0)和f(v,1)$即可。

        每个节点被访问两次（下行入栈一次，上行出栈一次）；计算$f$时比较的情况数等于该节点的度数，所有节点的度数和为$2|E|$。
        所以算法的时间复杂度为$O(|V|+|E|)$
    \end{solution}

    \question 无向图$G$的顶点覆盖是指顶点集合$U$，$G$中每条边都至少有一个顶点在此集合中。
    设计线性时间算法为树寻找一个顶点覆盖，并且使该点集的规模尽量小。

    \begin{solution}
        初始化所有结点的度。
        对于所有度数为$1$的节点，首先标记其相邻的点都在$U$中，然后删除与U中的点直接相邻的所有边。
        重复上述步骤，直至所有边都被删除。

        \textbf{伪代码见算法\ref{alg:0416:03}}

        选择合适的根节点所需时间复杂度为$O(|E|)$，
        BFS的时间复杂度为$O(|E|+|V|)$，
        遍历过程中，每个节点最多被访问三次。
        总体时间复杂度为$O(|E|+|V|)$。
    \end{solution}

    \begin{algorithm}[!htp]
        \caption{求树的最小顶点覆盖} \label{alg:0416:03}
        \begin{algorithmic}[1]
            \Require {$G=(V,E)$（一棵树）}
            \Ensure {$cover$（树的最小顶点覆盖）}

            \State \Return $\left\{ V[0] \right\}$ if {$|V| \le 2$}
            \State 选一个度数大于1的节点记为$root$，广度优先搜索构建一棵树
            \State $cover \gets \Phi$
            \State $s \gets \Call{Stack.Init}{root}$

            \While {$\neg \Call{Stack.isEmpty}{s}$} \Comment{后序遍历}

            \State $node \gets \Call{Stack.Pop}{s}$

            \If {$node.isLeaf$} \Comment{当前节点是叶子节点}

            \State $node.inCover \gets \mathsf{False}$

            \ElsIf{ $node.isVisited$ } \Comment{非叶子节点，子节点已入栈}

            \For{$child$ in $node.children$}
                \If {$\neg child.inCover $}
                    \State $node.inCover \gets \mathsf{True}$
                    \State $ cover \gets cover \cup \left\{ node \right\} $
                    \State \textbf{break}
                \EndIf
            \EndFor

            \Else \Comment{非叶子节点，子节点未入栈}

            \State $\Call{Stack.Push}{node}$
            \State $\Call{Stack.Push}{**node.children}$
            \State $node.isVisited \gets \mathsf{True}$

            \EndIf

            \EndWhile

            \State \Return $cover$
        \end{algorithmic}
    \end{algorithm}
\end{questions}