最近在复习算法,
没办法,要考试啦
. 在复习回溯法的时候终于理解了之前不是很清楚的多米诺性质.
1 回溯法
由于这篇博客主要讲解多米诺性质, 默认大家已经了解回溯法啦,这里对回溯法的具体内容就不进行讲解了,
其实是太懒不想写
.
回溯法是一个很实用的算法,适合求解搜索问题和优化问题.你也可以将它看做是蛮力法(枚举法)的改进.
但不是什么情况下都可以使用回溯法, 那么就要问了,回溯法的适用条件是什么? 这就是今天的主角:
多米诺性质
2 多米诺性质
先不看多米诺性质是什么,在了解了回溯法的基本思想后,我们可以总结一下什么情况下可以使用回溯法.
2.1 回溯法的基本思想
将待求解问题看做一个解空间树, 问题的解可以表示为
X=
<
x
1
,
x
2
,
.
.
.
,
x
n
>
X=<x_1, x_2, …, x_n>
X
=
<
x
1
,
x
2
,
.
.
.
,
x
n
>
,
然后利用深度优先搜索逐步确定每一个解
xi
x_i
x
i
, 当搜索到树的叶子结点时, 就得到问题的一个解
Xi
X_i
X
i
.
当然这个解不一定是最优解,在将整个解空间树搜索完之后,通比较得到的每个
Xi
X_i
X
i
,便可以得到最优解.
其实上面的思想是枚举搜索的思想,并不是回溯法.但是加上下面这一部分就成了回溯法了.
下面这一部分是回溯法的核心
在搜索的过程中, 问题的解
XX
X
需要满足约束条件
P(
X
)
P(X)
P
(
X
)
.
在搜索到一个结点的时候发现当前结点不满足约束条件,则放弃向下搜索,即不再搜索该结点的子结点, 而是回溯到上一个结点继续搜索.
由于在搜索过程中,放弃了一些没有必要搜索的结点,整个算法的效率就提高了.
为什么能够放弃? that is the question.
如果当前结点不满足约束条件,能够推导出它的子结点也不满足约束条件,那么就可以放弃搜索它的子结点.其实这就是多米诺性质.
2.2 多米诺性质的定义
设
X=
<
x
1
,
x
2
,
.
.
.
,
x
n
>
X = <x_1, x_2, …, x_n>
X
=
<
x
1
,
x
2
,
.
.
.
,
x
n
>
是问题的解,
Xi
=
<
x
1
,
x
2
,
.
.
.
,
x
i
>
,
X
i
+
1
=
<
x
1
,
x
2
,
.
.
.
,
x
i
,
x
i
+
1
>
,
X
i
,
X
i
+
1
⊆
X
X_i=<x_1, x_2, …, x_i>, X_{i+1} = <x_1, x_2, …, x_i, x_{i+1}>, X_i, X_{i+1} \subseteq X
X
i
=
<
x
1
,
x
2
,
.
.
.
,
x
i
>
,
X
i
+
1
=
<
x
1
,
x
2
,
.
.
.
,
x
i
,
x
i
+
1
>
,
X
i
,
X
i
+
1
⊆
X
.
Xi
和
X
i
+
1
X_{i}和X_{i+1}
X
i
和
X
i
+
1
分别是搜索到第i层和第i+1层的解.
如果
P(
X
i
+
1
)
→
P
(
X
i
)
P(X_{i+1}) \rightarrow P(X_i)
P
(
X
i
+
1
)
→
P
(
X
i
)
, 即
P(
X
i
+
1
)
P(X_{i+1})
P
(
X
i
+
1
)
蕴含
P(
X
i
)
P(X_i)
P
(
X
i
)
, 则称该问题满足多米诺性质.
是不是很难理解?
数学是个好东西,表达简洁优雅,没有二义性,但是太难理解.
其实上面定义的意思是: 如果子结点满足约束条件能够推导出其父结点满足约束条件,那么就满足多米诺性质.
为什么感觉和之前说的不太一样? 对比一下
- 如果当前结点不满足约束条件,能够推导出它的子结点也不满足约束条件.
- 如果子结点满足约束条件能够推导出其父结点满足约束条件.
你会发现其实这两个命题互为逆否命题,也就是这两个命题说的是同一件事.下面给出证明.(涉及一点数理逻辑的知识,但是逻辑很简单)
[证明]
:
如
果
问
题
满
足
多
米
诺
性
质
,
则
有
P
(
X
i
+
1
)
→
P
(
X
i
)
有
逆
否
命
题
¬
P
(
X
i
)
→
¬
P
(
X
i
+
1
)
成
立
在
当
前
结
点
不
满
足
约
束
条
件
时
,
即
¬
P
(
X
i
)
.
可
得
到
¬
P
(
X
i
+
1
)
成
立
即
当
前
结
点
不
满
足
约
束
条
件
时
,
它
的
子
结
点
也
不
满
足
约
束
条
件
.
\begin{aligned} & 如果问题满足多米诺性质, 则有P(X_{i+1}) \rightarrow P(X_i)\\ & 有逆否命题 \neg P(X_{i}) \rightarrow \neg P(X_{i+1}) 成立\\ & 在当前结点不满足约束条件时, 即\neg P(X_{i}).\\ & 可得到\neg P(X_{i+1})成立\\ & 即当前结点不满足约束条件时, 它的子结点也不满足约束条件. \end{aligned}
如
果
问
题
满
足
多
米
诺
性
质
,
则
有
P
(
X
i
+
1
)
→
P
(
X
i
)
有
逆
否
命
题
¬
P
(
X
i
)
→
¬
P
(
X
i
+
1
)
成
立
在
当
前
结
点
不
满
足
约
束
条
件
时
,
即
¬
P
(
X
i
)
.
可
得
到
¬
P
(
X
i
+
1
)
成
立
即
当
前
结
点
不
满
足
约
束
条
件
时
,
它
的
子
结
点
也
不
满
足
约
束
条
件
.
因此只要求解的问题满足多米诺性质,我们在使用回溯法时, 当发现当前结点不满足约束条件,就可以放弃对其子节点的搜索.
[理解]
:
考察多米诺性质的目的是为了确认, 在对解空间搜索的过程中, 在当前结点不满足约束条件时, 能不能放弃对当前结点的子结点的搜索.如果问题满足多米诺性质,则可以;否则, 不可以, 在这种情况下回溯法可能会丢解.
3 Example
3.1 背包问题
背包问题的描述在这里不进行赘诉.
背包问题的约束条件
-
nn
n
: 物品的数量 -
xi
x_i
x
i
: 表示是否选择该物品 -
wi
w_i
w
i
: 物品的重量 -
CC
C
:背包容量
{
Σ
i
=
1
n
x
i
∗
w
i
≤
C
,
0
<
i
≤
n
x
i
∈
{
0
,
1
}
,
0
<
i
≤
n
w
i
>
0
,
0
<
i
≤
n
\left\{ \begin{aligned} &\Sigma_{i=1}^{n} x_i*w_i \le C, 0 < i \le n\\ &x_i \in \{0,1\}, 0 < i \le n\\ &w_i > 0,0 < i \le n\\ \end{aligned} \right.
⎩
⎪
⎨
⎪
⎧
Σ
i
=
1
n
x
i
∗
w
i
≤
C
,
0
<
i
≤
n
x
i
∈
{
0
,
1
}
,
0
<
i
≤
n
w
i
>
0
,
0
<
i
≤
n
背包问题的多米诺性质
[证明]
:
设
X
i
=
Σ
k
=
1
i
x
k
∗
w
k
,
X
i
+
1
=
Σ
k
=
1
i
+
1
x
k
∗
w
k
∵
X
i
+
1
≤
C
,
w
k
>
0
,
x
k
∈
{
0
,
1
}
∴
X
i
<
X
i
+
1
≤
C
\begin{aligned} & 设X_{i}= \Sigma_{k=1}^{i} x_k*w_k, X_{i+1}= \Sigma_{k=1}^{i+1} x_k*w_k\\ & \because X_{i+1} \le C, w_k > 0, x_k \in \{0,1\}\\ & \therefore X_{i} < X_{i+1} \le C \end{aligned}
设
X
i
=
Σ
k
=
1
i
x
k
∗
w
k
,
X
i
+
1
=
Σ
k
=
1
i
+
1
x
k
∗
w
k
∵
X
i
+
1
≤
C
,
w
k
>
0
,
x
k
∈
{
0
,
1
}
∴
X
i
<
X
i
+
1
≤
C
因此背包问题满足多米诺条件,可以使用回溯法解决.
3.2 不等式的整数解
求解不等式
5∗
x
1
+
4
∗
x
2
−
x
3
≤
10
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
5*x_1 + 4*x_2 – x_3 \le 10, 1 \le x_i \le 3, i=1,2,3
5
∗
x
1
+
4
∗
x
2
−
x
3
≤
1
0
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
的整数解.
这个问题不满足多米诺性质
否则为什么要举这个例子
[证明]
:
当
5
∗
x
1
+
4
∗
x
2
−
x
3
≤
10
成
立
时
显
然
5
∗
x
1
+
4
∗
x
2
≤
10
不
一
定
成
立
\begin{aligned} & 当 5*x_1 + 4*x_2 – x_3 \le 10 成立时 \\ & 显然 5*x_1 + 4*x_2 \le 10 不一定成立\\ \end{aligned}
当
5
∗
x
1
+
4
∗
x
2
−
x
3
≤
1
0
成
立
时
显
然
5
∗
x
1
+
4
∗
x
2
≤
1
0
不
一
定
成
立
因此如果只是这样的话,没办法用回溯法解决.
但也是可以用回溯法解决的.
将不等式
5
∗
x
1
+
4
∗
x
2
−
x
3
≤
10
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
5*x_1 + 4*x_2 – x_3 \le 10, 1 \le x_i \le 3, i=1,2,3
5
∗
x
1
+
4
∗
x
2
−
x
3
≤
1
0
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
修改为
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
10
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
– x_1 + 5*x_2 + 4*x_3 \le 10, 1 \le x_i \le 3, i=1,2,3
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
1
0
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
, 就可以使用回溯法了.
[证明]
:
当
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
10
成
立
时
显
然
−
x
1
+
5
∗
x
2
≤
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
10
成
立
当
−
x
1
+
5
∗
x
2
≤
10
成
立
时
显
然
−
x
1
≤
−
x
1
+
5
∗
x
2
≤
10
成
立
\begin{aligned} & 当 – x_1 + 5*x_2 + 4*x_3 \le 10 成立时 \\ & 显然 – x_1 + 5*x_2 \le – x_1 + 5*x_2 + 4*x_3 \le 10 成立\\ & 当 – x_1 + 5*x_2 \le 10 成立时\\ & 显然 – x_1 \le – x_1 + 5*x_2 \le 10成立\\ \end{aligned}
当
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
1
0
成
立
时
显
然
−
x
1
+
5
∗
x
2
≤
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
1
0
成
立
当
−
x
1
+
5
∗
x
2
≤
1
0
成
立
时
显
然
−
x
1
≤
−
x
1
+
5
∗
x
2
≤
1
0
成
立
因此不等式
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
10
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
-x_1 + 5*x_2 + 4*x_3 \le 10, 1 \le x_i \le 3, i=1,2,3
−
x
1
+
5
∗
x
2
+
4
∗
x
3
≤
1
0
,
1
≤
x
i
≤
3
,
i
=
1
,
2
,
3
满足多米诺性质.