算法设计 |
您所在的位置:网站首页 › 问题空间的概念 › 算法设计 |
回溯法
适用于解一些组合数相当大的问题 策略: 深度优先策略 从根节点出发搜索解空间树 到任一点时: 1.先判断是否包含问题的解 2.如果不包含,则跳过对该结点为根的子树的搜索,逐层向 其祖先结点回溯 3.否则,进入该子树,继续按深度优先策略搜索 回溯法的算法框架 问题的解空间其含义为:所有可能解组成的空间 问题的解向量:一个n元式(x1,x2,x3…xn)的形式 显约束:对分量xi的取值进行限定,可以控制解空间的大小 隐约束:为满足问题的解而对不同分量之间施加的约束 ·对能否得到问题的可行解或最优解做出的约束 ·若不满足隐约束,说明得不到问题的可行解或最优解,就没必要 再沿该节点的分支进行搜索了,相当于把这个分支剪掉了 ·也称为剪枝函数 解空间:对于问题的一个实例,解向量满足显式约束条 件的所有多元组,构成了该实例的一个解空间 解空间越小,搜索效率越高 应至少包含问题的一个(最优)解 解空间多样性:同一个问题可以有多种表示,有些表示方法更简 单,所需表示的状态空间更小(存储量少,搜索方法简单) 解空间树:用一定的组织结构搜索最优解,并用树的形式表达出来,根据解空间树的不同,可分为子集树,排列数,m叉树等 回溯法基本思想基本步骤: 1.针对问题,定义问题的解空间 2.确定易于搜索的解空间结构 3.以深度优先方式搜索解空间,搜索中用剪枝函数避免无效搜索 剪枝函数:提高搜索效率 用约束函数在扩展结点处剪去不满足约束的子树 (能否得到问题的可行解的约束) 用限界函数剪去得不到最优解的子树 (能否得到最优解的约束) 复杂性 最长路径的长度为h(n),回溯法所需的空间为O(h(n)) 生成问题状态的基本方法扩展结点:一个正在产生儿子的结点 活结点:一个自身已生成但其儿子还没有全部生成的结点 死结点:一个所有儿子已经产生的结点 深度优先的问题状态生成法:如果对一个扩展结点R,一 旦产生了它的一个儿子C,就把C当做新的扩展结点。在完 成对子树C(以C为根的子树)的穷尽搜索之后,将R重新变成扩展结点继续生成R的下一个儿子(如果存在) 宽度优先的问题状态生成法:在一个扩展结点变成死结点 之前,它一直是扩展结点 回溯法:具有限界函数的深度优先生成 以旅行商问题示例: 右下角即为解空间树 递归回溯递归体内: 1.先判断是否到达叶结点: 再判断是否为更优的解 ①如果是,则更新路径,优值等信息 ②如果不是,不作处理 2.搜索下一个满足条件的结点 ①搜索到后,将本层结点保存 ②递归寻找 迭代回溯 子集树与排列树子集树:当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间 即从集合中选出满足条件的元素的集合,如背包问题:每个物品都存在选与不选的选择 排列数:当所给问题是确定n个元素满足某种性质的排列时,相应的解空间树 即将所有元素进行排序,集合中所有元素都使用,如全排列 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |