深度优先搜索的穷举

 我来答
发现8828
2016-05-14 · 超过75用户采纳过TA的回答
知道答主
回答量:203
采纳率:100%
帮助的人:70.8万
展开全部

在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举);
对于问题的第一个状态,叫初始状态,要求的状态叫目标状态。
搜索就是把规则应用于实始状态,在其产生的状态中,直到得到一个目标状态为止。
产生新的状态的过程叫扩展(由一个状态,应用规则,产生新状态的过程)
搜索的要点:(1)初始状态;
(2)重复产生新状态;
(3)检查新状态是否为目标,是结束,否转(2);
如果搜索是以接近起始状态的程序依次扩展状态的,叫宽度优先搜索。
如果扩展是首先扩展新产生的状态,则叫深度优先搜索。
深度优先搜索
深度优先搜索用一个数组存放产生的所有状态。
(1) 把初始状态放入数组中,设为当前状态;
(2) 扩展当前的状态,产生一个新的状态放入数组中,同时把新产生的状态设为当前状态;
(3) 判断当前状态是否和前面的重复,如果重复则回到上一个状态,产生它的另一状态;
(4) 判断当前状态是否为目标状态,如果是目标,则找到一个解答,结束算法。
(5) 如果数组为空,说明无解。
对于pascal语言来讲,它支持递归,在递归时可以自动实现回溯(利用局部变量)所以使用递归编写深度优先搜索程序相对简单,当然也有非递归实现的算法。
搜索是人工智能中的一种基本方法,是一项非常普遍使用的算法策略,能够解决许许多多的常见问题,在某些情况下我们很难想到高效的解法时,搜索往往是可选的唯一选择。按照标准的话来讲:搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。
搜索虽然简单易学易于理解,但要掌握好并写出速度快效率高优化好的程序却又相当困难,总而言之,搜索算法灵活多变,一般的框架很容易写出,但合适的优化却要根据实际情况来确定。在搜索算法中,深度优先搜索(也可以称为回溯法)是搜索算法里最简单也最常见的,今天我们就从这里讲起,下面的内容假设读者已经知道最基本的程序设计和简单的递归算法。

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
柚鸥ASO
2024-03-16 广告
首先,要了解ASO优化的基本概念,以及与aso有关的相关技术。其次,要掌握运用界面的相关知识,熟悉aso有关的相关操作。此外,还需要通过各大渠道了解行业内的最新技术和aso优化的最新操作。 柚鸥ASO优化就做的蛮不错的;专注应用商店下载量优... 点击进入详情页
本回答由柚鸥ASO提供
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式