最近在复习算法, 没办法,要考试啦. 在复习回溯法的时候终于理解了之前不是很清楚的多米诺性质.

目录

1. 1 回溯法
2. 2 多米诺性质
   1. 2.1 回溯法的基本思想
   2. 2.2 多米诺性质的定义
3. 3 Example
   1. 3.1 背包问题
      1. 背包问题的多米诺性质
   2. 3.2 不等式的整数解

1 回溯法

由于这篇博客主要讲解多米诺性质, 默认大家已经了解回溯法啦,这里对回溯法的具体内容就不进行讲解了,其实是太懒不想写.

回溯法是一个很实用的算法,适合求解搜索问题和优化问题.你也可以将它看做是蛮力法(枚举法)的改进.

但不是什么情况下都可以使用回溯法, 那么就要问了,回溯法的适用条件是什么? 这就是今天的主角: 多米诺性质

2 多米诺性质

先不看多米诺性质是什么,在了解了回溯法的基本思想后,我们可以总结一下什么情况下可以使用回溯法.

2.1 回溯法的基本思想

将待求解问题看做一个解空间树, 问题的解可以表示为.
然后利用深度优先搜索逐步确定每一个解, 当搜索到树的叶子结点时, 就得到问题的一个解.
当然这个解不一定是最优解,在将整个解空间树搜索完之后,通比较得到的每个,便可以得到最优解.

其实上面的思想是枚举搜索的思想,并不是回溯法.但是加上下面这一部分就成了回溯法了. 下面这一部分是回溯法的核心

在搜索的过程中, 问题的解需要满足约束条件.
在搜索到一个结点的时候发现当前结点不满足约束条件,则放弃向下搜索,即不再搜索该结点的子结点, 而是回溯到上一个结点继续搜索.

由于在搜索过程中,放弃了一些没有必要搜索的结点,整个算法的效率就提高了.

为什么能够放弃? that is the question.

如果当前结点不满足约束条件,能够推导出它的子结点也不满足约束条件,那么就可以放弃搜索它的子结点.其实这就是多米诺性质.

2.2 多米诺性质的定义

设是问题的解,

. 分别是搜索到第i层和第i+1层的解.

如果 , 即 蕴含 , 则称该问题满足多米诺性质.

是不是很难理解?数学是个好东西,表达简洁优雅,没有二义性,但是太难理解.

其实上面定义的意思是: 如果子结点满足约束条件能够推导出其父结点满足约束条件,那么就满足多米诺性质.

为什么感觉和之前说的不太一样? 对比一下

• 如果当前结点不满足约束条件,能够推导出它的子结点也不满足约束条件.
• 如果子结点满足约束条件能够推导出其父结点满足约束条件.

你会发现其实这两个命题互为逆否命题,也就是这两个命题说的是同一件事.下面给出证明.(涉及一点数理逻辑的知识,但是逻辑很简单)

[证明]:

因此只要求解的问题满足多米诺性质,我们在使用回溯法时, 当发现当前结点不满足约束条件,就可以放弃对其子节点的搜索.

[理解]:

考察多米诺性质的目的是为了确认, 在对解空间搜索的过程中, 在当前结点不满足约束条件时, 能不能放弃对当前结点的子结点的搜索.如果问题满足多米诺性质,则可以;否则, 不可以, 在这种情况下回溯法可能会丢解.

3 Example

3.1 背包问题

背包问题的描述在这里不进行赘诉.

背包问题的约束条件

1. : 物品的数量
2. : 表示是否选择该物品
3. : 物品的重量
4. :背包容量

背包问题的多米诺性质

[证明]:

因此背包问题满足多米诺条件,可以使用回溯法解决.

3.2 不等式的整数解

求解不等式 的整数解.

这个问题不满足多米诺性质否则为什么要举这个例子

[证明]:

但也是可以用回溯法解决的.

将不等式 修改为 , 就可以使用回溯法了.

[证明]:

因此不等式满足多米诺性质.