回溯(屈婉玲)下载_在线阅读_38

is_634028

暂无简介

回溯(屈婉玲) 1 回溯（backtrack）回溯算法的基本思想和适用条件回溯算法的设计步骤估计回溯算法的效率改进回溯算法的途径分支估界应用实例 2 基本思想和适用条件实例基本思想搜索问题搜索空间搜索策略判定条件结点状态存储结构必要条件 3 实例1: 四后问题解表示成一个4维向量，（放置列号）搜索空间：4叉树 4 V={12,11,9,8}, W={8,6,4,3}, B=13 结点：向量（子集的部分特征向量）搜索空间：子集树...

1 回溯（backtrack）回溯算法的基本思想和适用条件回溯算法的

设计

领导形象设计圆作业设计 ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计

步骤估计回溯算法的效率改进回溯算法的途径分支估界应用实例 2 基本思想和适用条件实例基本思想搜索问

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

搜索空间搜索策略判定条件结点状态存储结构必要条件 3 实例1: 四后问题解

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf 视力表打印pdf 用图表说话 pdf

示成一个4维向量，（放置列号）搜索空间：4叉树 <1> <4> <2,4> <2,4,1> <2,4,1,3> 4 V={12,11,9,8}, W={8,6,4,3}, B=13 结点：向量（子集的部分特征向量）搜索空间：子集树，2n片树叶 <0,1,1,1> 可行解： x1=0, x2=1, x3=1, x4=1. 重量：13, 价值：28 <1,0,1,0>可行解： x1=1, x2=0, x3=1, x4=0. 重量：12，价值：21 实例2：0-1背包问题 <1> <0> <1,0,1,0> <0,1,1,1> 5 <1,2,4,3> 对应于巡回路线：1→2 →4 →3 →1 长度：5+2+7+9=23 实例3：货郎担问题 <1> <1,2> <1,4> <1,2,4,3> 1 2 3 4 5 24 9 7 13 为巡回路线搜索空间：排列树, (n-1)!片树叶 6 基本思想适用问题：求解搜索问题搜索空间：树，结点对应部分解向量，树叶对应可行解搜索过程：采用系统的

方法

快递客服问题件处理详细方法山木方法pdf 计算方法pdf 华与华方法下载八字理论方法下载

