权值之和最小的 Hamilton圈 如果假定城市A是驻地。则推销员从A地出发,第一站有3种选 择:城市B、C或城市D;第一站选定后,第二站有两种选择:如第 一站选定B,则第二站只能选C、D两者之一。当第一、第二两站都 选定时,第三站只有一种选择:比如,当第一、第二两站先后选择了 B和C时,第三站只能选择D。最后推销员由城市D返回驻地A。推 销员所有可能的周游路线可由下面的图反映出来。 例2.定和子集问题:已知一个正实数的集合A={,2…,wn} 和正实数M.试求A的所有子集S,使得S中的数之和等于M 这个问题的解可以表示成0/数组(x1,x2,,xn),依据w是否 属于S,x1分别取值1或0。故解空间中共有2个元素。它的树结构 是一棵完全二叉树 例3.4皇后问题:在4×4棋盘上放置4个皇后,且使得每两个之 间都不能互相攻击,即任意两个皇后都不能放在同一行、同一列及同 对角线上。 将4个皇后分别给以1到4的编号,这个问题的解决就是要安排 4个皇后的位置。因而,每个决策序列由4个决策组成:P1,P2,P3, P4,这里P代表安排第k个皇后的位置,因而有16种可能。该问题 的解空间有164个决策序列。这时的约束条件是:任意两个皇后均不 能位于同一行、同一列及同一个对角线上。注意到这个解空间比较大, 从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不 在同一行”也放在问题中考虑,即:将4个皇后放在4×4棋盘的不权值之和最小的 Hamilton 圈。 如果假定城市 A 是驻地。则推销员从 A 地出发，第一站有 3 种选 择：城市 B、C 或城市 D；第一站选定后，第二站有两种选择：如第 一站选定 B，则第二站只能选 C、D 两者之一。当第一、第二两站都 选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了 B 和 C 时，第三站只能选择 D。最后推销员由城市 D 返回驻地 A。推 销员所有可能的周游路线可由下面的图反映出来。 例 2．定和子集问题：已知一个正实数的集合 { , , , } A = w 1 w2 L wn 和正实数 M．试求 A 的所有子集 S，使得 S 中的数之和等于 M。 这个问题的解可以表示成 0/1 数组(x1, x2, . . . , xn )，依据 wi是否 属于 S，xi分别取值 1 或 0。故解空间中共有 2n个元素。它的树结构 是一棵完全二叉树。 例 3．4 皇后问题: 在 4×4 棋盘上放置 4 个皇后，且使得每两个之 间都不能互相攻击，即任意两个皇后都不能放在同一行、同一列及同 一对角线上。 将 4 个皇后分别给以 1 到 4 的编号，这个问题的解决就是要安排 4 个皇后的位置。因而，每个决策序列由 4 个决策组成：P1，P2，P3， P4，这里 Pk代表安排第 k 个皇后的位置，因而有 16 种可能。该问题 的解空间有 164个决策序列。这时的约束条件是: 任意两个皇后均不 能位于同一行、同一列及同一个对角线上。注意到这个解空间比较大， 从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不 在同一行” 也放在问题中考虑，即：将 4 个皇后放在 4×4 棋盘的不