清华大学出版社 问题的解空间 问题的解向量:回溯法希望一个问题的解能够表示成一个n 元式(x1,x2,…,xn)的形式。 显约束:对分量xi的取值限定。 ·隐约束:为满足问题的解而对不同分量之间施加的约束。 ·解空间:对于问题的一个实例,解向量满足显式约束条件的 所有多元组,构成了该实例的一个解空间。 注意:同一个问题可以有多种表示,有些表示方法更简单 所需表示的状态空间更小(存储量少,搜索方法简单)。 n=3时的0-1背包问题用完全二叉树表示的解空间33 问题的解空间 • 问题的解向量：回溯法希望一个问题的解能够表示成一个n 元式(x1,x2,…,xn)的形式。 • 显约束：对分量xi的取值限定。 • 隐约束：为满足问题的解而对不同分量之间施加的约束。 • 解空间：对于问题的一个实例，解向量满足显式约束条件的 所有多元组，构成了该实例的一个解空间。 注意：同一个问题可以有多种表示，有些表示方法更简单， 所需表示的状态空间更小（存储量少，搜索方法简单）。 n=3时的0-1背包问题用完全二叉树表示的解空间