回溯法的多米诺性质

  • Post author:
  • Post category:其他


最近在复习算法,

没办法,要考试啦

. 在复习回溯法的时候终于理解了之前不是很清楚的多米诺性质.



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




















>





,

然后利用深度优先搜索逐步确定每一个解



x

i

x_i







x










i





















, 当搜索到树的叶子结点时, 就得到问题的一个解



X

i

X_i







X










i





















.

当然这个解不一定是最优解,在将整个解空间树搜索完之后,通比较得到的每个



X

i

X_i







X










i





















,便可以得到最优解.

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

下面这一部分是回溯法的核心

在搜索的过程中, 问题的解



X

X






X





需要满足约束条件



P

(

X

)

P(X)






P


(


X


)





.

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

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


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

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



2.2 多米诺性质的定义





X

=

&lt;

x

1

,

x

2

,

.

.

.

,

x

n

&gt;

X = &lt;x_1, x_2, …, x_n&gt;






X




=






<









x










1


















,





x










2


















,




.


.


.


,





x










n




















>





是问题的解,




X

i

=

&lt;

x

1

,

x

2

,

.

.

.

,

x

i

&gt;

,

X

i

+

1

=

&lt;

x

1

,

x

2

,

.

.

.

,

x

i

,

x

i

+

1

&gt;

,

X

i

,

X

i

+

1

X

X_i=&lt;x_1, x_2, …, x_i&gt;, X_{i+1} = &lt;x_1, x_2, …, x_i, x_{i+1}&gt;, 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





.




X

i

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} &amp; 如果问题满足多米诺性质, 则有P(X_{i+1}) \rightarrow P(X_i)\\ &amp; 有逆否命题 \neg P(X_{i}) \rightarrow \neg P(X_{i+1}) 成立\\ &amp; 在当前结点不满足约束条件时, 即\neg P(X_{i}).\\ &amp; 可得到\neg P(X_{i+1})成立\\ &amp; 即当前结点不满足约束条件时, 它的子结点也不满足约束条件. \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 背包问题

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

背包问题的约束条件




  1. n

    n






    n





    : 物品的数量




  2. x

    i

    x_i







    x










    i





















    : 表示是否选择该物品




  3. w

    i

    w_i







    w










    i





















    : 物品的重量




  4. C

    C






    C





    :背包容量





{

Σ

i

=

1

n

x

i

w

i

C

,

0

&lt;

i

n

x

i

{

0

,

1

}

,

0

&lt;

i

n

w

i

&gt;

0

,

0

&lt;

i

n

\left\{ \begin{aligned} &amp;\Sigma_{i=1}^{n} x_i*w_i \le C, 0 &lt; i \le n\\ &amp;x_i \in \{0,1\}, 0 &lt; i \le n\\ &amp;w_i &gt; 0,0 &lt; 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

&gt;

0

,

x

k

{

0

,

1

}

X

i

&lt;

X

i

+

1

C

\begin{aligned} &amp; 设X_{i}= \Sigma_{k=1}^{i} x_k*w_k, X_{i+1}= \Sigma_{k=1}^{i+1} x_k*w_k\\ &amp; \because X_{i+1} \le C, w_k &gt; 0, x_k \in \{0,1\}\\ &amp; \therefore X_{i} &lt; 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} &amp; 当 5*x_1 + 4*x_2 – x_3 \le 10 成立时 \\ &amp; 显然 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} &amp; 当 – x_1 + 5*x_2 + 4*x_3 \le 10 成立时 \\ &amp; 显然 – x_1 + 5*x_2 \le – x_1 + 5*x_2 + 4*x_3 \le 10 成立\\ &amp; 当 – x_1 + 5*x_2 \le 10 成立时\\ &amp; 显然 – 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





满足多米诺性质.



版权声明:本文为yx1302317313原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。