隐含遍历搜索树搜索策略：深度优先，宽度优先，函数优先，宽深结合等结点分支判定条件：满足约束条件---分支扩张解向量不满足约束条件，回溯到该结点的父结点结点状态：动态生成白结点(尚未访问)；灰结点(正在访问该结点为根的子树); 黑结点(该结点为根的子树遍历完成) 存储：当前路径 7 设 P(x1, x2, …, xi) 为真表示向量中i 个皇后放置在彼此不能攻击的位置例4 求不等式的整数解 5x1+4x2−x3 ≤ 10, 1 ≤ xi ≤ 3, i=1,2,3 P(x1, …, xk) : 意味将x1, x2, … , xk代入原不等式的相应部分使得左边小于等于10 不满足多米诺性质变换：令 x3=3 −x3’, 5x1+4x2+x3’ ≤ 13 ，1 ≤ x1, x2 ≤ 3, 0 ≤ x3’≤ 2 nkxxxPxxxP kk <<→+ 0),...,,(),...,,( 21121 必要条件：多米诺性质 8 回溯算法的设计要素定义搜索问题的解向量和每个分量的取值范围解向量为确定 xi 的可能取值的集合为 Xi , i = 1, 2, … , n. 当 x1, x2, … , xk-1 确定以后计算 xk取值集合Sk, Sk ⊆ Xk 确定结点儿子的排列规则判断是否满足多米诺性质搜索策略----深度优先、宽度优先等确定每个结点分支约束条件确定存储搜索路径的数据结构 9 算法 ReBack(k) 1. if k>n then 是解 2. else while Sk ≠ ∅ do 3. xk←Sk中最小值 4. Sk←Sk–{xk} 5. 计算Sk+1 6. ReBack(k+1) 算法 ReBacktrack(n) 1. for k←1 to n 计算 Xk 2. ReBack(1) 递归实现 10 迭代算法 Backtrack 1. 对于i =1, 2, … , n 确定Xi 2. k←1 3. 计算Sk 4. while Sk ≠ ∅ do 5. xk←Sk中最小值; Sk←Sk–{xk} 6. if k是解 9. if k>1 then k←k-1； goto 4 迭代实现 11 估计回溯算法的平均效率计数搜索树中平均遍历的结点，Monte Carlo方法 Monte Carlo方法 1．从根开始，随机选择一条路经，直到不能分支为止, 即从x1,x2,…, 依次对xi 赋值，每个xi 的值是从当时的 Si中随机选取，直到向量不能扩张为止. 2．假定搜索树的其他 | Si | −1 个分支与以上随机选出的路径一样，计数搜索树的点数. 3．重复步骤 1 和 2，将结点数进行概率平均. 12 Monte Carlo 1．sum ← 0 //sum为 t 次结点平均数 2．for i ←1 to t do //取样次数 t 3. m ← Estimate(n) //m为本次结点总数 4. sum ← sum + m 5. sum ← sum / t 算法实现 13 m为输出——本次取样结点总数，k 为层数，r1为本层分支数, r2为上层分支数，n为树的层数算法Estimate(n) 1. m←1; r2←1; k←1 //m为结点总数 2. While k ≤ n do 3. if Sk=∅ then return m 4. r1 ← |Sk|*r2 //r1为扩张后结点总数 5. m ← m + r1 // r2为扩张前结点总数 6. xk←随机选择 Sk的元素 7. r2 ← r1 8. k ← k+1 计算结点数 14 例5 估计四后问题的效率 case1．<1,4,2>：1+4+4×2+4×2=21 case2．<2,4,1,3>: 4×4+1=17 case3．<1,3>：1+4×1+4×2=13 实例 Case3: <1,3> Case1: <1,4,2> Case2: <2,4,1,3> 15 估计效率假设 4 次抽样测试： case1:1次，case2:1次，case3:2次，平均结点数＝(21×1+17×1+13×2)/4=16 搜索空间访问的结点数为17 搜索空间 16 影响算法效率的因素最坏情况下的时间W(n)=(p(n)f(n)) 其中 p(n) 为每个结点时间，f(n)为结点个数影响回朔算法效率的因素搜索树的结构分支情况：分支均匀否树的深度对称程度：对称适合裁减解的分布在不同子树中分布多少是否均匀分布深度约束条件的判断：计算简单 17 根据树分支设计优先策略：结点少的分支优先，解多的分支优先利用搜索树的对称性剪裁子树分解为子问题: 求解时间 f(n)=c2n，组合时间T=O(f(n)) 如果分解为 k 个子问题，每个子问题大小为 n/k 求解时间为 Tkc k n +2 改进途径 18 4,3,2,1, 107432 953max 4321 4321 =∈ ≤+++ +++ iNx xxxx xxxx i 组合优化问题相关概念目标函数（极大化或极小化）约束条件搜索空间中满足约束条件的解称为可行解使得目标函数达到极大(或极小)的解称为最优解实例：背包问题 19 分支估界技术（极大化）设立代价函数函数值以该结点为根的搜索树中的所有可行解的目标函数值的上界父结点的代价不小于子结点的代价设立界代表当时已经得到的可行解的目标函数的最大值界的设定初值可以设为0 可行解的目标函数值大于当时的界，进行更新搜索中停止分支的依据不满足约束条件或者其代价函数小于当时的界 20 背包问题的实例： 4,3,2,1,N 107432 953max 4321 4321 =∈ ≤+++ +++ ix xxxx xxxx i 对变元重新排序使得 1 1 + +≥ i i i i w v w v 4,3,2,1,N 102347 359max 4321 4321 =∈ ≤+++ +++ ix xxxx xxxx i 实例：背包问题 21 的代价函数否则有若对某个 ∑ ∑ ∑∑ = = = + + = ≥−> −+ k i ii j k i ii k i k k ii k i ii xv wxwbkj w v xwbxv 1 1 1 1 1 1 )( 分支策略----深度优先代价函数与分支策略确定 22 8 3/3210 ⋅+ x2=2 7 3/339 ⋅+ 0 4,3,2,1,N,102347 359max 4321 4321 =∈≤+++ +++ ixxxxx xxxx i 0 7/910 ⋅ 7 4/539 ⋅+ x1=1 15 x2=2 11 1 16 x2=3 13 2 7 2/139 ⋅+ 0 10 12 1 0 4/510 ⋅ x1=0 4 3/365 ⋅+ 1 0 3/310 ⋅ 0 w v实例 23 最大团问题问题：给定无向图G=, 求G中的最大团. 相关知识：无向图G = , G的子图：G’= , 其中V’⊆V, E’⊆E, G的补图：Ğ =, E’是E关于完全图边集的补集 G中的团：G 的完全子图 G 的点独立集：G 的顶点子集A，且∀u,v∈A, {u,v}∉E. 最大团：顶点数最多的团最大点独立集：顶点数最多的点独立集命题：U是G 的最大团当且仅当U是Ğ的最大点独立集 24 结点的含义：已检索 k 个顶点，其中 xi=1 对应的顶点在当前的团内搜索树为子集树约束条件：该顶点与当前团内每个顶点都有边相连界：当前图中已检索到的极大团的顶点数代价函数：目前的团扩张为极大团的顶点数上界 F = Cn+n−k 其中 Cn 为目前团的顶点数（初始为0）， k 为结点层数时间：O(n2n) 算法设计 25 2 3 5 1 4 顶点编号顺序为 1, 2, 3, 4, 5, 对应 x1, x2, x3, x4, x5, xi=1 当且仅当 i 在团内分支规定左子树为1，右子树为0. B 为界，F 为代价函数值. 最大团的实例 26 a：得第一个极大团 { 1, 2, 4 }, 顶点数为3, 界为3； b：代价函数值 F = 3, 回溯； c：得第二个极大团{1, 3, 4, 5}, 顶点数为4, 修改界为4； d：不必搜索其它分支, 因为F = 4, 不超过界； e：F = 4, 不必搜索. 最大团为 {1, 3, 4, 5}, 顶点数为 4. 2 3 5 1 4 实例求解 a,B=3 b,F=3 c,B=4 d,F=3 e,F=4 27 图的m着色给定无向连通图G和m种颜色，给图的顶点着色，每个顶点一种颜色，且每条边的两个顶点不同色。给出所有可能的着色

方案

气瓶现场处置方案 .pdf 气瓶现场处置方案 .doc 见习基地管理方案.doc 关于群访事件的化解方案建筑工地扬尘治理专项方案下载

（如果不存在，则回答“No” ）搜索空间为m叉完全树. 将颜色编号为1, 2, … , m. 结点表示顶点1着色 x1,顶点2着色 x2, … , 顶点 k 着色 xk 约束条件：该顶点邻接表中已着色的顶点没有同色的代价函数：没有（不是优化问题）时间：O(nmn) 28 实例 <1> <1,2> <1,2,1> <1,2,1,3> <1,2,1,3,1> <1,2,1,3,1,2> <1,2,1,3,1,2,3> 1 2 3 32 1 3 1 2 3 1 2 1 3 2 29 提高效率的途径根据对称性，只需搜索1/3的解空间即可. 当1和2确定,即 <1,2>以后，只有1个解，因此在<1,3>为根的子树中也只有 1个解.由于3个子树的对称性，总共有6个解. 进一步分析，在取定<1,2>以后，不可以扩张成<1,2,3>, 因为可以检查是否有和1,2,3都相邻的顶点.如果存在,例如7, 则没有解. 所以可以从打叉的结点回溯，而不必搜索它的子树. 30 货郎担问题问题：给定n个城市集合C={c1,c2,…,cn}, 从一个城市到另一个城市的距离 dij 为正整数，求一条最短且每个城市恰好经过一次的巡回路线. 巡回售货员问题的类型：有向图、无向图. 设巡回路线从1开始，解向量为, 其中 i1, i2, … , in-1为{ 2, 3, … , n }的排列. 搜索空间为排列树，结点表示得到 k 步巡回路线 31 ∑∑ ∉= += Bi i k j j j j ldL 1 为部分巡回路线扩张成全程巡回路线的长度下界时间 O(n!)：计算O((n−1)!)次，代价函数计算O(n) 约束条件：令B = { i1, i2, … , ik }, 则 ik+1∈{ 2, … , n }−B 界：当前得到的最短巡回路线长度代价函数：设顶点 ci 出发的最短边长度为 li，dj 为选定巡回路线中第 j 段的长度，则算法设计 32 圆排列问题给定n个圆的半径序列, 将各圆与矩形底边相切排列, 求具有最小长度 ln的圆的排列顺序. 解为为1, 2, … , n的排列，解空间为排列树. 部分解向量：表示前 k 个圆已排好. 令B={ i1, i2, … , ik },下一个园选择ik+1. 约束条件：ik+1∈{1, 2, … , n}−B 界：当前得到的最小园排列长度 33 k：算法完成第 k 步，已经选择了第1— k 个圆 rk：第 k 个圆的半径 dk：第 k−1 个圆到第 k 个圆的圆心水平距离，k>1 xk：第 k 个圆的圆心坐标，规定 x1=0, lk：第 1— k 个圆的排列长度 Lk：放好 1—k 个圆以后，对应结点的代价函数值 Lk≤ ln 代价函数符号说明 34 11211 121 2...22 ... rrrrrrrrx rrdddxL nnnkkkkk nnkkkk ++++++= ++++++= −+++ ++ 11 1 2 1 2 1 , 2)()( rrxldxx rrrrrrd kkkkkk kkkkkkk ++=+= =−−+= − −−− 有关量的计算 r1 xk dk+1 rk rk+1 dk+2 dn rn rk rk+1 … … 35 Bnirrr rrknx rrrknx rrrrrrrrxL jki k k nnnkkkkkk j −∈= ++−+= ++−+≥ ++++++= −+++ },...,2,1{),min( )122( )(2 2...22 1 1 11211 时间：O(n n!)=O((n+1)!) B = { i1, i2, … , ik }, 代价函数 36 R = {1, 1, 2, 2, 3, 5} 取排列 <1, 2, 3, 4, 5, 6>, 半径排列为：1, 1, 2, 2, 3, 5，结果见下表和下图 27.427.421.47.756 23.717.713.74.935 19.811.88.8424 19.87.84.82.823 1242212 1220011 Lklkxkdkrkk 实例：计算过程 37 R = {1, 1, 2, 2, 3, 5 } 取排列 <1, 2, 3, 4, 5, 6>, 半径排列为: 1, 1, 2, 2, 3, 5，最短长度 l6 = 27.4 实例：图示 d6d5d4d3d2r1 0 2 4.8 8.8 13.7 21.4 26.4 38 回溯算法小结适应于求解组合搜索问题（含组合优化问题）求解条件：满足多米诺性质解的表示：解向量，求解是不断扩充解向量的过程回溯条件：搜索问题-约束条件优化问题-约束条件+代价函数算法复杂性：最坏情况为指数，空间代价小平均时间复杂性的估计：Monte Carlo方法降低时间复杂性的主要途径：利用对称性裁减子树，划分成子问题分支策略（深度优先、宽度优先、宽深结合、优先函数）

本文档为【回溯(屈婉玲)】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

回溯(屈婉玲)

热门搜索

历史搜索