文档章节

回溯法

cumtm3
 cumtm3
发布于 2017/04/07 21:40
字数 425
阅读 16
收藏 0

1.概念:

        回溯法实际上是上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现不满足要求的解条件时,就“返回”,尝试别的路径。

        回溯法是一种优先搜索法,按照选优条件向前搜索,以达到目标。但是当搜索到某一步时,发现原先选择的并不是最优的或者达不到目标,就退回一步,重新选择。

        许多复杂的,规模较大的问题都可以使用回溯法。

2.基本思想

        在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根节点出发深度探索解空间树。当探索到某一节点时,要先判断该节点是否包含问题的解,如果包含,就从该节点继续出发,探索下去,如果街边不包含问题的解,则逐层回溯到祖先节点。(主要的思想是深度优先遍历)

3.回溯法的的一般步骤:

(1) 针对所给的问题,确定问题的解空间,解空间至少包含问题的一个最优解

(2)确定节点的扩展搜索规则

(3)以深度优先方式搜索解空间,利用“剪枝函数”进行吧避免无效的搜索。

 

4算法框架:

int[] a =new int [n];
try(int i)
{
if(i>n)
  输出结果;
else
{
for(int i=0;i<=上界;j++)
{
if(fun(j)
{
a[i]=j;
...
try(i+1);
}
)
}
}

}

 

 

分支限界法的搜索方式是以广度优先或者以最小耗费优先的方式进行搜索空间树。

© 著作权归作者所有

上一篇: 动态规划
下一篇: 找工作体会
cumtm3
粉丝 3
博文 32
码字总数 20918
作品 0
徐州
程序员
私信 提问

暂无文章

Eureka应用注册与集群数据同步源码解析

在之前的EurekaClient自动装配及启动流程解析一文中我们提到过,在构造DiscoveryClient类时,会把自身注册到服务端,本文就来分析一下这个注册流程 客户端发起注册 boolean register() t...

Java学习录
25分钟前
5
0
Java描述设计模式(15):责任链模式

本文源码:GitHub·点这里 || GitEE·点这里 一、生活场景描述 1、请假审批流程 公司常见的请假审批流程:请假天数 当 day<=3 天,项目经理审批当 3<day<=5 天,部门经理审批当 day>5 天...

知了一笑
36分钟前
6
0
总结:数组与链表

1、内存申请:数组在内存上是连续的空间;链表,内存地址上可以是不连续的。 2、查询速度:数组可以随机访问,链表必须顺序访问,即从首个元素开始遍历,逐个查找,所以数组查询很快。 3、写入...

浮躁的码农
44分钟前
6
0
HashMap源码分析

read

V丶zxw
今天
5
0
Python字符串或JSON字符串转字典dict、列表list

有3种方法 1、使用ast模块 >>> import ast>>> s = '["test",1]'>>> ast.literal_eval(s)['test',1]>>> s = '{"test":1}'>>> ast.literal_eval(s){'test': 1} 2、eval函数,这个......

编程老陆
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部