子集和数问题解的另一种表达 解由n元组(X1,x2,…,X)表示; 显式约束条件x∈{0,1},1≤≤n,如果没有 选择W,则x=0;如果选择了W,则x=1 于是上面的解可以表示为(1,1,0,1和 (0,0,1,1); 隐式约束条件(x1×W)的和数为M 解空间的大小为2n个元组
子集和数问题解的另一种表达 解由n-元组(x1 , x2 , …, xn )表示; 显式约束条件xi∈{0,1} ，1≤i≤n，如果没有 选择Wi，则xi=0；如果选择了Wi，则xi=1。 于是上面的解可以表示为(1，1，0，1)和 (0,0,1,1); 隐式约束条件(xi × wi )的和数为M 解空间的大小为2 n个元组
解空间的树结构 回溯算法通过系统地检索给定问题的解空间来确定问题的解。 这检索可以用这个解空间的树结构来简化。 为了便于讨论,引进一些关于解空间树结构的术语。 问题状态( problem state):树中的每一个结点确定所求解问 题的一个问题状态。 状态空间( state space):由根结点到其它节点的所有路径则 确定了这个问题的状态空间。 解状态( solution states):解状态是这样一些问题状态S,对 于这些问题状态,由根到S的那条路径确定了这解空间中的一 元组 *答案状态( answer states):对于这些解状态而言,由根到S的 这条路径确定了这问题的一个解(即,它满足隐式约束条件)。 状态空间树( state space tree):解空间的树结构
解空间的树结构 回溯算法通过系统地检索给定问题的解空间来确定问题的解。 这检索可以用这个解空间的树结构来简化。 为了便于讨论，引进一些关于解空间树结构的术语。 ﹡问题状态(problem state)：树中的每一个结点确定所求解问 题的一个问题状态。 ﹡状态空间(state space)：由根结点到其它节点的所有路径则 确定了这个问题的状态空间。 ﹡解状态(solution states)：解状态是这样一些问题状态S，对 于这些问题状态，由根到S的那条路径确定了这解空间中的一 个元组。 ﹡答案状态(answer states)：对于这些解状态而言，由根到S的 这条路径确定了这问题的一个解(即，它满足隐式约束条件)。 ﹡状态空间树(state space tree)：解空间的树结构
◎静态树:树结构与所求问题的实例无关, 结构不变的解空间树 动态树:树结构是动态变化的,与所求问 题有关。即,具体问题的数据发生变化, 空间树的结构也会发生变化。 ◎组织空间树就是根据元组的特点构造解空 间
静态树：树结构与所求问题的实例无关， 结构不变的解空间树 动态树： 树结构是动态变化的，与所求问 题有关。即，具体问题的数据发生变化， 空间树的结构也会发生变化。 组织空间树就是根据元组的特点构造解空 间