UA SIE545 优化理论基础5 搜索与整数规划1 DFS算法

• DFS方法基础
• 邮票问题

这部分的主要目标是建立求解整数规划的方法，早期解决整数规划需要穷举，后来人们把搜索技术应用到整数规划中，极大地提高了整数规划求解地效率，最常被用到的两种技术是DFS和分支定界，所以这部分就从这两种技术开始介绍，然后讨论怎么用来解决整数规划问题。

DFS方法基础

DFS全称是Depth First Search，也就是深度优先搜索。这个算法思路很简单，就是莽就完了，但莽的时候要记录莽过的路径，下一个位置不符合要求就可以退回来重新莽。下面用一个简单的例子说明，假设在一个$4\times 4$的棋盘上要放四个棋子，每两个棋子不能位于同一行同一列同一对角线，要计算所有的放法。

首先讨论一下穷举法，在$4\times 4$的棋盘上放四个棋子的放法一共有$4^4=256$种，因此用穷举法需要对256种可能性进行判断。（如果我是随便做做估计就穷举了，毕竟不用动脑筋而且运算量也不大）但显然用穷举来做估计是拿不到分的，我们要根据题目的限制条件来做搜索。

简单阐述一下DFS解决这个问题的思想。假设第一个棋子放在第一行，第二个放在第二行，以此类推，用$i,j,k,l$表示第1-4行的棋子的位置。第一步，考虑$(1,j,k,l)$:

OXXX

X	X
X		X
X			X

O代表对应位置放上了棋子，X代表对应位置不能再放棋子了。从这个图可以看出，$i=1$，也就是第一个棋子放在第一行第一个位置以后，第二个棋子只能在$j=3,4$的位置，假设优先搜索靠左的位置，接下来我们考虑$(1,3,k,l)$：

OXXX

X	X	O	X
X		X
X		X	X

现在放第三个棋子，显然它只能在$k=2,4$的位置，接下来就考虑$(1,3,2,l)$:

OXXX

X	X	O	X
X	O	X	X
X	X	X	X

于是路就走不通了，第四个棋子没位置了，那么我们退回去，考虑$(1,3,4,l)$:

OXXX

X	X	O	X
X	X	X	O
X		X	X

最后剩下$l=2$这个位置，它是符合要求的，那么$(1,3,4,2)$就构成了第一条通路。现在我们记录下通路的信息，然后回到第二个棋子处，考虑$(1,4,k,l)$:

OXXX

X	X	X	O
X		X	X
X			X

第三个棋子没得选，那就放在第二个位置

OXXX

X	X	X	O
X	O	X	X
X	X		X

最后第四个棋子只能放在第三个位置，因此$(1,4,2,3)$构成了第二条通路。这样我们就完成了$i=1$的所有搜索，下面的步骤就是对$i=2,3,4$做同样的搜索。

邮票问题

邮局发行了一套有$n$种不同面值的邮票，记面值为$(S_1,\cdots ,S_n)$（$S_i<S_{i-1}$），每个信封最多能贴$m$张邮票，为了保证这套邮票可以贴出$(1,2,\cdots ,N)$这些面值，请问面值应该怎么设计？

假设$r$是一个自然数，如果它是能被这套邮票表示的面值，那么$\exists \{t_1,\cdots ,t_n\}\subset \mathbb{N}$,
$$r=\sum _{i=1}^n{t}_i{S}_i,\sum _{i=1}^n{t}_i\le m$$

这个问题的输入是$n,m$，输出是$(S_1,\cdots ,S_n)$以及$N$，要实现的是
$$\begin{gathered} \underset{S_1,\cdots ,S_N}{\max }N \\ s.t.r=\sum _{i=1}^n{t}_i{S}_i,\sum _{i=1}^n{t}_i\le m \\ 1\le r\le N \end{gathered}$$

这是一个典型的整数规划问题，下面我们简单讨论一下怎么用DFS的思想解这个问题。先考虑搜素范围，显然
$$1=S_1<S_2<S_3<\cdots <S_n\le N$$

在搜索$S_i$的可能取值时，要保证$S_i$不会大于能用前$i-1$个面值的邮票连续表示的最大整数，记为$Int(S_1,\cdots ,S_{i-1})$，也就是
$$S_{i-1}<S_i\le Int(S_1,\cdots ,S_{i-1})$$

按这个记号，$N=Int(S_1,\cdots ,S_n)$。下面以$n=5$,$m=3$为例说明一下搜索过程：

$S_1=1$, $m=3\Rightarrow Int(S_1)=3$，因此$S_2\in \{2,3\}$，假设更小的数被优先搜索，下面考虑$S_2=2$；

$Int(S_1,S_2)=6$，因此$S_3\in \{3,4,5,6\}$，下一步考虑$S_3=3$

$Int(S_1,S_2,S_3)=9$，因此$S_4\in \{4,5,6,7,8,9\}$，下一步考虑$S_4=4$

$Int(S_1,S_2,S_3,S_4)=12$，因此$S_5\in \{5,6,7,8,9,10,11,12\}$，如果$S_5=5$，则$N=15$。这就拿到了第一种可能面值为$(1,2,3,4,5)$，三张邮票能表示的最大面值为15，记录下这个信息后转到$S_5=6$，计算得到$N=16$，记录这个信息后转到$S_5=7$，以此类推，讨论完$S_5$的所有可能性后回到$S_4$的其他可能，然后再回到$S_3$和$S_2$的其他可能

Lunnon（1969）修正了这个算法，提出在搜索$S_i$的取值时可以先进行剪枝操作再搜索，可以降低算法复杂度。他认为
$$S_i<\frac{Int(S_1,\cdots ,S_{i-1})-1}{m},S_{i-1}<\frac{Int(S_1,\cdots ,S_{i-1})-1}{m^2}$$

这两个分支可以剪掉。沿用上面的数值例子，引入剪枝操作，简单说明一下搜索过程：

$S_1=1$, $m=3\Rightarrow Int(S_1)=3$，因此$S_2\in \{2,3\}$，计算$\frac{Int(S_1)-1}{m}=2/3$与$S_2$的可能取值比较，发现不符合剪枝条件，假设更小的数被优先搜索，下面考虑$S_2=2$；

$Int(S_1,S_2)=6$，因此$S_3\in \{3,4,5,6\}$，计算$\frac{Int(S_1,S_2)-1}{m}=5/3$，与$S_3$的可能取值比较，不符合剪枝条件；计算$\frac{Int(S_1,S_2)-1}{m^2}=5/9$，与$S_2$的可能取值比较，不符合剪枝条件，下一步考虑$S_3=3$；

后续步骤以此类推，我就不打字详细说明了。

总结

以上是生活随笔为你收集整理的UA SIE545 优化理论基础5 搜索与整数规划1 DFS算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。