山东程子太军 5.1.1问题的解空间 HANDONG UNIVERSITY OF TECHNOLOOY 会会空会的不空3会华是 ●为了用回溯法求解一个具有个输入的问题，一般情况 下，将其可能解表示为满足某个约束条件的等长向量 X=(x,2,x,其中分量x(1≤in)的取值范围是某个有 限集合S={a,az,and,所有可能的解向量构成了问题 的解空间。 ●问题的解空间一般用解空间树(Solution Space Trees,也 称状态空间树)的方式组织，树的根结点位于第1层，表 示搜索的初始状态，第2层的结点表示对解向量的第一个 分量做出选择后到达的状态，第1层到第2层的边上标出 对第一个分量选择的结果，依此类推，从树的根结点到 叶子结，点的路径就构成了解空间的一个可能解。 2025年4月3日 16
2025年4月3日 16 5.1.1 问题的解空间 ⚫ 为了用回溯法求解一个具有n个输入的问题，一般情况 下，将其可能解表示为满足某个约束条件的等长向量 X=(x1 , x2 , ., xn )，其中分量xi (1≤i≤n)的取值范围是某个有 限集合Si={ai1, ai2, ., airi}，所有可能的解向量构成了问题 的解空间。 ⚫ 问题的解空间一般用解空间树（Solution Space Trees,也 称状态空间树）的方式组织，树的根结点位于第1层，表 示搜索的初始状态，第2层的结点表示对解向量的第一个 分量做出选择后到达的状态，第1层到第2层的边上标出 对第一个分量选择的结果，依此类推，从树的根结点到 叶子结点的路径就构成了解空间的一个可能解
5.1.1问题的解空间 归东程子末军 SHANDONG UNIVERSITY OF TECHNOLOGY 1.背包问题 ●对于=3的0/1背包问题，其解空间树如下图所示， 树中的8个叶子结，点分别代表该问题的8个可能 解。 对物品1的选择 0 对物品2的选择 10 3 对物品3的选择 2025年4月3日
2025年4月3日 17 5.1.1 问题的解空间 1.背包问题 ⚫ 对于n=3的0/1背包问题，其解空间树如下图所示， 树中的8个叶子结点分别代表该问题的8个可能 解。 对物品1的选择 对物品3的选择 对物品2的选择 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 2 3 4 5 7 8 11 12 14 15 6 10 3 9
山东程子太军 2旅行售货员问题 HANDONG UNIVERSITY OF TECINOLOGY 会是33☆ ● 问题描述：某售货员 要到若干城市去推销 30 商品，已知各城市之 间的路程，他要选定 10 一 条从驻地出发，经 4 3 过每个城市一遍，最 20 后回到住地的路线， 使总的路程最短。 ● 该问题是一个NP完 2 B 全问题，有(n-1)1条 4 可选路线 C D 最优解(1,3,2,4,1)， 3 24 2 最优值25 F G 4 3 4 2 2 M P 2025年4月3日 18
2025年4月3日 18 2 旅行售货员问题 ⚫ 问题描述：某售货员 要到若干城市去推销 商品，已知各城市之 间的路程，他要选定 一条从驻地出发，经 过每个城市一遍，最 后回到住地的路线， 使总的路程最短。 ⚫ 该问题是一个NP完 全问题，有(n-1)!条 可选路线 ⚫ 最优解(1,3,2,4,1)， 最优值25 1 2 3 4 20 6 30 5 4 10 A B C D E F G H I J K L M N O P Q 1 2 3 4 3 4 4 3 4 2 3 2 2 4 2 3
归东程子末军 5.1.2回溯法的基本思想 SHANDONG UNIVERSITY OF TECHNOLOGY 华器会空空合安会空会的会 ●1 回溯法从根结点出发，按照深度优先策略搜索（遍 历)解空间树，搜索满足约束条件的解。 ● 初始时，根结点成为一个活结点，同时也称为当前 的扩展结点。在当前扩展结，点处，搜索向纵深方向 移至一个新结，点。这个新结点成为一个新的活结点， 并成为当前的扩展结点。如果在当前的扩展结，点处 不能再向纵深方向移动，则当前的扩展结点就成为 一个死结点（即不再是一个活节点)。此时，应往 回移动（回溯)至最近的一个活结点处，并使这个 活结点成为当前的扩展结，点。 2025年4月3日 19
2025年4月3日 19 5.1.2 回溯法的基本思想 ⚫ 回溯法从根结点出发，按照深度优先策略搜索（遍 历）解空间树，搜索满足约束条件的解。 ⚫ 初始时，根结点成为一个活结点，同时也称为当前 的扩展结点。在当前扩展结点处，搜索向纵深方向 移至一个新结点。这个新结点成为一个新的活结点， 并成为当前的扩展结点。如果在当前的扩展结点处 不能再向纵深方向移动，则当前的扩展结点就成为 一个死结点（即不再是一个活节点）。此时，应往 回移动（回溯）至最近的一个活结点处，并使这个 活结点成为当前的扩展结点
山东程子太置 SHANDONG UNIVERSITY OF TECINOLOGY 华5空空实是子3分是，京☆ 。 扩展结点：一个正在产生儿子的结点称为扩展结点。 活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结 点。 死结点：一个所有儿子已经产生的结点称做死结点。 活结点 扩展结点 0 死结点 F 0 20
20 死结点 扩展结点 活结点 • 扩展结点:一个正在产生儿子的结点称为扩展结点。 • 活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结 点。 • 死结点:一个所有儿子已经产生的结点称做死结点