5
问题的解空间 (solution
space)
•
问题的解向量:回溯法希望一个问题的解能够表示成一个 n
元式 (x1,x2,…,xn) 的形式。
•
显约束:对分量 xi 的取值限定。
•
隐约束:为满足问题的解而对不同分量之间施加的约束。
•
解空间:对于问题的一个实例,解向量满足显式约束条件的
所有多元组,构成了该实例的一个解空间。
例: n=3 时 0-1 背包问题的解空间
( 0 , 0 , 0 )( 0 , 0 , 1 )( 0 , 1 , 0 )( 0 , 1 ,
1 )( 1 , 0 , 0 )
( 1 , 0 , 1 )( 1 , 1 , 0 )( 1 , 1 , 1 )