• 形式化描述：对于给定的正整数集合S = { x1, x2, …, xn }和正整数c，求向量P = ( p1, p2, …, pn )，其中pi ∈ { 0, 1 }，使得∑x∈S1,p∈P xi×pi = c （约束条件）。
已知集合S = { 2,2,6,5,4 }，c=10。求所有可能子集。
0
1 …… ……
最终结果： 1. ( 0, 0, 1, 0, 1 ) 2. ( 1, 1, 1, 0, 0 )
2 0
0 0
3 1
1
4Leabharlann 110 15
0 1 0
8
1 0
×
12
1 0
6
7
9
10 13
14
End
1. 给出该问题的形式化描述。 2. 利用回溯法深度搜索解空间树，利用剪枝函 数求其所有解，要求画出其实际生成的解空 间树（即要标出被剪枝的部分）。
子集和问题
• 问题描述：子集和问题的一个实例为< S, t >。其 中，S = { x1, x2, …, xn }是一个正整数的集合，c是 一个正整数。子集和问题判定是否存在S的一个子 集S1，使得∑x∈S1x = c。 • 形式化描述：对于给定的正整数集合S = { x1, x2, …, xn }和正整数c，求向量P = { p1, p2, …, pn }， 其中pi ∈ { 0, 1 }，使得∑x∈S1,p∈P xi×pi = c。
课后练习：第5章 回溯法
• 练习1：6皇后问题。
1. 给出该问题的形式化描述。
2. 利用回溯法深度搜索解空间树，利用剪枝函数求 其所有布局，要求画出其实际生成的解空间树 （即要标出被剪枝的部分）。
6皇后问题
6皇后问题形式化描述： • Si = { 0, 1, 2, 3, 4, 5 }，0≤i<5，且xi≠xj(0≤i,j<5 ,i≠j)。 • 相应的隐式约束为：对任意0≤i,j<5 ，当i≠j时，|i-j|≠|xi-xj| 。 • 与此相对应的解空间大小为6!。
• 回溯法：为了避免生成那些不可能产生最佳解的 问题状态，要不断地利用限界函数（隐式约束） 来处死那些实际上不可能产生所需解的活结点， 以减少问题的计算量。具有限界函数的深度优先 生成法称为回溯法。
6皇后问题形式化描述： • Si = { 0, 1, 2, 3, 4, 5 }，0≤i<5，且xi≠xj(0≤i,j<5 ,i≠j)。 • 相应的隐式约束为：对任意0≤i,j<5 ，当i≠j时，|i-j|≠|xi-xj| 。 • 与此相对应的解空间大小为6!。 0 1 × 1 A
对0号皇后位置的选择 对1号皇后位置的选择 对2号皇后位置的选择
۩ ۩ ۩ ۩ ۩ ۩ 非可行解！
B 2
C 4 3 × × 1 D E 3 F 5 F
对3号皇后位置的选择
对4号皇后位置的选择 对5号皇后位置的选择
课后练习
•
•
练习2：教材 算法实现题5-1 子集和问题。
已知集合S = { 2,2,6,5,4 }，c=10。求所有可能 子集。要求：