精华内容
下载资源
问答
  • 2020-03-18 16:01:36

    搜索算法

    本文主要以一些概念对较为常见的搜索作简单介绍:

    一、盲目搜索


        对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中,广度优先算法和深度优先搜索算法都十分重要,因为它们提供了一套系统地访问图数据结构的方法。我们着重讲解广度优先搜索算法。

    具体例子可看以下文章:

    广度和深度解析

    1.深度优先搜索

    深度优先搜索算法(简称DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点的所在边都己被探寻过,搜索将回溯到发现节点的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。由于深度优先搜索不是接下来最短路径算法的基础,因此这里不做拓展。

    2.广度优先搜索

    广度优先搜索算法(简称BFS)又称为宽度优先搜索从起点开始,首先遍历起点周围邻近的点,然后再遍历已经遍历过的点邻近的点,逐步的向外扩散,直到找到终点。
    在执行算法的过程中,每个点需要记录达到该点的前一个点的位置 —父节点。这样做之后,一旦到达终点,便可以从终点开始,反过来顺着父节点的顺序找到起点,由此就构成了一条路径。
    以上两种算法的不同搜索策略可以通过下面网页查看动图,这是两种相邻节点之间的移动代价相等时用到的算法,图中的边不设权值。
    https://cs.stanford.edu/people/abisee/tutorial/bfsdfs.html

    3.Dijkstra算法

    Dijkstra算法是由计算机科学家Edsger W.Dijkstra在1956年提出的。
    考虑这样一种场景,在一些情况下,图形中相邻节点之间的移动代价并不相等。例如,游戏中的一幅图,既有平地也有山脉,那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。在Dijkstra算法中,需要计算每一个节点距离起点的总移动代价。同时,还需要一个优先队列结构。对于所有待遍历的节点,放入优先队列中会按照代价进行排序。在算法运行的过程中,每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。
    对比了不考虑节点移动代价差异的广度优先搜索与考虑移动代价的Dijkstra算法,又如下动图所示:

    可以看出当图形为网格图,并且每个节点之间的移动代价是相等的,那么Dijkstra算法将和广度优先算法变得一样。以下网址链接可以自行设置绿色网格的位置。

    在这里的无法插入图片描述

    Dijkstra算法(可自行设置障碍物)

    二、启发式搜索算法

    1.贪婪最佳优先

    在Dijkstra算法中,我已经发现了其最终要的缺陷,搜索存在盲目性。在这里,我们只针对这个痛点,采用贪婪最佳优先搜索来解决。如何解决?我们只需稍微改变下观念即可,在Dijkstra算法中,优先队列采用的是,每个顶点到起始顶点的预估值来进行排序。在贪婪最佳优先搜索采用的是,每个顶点到起始顶点的预估值来进行排序。
    两者的搜索过程对比如下动图所示:

    在这里插入图片描述

    明显看到右边的算法(贪婪最佳优先搜索 )寻找速度要快于左侧,虽然它的路径不是最优和最短的,但障碍物最少的时候,他的速度却足够的快。这就是贪心算法的优势,基于目标去搜索,而不是完全搜索。
    贪婪最佳优先搜索动态图(可自行设置障碍物)

    2.A star算法

    我们找到了最短路径和搜索顶点最少数量的两种方案,Dijkstra 算法和贪婪最佳优先搜索。接下来能否汲取两者的有点选择既速度快又能得到最优解的算法?.
    A star算法正是这么做了,它吸取了Dijkstra 算法中的当前代价,为每个边长设置权值,不停的计算每个顶点到起始顶点的距离,以获得最短路线,同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势,并持续计算每个顶点到目标顶点的距离,以引导搜索队列不断想目标逼近,从而搜索更少的顶点,保持寻路的最优解。A star算法在运算过程中,每次从优先队列中选取f(n)值最小(优先级最高)的节点作为下一个待遍历的节点。A star算法使用两个集合来表示待遍历的节点,与已经遍历过的节点,这通常称之为open_set和close_set。
    A star算法优先队列排序方式基于估价值,估价值由顶点到起始顶点的距离(代价)加上顶点到目标顶点的距离(启发函数)之和构成。
    A star算法、贪婪最佳优先、Dijkstra算法三者的静态效果图如下:

    在这里插入图片描述

    三者动态效果图对比(可自行设置障碍物)

    三、启发函数

    f(n)=g(n)+h(n)f(n)=g(n)+h(n)
    f(n)=g(n)+h(n)

    f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时,我们总会选取综合优先级最高(值最小)的节点。g(n) 是节点n距离起点的代价。h(n)是节点n距离终点的预计代价,这也就是A star算法的启发函数。
    上面已经提到,启发函数会影响A star算法的行为。
    在极端情况下,当启发函数h(n)始终为0,则将由g(n)决定节点的优先级,此时算法就退化成了Dijkstra算法。
    如果h(n)始终小于等于节点n到终点的代价,则A star算法保证一定能够找到最短路径。但是当h(n)的值越小,算法将遍历越多的节点,也就导致算法越慢。
    如果h(n)完全等于节点n到终点的代价,则A star算法将找到最佳路径,并且速度很快。可惜的是,并非所有场景下都能做到这一点。因为在没有达到终点之前,我们很难确切算出距离终点还有多远。
    如果h(n)的值比节点n到终点的代价要大,则A star算法不能保证找到最短路径,不过此时会很快。在另外一个极端情况下,如果h(n)相较于g(n)大很多,则此时只有h(n)产生效果,这也就变成了贪婪最佳优先搜索。
    由上面这些信息我们可以知道,通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况,我们可能未必需要最短路径,而是希望能够尽快找到一个路径即可。这也是A star算法比较灵活的地方。对于网格形式的图,有以下这些启发函数可以使用:
    如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离。
    如果图形中允许朝八个方向移动,则可以使用对角距离。
    如果图形中允许朝任何方向移动,则可以使用欧几里得距离。

    总结

    以下网页是五种不同搜索算法的搜索过程对比:

    五种搜索算法(可进行添加多种障碍物)

    下面对在有权图(紫)和无权图(黄)上利用搜索算法的特点做一个总结:

    本文相关PDF文件:
    Graph Search Algorithms

    本文参考文章链接:

    http://frankorz.com/2017/12/16/greedy-best-find-search/
    https://cs.stanford.edu/people/abisee/tutorial/customize.html
    https://zhuanlan.zhihu.com/p/54510444?utm_source=com.tencent.tim&utm_medium=social&utm_oi=774664375033163776
    https://www.gameres.com/777251.html
     

    更多相关内容
  • 合工大人工智能原理educoder实训盲目搜索算法
  • 常用搜索算法—盲目搜索和启发式搜索

    万次阅读 多人点赞 2019-05-25 00:51:39
    一、盲目搜索 对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中,广度优先算法和深度优先搜索算法都十分重要,因为它们提供了一套系统地访问图数据结构的方法。我们着重讲解广度优先搜索...

    搜索算法

    本文主要以一些概念对较为常见的搜索作简单介绍:

    一、盲目搜索

    对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中,广度优先算法和深度优先搜索算法都十分重要,因为它们提供了一套系统地访问图数据结构的方法。我们着重讲解广度优先搜索算法。

    1.深度优先搜索
    深度优先搜索算法(简称DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点的所在边都己被探寻过,搜索将回溯到发现节点的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。由于深度优先搜索不是接下来最短路径算法的基础,因此这里不做拓展。
    2.广度优先搜索
    广度优先搜索算法(简称BFS)又称为宽度优先搜索从起点开始,首先遍历起点周围邻近的点,然后再遍历已经遍历过的点邻近的点,逐步的向外扩散,直到找到终点。
    在执行算法的过程中,每个点需要记录达到该点的前一个点的位置 —父节点。这样做之后,一旦到达终点,便可以从终点开始,反过来顺着父节点的顺序找到起点,由此就构成了一条路径。
    以上两种算法的不同搜索策略可以通过下面网页查看动图,这是两种相邻节点之间的移动代价相等时用到的算法,图中的边不设权值。
    https://cs.stanford.edu/people/abisee/tutorial/bfsdfs.html
    3.Dijkstra算法
    Dijkstra算法是由计算机科学家Edsger W.Dijkstra在1956年提出的。
    考虑这样一种场景,在一些情况下,图形中相邻节点之间的移动代价并不相等。例如,游戏中的一幅图,既有平地也有山脉,那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。在Dijkstra算法中,需要计算每一个节点距离起点的总移动代价。同时,还需要一个优先队列结构。对于所有待遍历的节点,放入优先队列中会按照代价进行排序。在算法运行的过程中,每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。
    对比了不考虑节点移动代价差异的广度优先搜索与考虑移动代价的Dijkstra算法,又如下动图所示:
    在这里的无法插入图片描述
    可以看出当图形为网格图,并且每个节点之间的移动代价是相等的,那么Dijkstra算法将和广度优先算法变得一样。以下网址链接可以自行设置绿色网格的位置。

    Dijkstra算法(可自行设置障碍物)

    二、启发式搜索算法

    1.贪婪最佳优先
    在Dijkstra算法中,我已经发现了其最终要的缺陷,搜索存在盲目性。在这里,我们只针对这个痛点,采用贪婪最佳优先搜索来解决。如何解决?我们只需稍微改变下观念即可,在Dijkstra算法中,优先队列采用的是,每个顶点到起始顶点的预估值来进行排序。在贪婪最佳优先搜索采用的是,每个顶点到目标顶点的预估值来进行排序。
    两者的搜索过程对比如下动图所示:
    在这里插入图片描述
    明显看到右边的算法(贪婪最佳优先搜索 )寻找速度要快于左侧,虽然它的路径不是最优和最短的,但障碍物最少的时候,他的速度却足够的快。这就是贪心算法的优势,基于目标去搜索,而不是完全搜索。
    贪婪最佳优先搜索动态图(可自行设置障碍物)

    2.A star算法
    我们找到了最短路径和搜索顶点最少数量的两种方案,Dijkstra 算法和贪婪最佳优先搜索。接下来能否汲取两者的有点选择既速度快又能得到最优解的算法?.
    A star算法正是这么做了,它吸取了Dijkstra 算法中的当前代价,为每个边长设置权值,不停的计算每个顶点到起始顶点的距离,以获得最短路线,同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势,并持续计算每个顶点到目标顶点的距离,以引导搜索队列不断想目标逼近,从而搜索更少的顶点,保持寻路的最优解。A star算法在运算过程中,每次从优先队列中选取f(n)值最小(优先级最高)的节点作为下一个待遍历的节点。A star算法使用两个集合来表示待遍历的节点,与已经遍历过的节点,这通常称之为open_set和close_set。
    A star算法优先队列排序方式基于估价值,估价值由顶点到起始顶点的距离(代价)加上顶点到目标顶点的距离(启发函数)之和构成。
    A star算法、贪婪最佳优先、Dijkstra算法三者的静态效果图如下:
    在这里插入图片描述
    三者动态效果图对比(可自行设置障碍物)

    三、启发函数

    f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)
    f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时,我们总会选取综合优先级最高(值最小)的节点。g(n) 是节点n距离起点的代价。h(n)是节点n距离终点的预计代价,这也就是A star算法的启发函数。
    上面已经提到,启发函数会影响A star算法的行为。
    在极端情况下,当启发函数h(n)始终为0,则将由g(n)决定节点的优先级,此时算法就退化成了Dijkstra算法。
    如果h(n)始终小于等于节点n到终点的代价,则A star算法保证一定能够找到最短路径。但是当h(n)的值越小,算法将遍历越多的节点,也就导致算法越慢。
    如果h(n)完全等于节点n到终点的代价,则A star算法将找到最佳路径,并且速度很快。可惜的是,并非所有场景下都能做到这一点。因为在没有达到终点之前,我们很难确切算出距离终点还有多远。
    如果h(n)的值比节点n到终点的代价要大,则A star算法不能保证找到最短路径,不过此时会很快。在另外一个极端情况下,如果h(n)相较于g(n)大很多,则此时只有h(n)产生效果,这也就变成了贪婪最佳优先搜索。
    由上面这些信息我们可以知道,通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况,我们可能未必需要最短路径,而是希望能够尽快找到一个路径即可。这也是A star算法比较灵活的地方。对于网格形式的图,有以下这些启发函数可以使用:
    如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离。
    如果图形中允许朝八个方向移动,则可以使用对角距离。
    如果图形中允许朝任何方向移动,则可以使用欧几里得距离。

    总结

    以下网页是五种不同搜索算法的搜索过程对比:

    五种搜索算法(可进行添加多种障碍物)

    下面对在有权图(紫)和无权图(黄)上利用搜索算法的特点做一个总结:

    本文相关PDF文件:
    Graph Search Algorithms

    本文参考文章链接:

    http://frankorz.com/2017/12/16/greedy-best-find-search/
    https://cs.stanford.edu/people/abisee/tutorial/customize.html
    https://zhuanlan.zhihu.com/p/54510444?utm_source=com.tencent.tim&utm_medium=social&utm_oi=774664375033163776
    https://www.gameres.com/777251.html

    展开全文
  • 1.搜索算法是很多优化和规划问题问题的基础,很多问题的解决都依赖于搜索策略。 2.把一个问题转化为搜索问题(即问题的形式化)需要: 将问题表示为状态...盲目搜索(Uninformed Search、Blind Search) 深度优先

    1.搜索算法是很多优化和规划问题问题的基础,很多问题的解决都依赖于搜索策略。
    2.把一个问题转化为搜索问题(即问题的形式化)需要:
    将问题表示为状态(STATES)和操作算子(OPERATORS)的集合,操作算子可以将问题由一个状态转化为另一种状态。利用不同的操作算子将问题从初始状态转化到目标状态,所有这些操作算子的序列即为问题的一个解。因此,我们要想找到一个问题的解就是在状态空间中找到连接初始状态和目标状态操作算子序列。
    在这里插入图片描述

    盲目搜索(Uninformed Search、Blind Search)

    深度优先搜索(Depth-first search):
    按照深度优先方式遍历搜索空间,但是这种方式可能会使遍历一直在非目标状态方向上深度遍历,导致找不到解。
    广度优先搜索(Breadth-first search):
    广度优先搜索始终可以保证找到问题的解,但时间和空间消耗较大。
    迭代搜索(Iterative deepening search):
    考虑到深度优先搜索不一定可以找到问题的解,但是可以将深度优先和广度优先向结合,即为其添加深度限制。当深度遍历到一定的深度还是找不到解时使搜索方向转到其他状态分支继续深度遍历,使受限制的层数不断增加直到找到问题的解。

    启发式搜索(Heuristic Search、Best-first Search)

    A*算法
    为搜索提供一些可知信息(knowledge),可使搜索的方向性更强,避免一些不必要的状态的扩展,节约时间和空间。考虑当当前状态与目标状态相似度最高时,可以更快找到解,因此引入评估函数f(n)=h(n)+g(n),其中h(n)为当前状态和目标状态不同棋子的个数,g(n)为当前状态的深度。f(n)值最小的是和目标状态最接近的状态,因此优先扩展。
    加强评估函数的A*算法
    考虑到棋子移动的步数也是可知的并且会影响扩展序列个数的因素,因此设f(n)=h(n)+g(n),其中h(n)为每个棋子当前状态到达目标状态的步数和,g(n)为当前状态的深度。这样可以进一步减少不必要的扩展。

    一般图搜索算法

    为使各搜索算法更便于实现,将这些算法整合为一般图搜索算法
    创建open表(存储待扩展序列)和close表(存储已扩展序列),几种算法的不同只在于入表和出表的方式和排序方法
    在这里插入图片描述
    在这里插入图片描述

    以九宫重排问题为例,比较几种算法的优劣

    实现代码
    在这里插入图片描述
    1.盲目搜索(广度优先搜索算法)
    按照广度优先遍历九宫格的所有可能状态:
    在这里插入图片描述

    2.盲目搜索(深度优先搜索算法)
    按照普通深度优先遍历九宫格的所有可能状态:
    在这里插入图片描述

    如图所示,深度优先遍历不一定能找到正确的结果,因为搜索可能会在非目标状态的分支里一直深度遍历。因此考虑增加层数限制,使得在搜索某分支的固定层数后无解时可以返回继续遍历其他分支
    3.盲目搜索(迭代搜索算法)
    规定层数为10:
    在这里插入图片描述

    规定层数为50:
    在这里插入图片描述

    4.启发式搜索(A*搜索算法)
    规定评估函数f(n)=h(n)+g(n),
    其中h(n)为当前状态和目标状态不同棋子的个数,g(n)为当前状态的深度:
    在这里插入图片描述

    5.启发式搜索(加强启发条件的A*搜索算法)
    规定评估函数f(n)=h(n)+g(n),
    其中h(n)为每个棋子当前状态到达目标状态的步数和,g(n)为当前状态的深度:
    在这里插入图片描述
    各搜索算法对比:
    在这里插入图片描述

    由上表对比数据可知:

    1. 广度优先搜索虽然可以保证一定找到解,但是时间复杂度和空间复杂度很高。
    2. 增加了深度限制的深度优先搜索比广度优先搜索扩展步数更少、耗时更短。
    3. 为搜索增加评估函数的A*算法可以使搜索更有方向性,极大的减少了扩展步数,节约了待扩展序列的存储空间;时间效率也大大提高。
    4. 加强A*算法的评估函数的条件,继续避免一些不必要的扩展,可以进一步提高搜索效率。
    展开全文
  • 盲目搜索(广度搜索)解重排九宫问题,即把数码问题的盲目搜索求解!C++实现的。
  • 第六讲 一般搜索原理 -- 盲目搜索 ? 搜索 : 从问题表示到问题解决的求解过程 . 一 . 盲目搜索 : 人为给定搜索顺序的无信息搜索 . 1. 宽度优先搜索 2. 深度优先搜索 3. 等代价搜索 二 . 启发式搜索 : 根据检测到的...
  • 搜索的策略(1)——盲目搜索

    千次阅读 2019-03-29 17:46:27
     盲目搜索的名字不太好听,容易被扣上“性能低下”的帽子,通常在找不到解决问题的规律时使用,但凡能找到某些规律,就不会选择蛮力法,可以说盲目搜索策略是最后的大招。遗憾的是,很多问题都没有明显的规律可循,...

      早在1952年,克劳德·香农就已经是电子信息界的传奇人物,但是对当时的普通大众来说,他仍然是个陌生人。不过在即将开始的会展后,他就人尽皆知了。

      在会议展上,香农展示了一只木制的、带有铜须的玩具老鼠,这只老鼠能够在迷宫中穿梭,最终找到出口处的金属硬币。老鼠是通过试错的方式探索迷宫的,通过胡须,它可以感知是否碰到了走不通的墙壁,如果正对的墙壁走不通,就会退到后一个格子,旋转90°,继续探测下一个方向。如果走通了迷宫,老鼠还能记住这条路线,在下一次直接完成任务。

      其实香农的老鼠并没有那么智能,它仅仅是“记住”路线,而不是“认识”路线——在老鼠走通迷宫后,如果撤掉迷宫的墙壁,老鼠依然是按照上次的线路前进。香农可没有把这一点告诉观众,对于观众来说,这只机器老鼠简直是来自异次元的天物,是一个会思考的机器!

      这个其貌不扬的小老鼠在当年登上了《时代》和《生活》杂志的封面,有一期文章甚至用《这只老鼠比你聪明》为标题。贝尔实验室的老板们对这只老鼠印象深刻,他们在冲动中甚至要把香农拉进贝尔电话公司的董事会。

    盲目搜索

      从老鼠探索迷宫的行为可以看出,它使用的深度优先搜索,这是一种简单而暴力的穷举搜索,几乎没有任何神秘性可言——找到一条路就一直走下去,直到撞墙为止,然后回溯,继续探索,我们将这种搜索策略称为“盲目搜索”。

      盲目搜索就是我们常说的“蛮力法”,又叫非启发式搜索。作为最先想到的一种所搜策略,盲目搜索是一种无信息搜索。之所以被称为“盲目”,是因为这种搜索策略只是按照预定的策略搜索解空间的所有状态,而不会考虑到问题本身的特性。我们熟悉的深度优先搜索和广度优先搜索就是两种典型的盲目搜索。

      盲目搜索的名字不太好听,容易被扣上“性能低下”的帽子,通常在找不到解决问题的规律时使用,但凡能找到某些规律,就不会选择蛮力法,可以说盲目搜索策略是最后的大招。遗憾的是,很多问题都没有明显的规律可循,很多时候我们不得不求助于蛮力法。同时,由于思路简单,盲目搜索策略通常是被人们第一个想到的,对于一些比较简单的问题,盲目搜索确实能发挥奇效。对于盲目策略来说,我们既鄙视它近似蛮力的“性能低下”,又膜拜它把一切托付给计算机的“节省脑细胞”。

      在这一章里,我们先对盲目所搜展开讨论,看看计算机带给我们的神奇的大招。同时我们也将看到,“盲目”也并非一味的蛮干,在加以改进后,算法也并非像我们想象的那样“性能低下”。

    八皇后问题

      在国际象棋中,皇后(Queen)是攻击力最强的棋子,皇后可横、直、斜走,且格数不限,吃子与走法相同,往往是棋局中制胜的决定性力量,少掉一个皇后往往意味着棋局告负。皇后模拟的是欧洲中世纪时,王室自皇后娘家借来的援军,作为棋盘上最具威力的一子,皇后代表强大的援军。

      国际象棋棋手马克斯·贝瑟尔于1848年提出了一个问题:在8×8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,一共有多少种摆法?

    解空间

      八皇后看起来不那么好对付,除了挨个尝试之外没什么太好的办法了。如果不考虑皇后的互相攻击,将八个皇后每行摆放一个,一共会有多少种摆法呢?

      这个问题实际是在回答要搜索的解空间,这也是问题的关键——盲目搜索并不是漫无目的的搜索,而是在一个固定的范围内寻找答案。有时候解空间的范围不太容易直接回答,此时的一种思路是将问题简化,由简单的问题入手,逐步归纳总结出最后的答案。我们不妨把问题规模缩小,把2个皇后摆放在2×2的棋盘上,看看一共有多少种摆法。

      为了叙述方便,我们把每一行的皇后都编上号,摆放在第1行的皇后是1号,第2行是2号,两个皇后一共有22=4种摆法:

      类似地,把3个皇后摆放在3×3的棋盘上时,先固定前两行的皇后,再摆放3号,此时有3种摆法:

      保持1号不动,移动2号时,会产生另外6种摆法:

      这就形成了9种摆法。最后再移动1号,会产生另外9×2=18种摆法,因此把3个皇后摆放在3×3的棋盘上一共有33=27种摆法。以此类推,八皇后问题的解空间是88=16777216。仅仅是8个棋子就产生了如此多的解空间,没有计算机可真是累人。

    搜索策略

      160多万的解空间真的要全部搜索吗?当然不会,每个皇后都有自己的攻击范围,在摆放第1个皇后时,其它皇后的摆放位置也被某种程度的限定了:

      为了避开皇后1的攻击范围,第2个皇后只能在剩下的6浅色格子中选择;而2号皇后落子后,又将对其它皇后做出进一步限制;到了第3行,摆放位置可能只剩下4个:

      我们并不会傻乎乎的对所有解空间进行搜索,而是随着步骤的进行,避开了绝对不可能的解,从而有效地缩小了解空间的范围。

      之后的皇后也采用这样的办法来摆放,这是一种试探法——先把皇后摆放在“安全”位置,然后设置她的攻击范围,再在下一个安全位置摆放下一个皇后;如果下一个皇后没有“安全”位置了,那么“悔棋”,重新摆放上一皇后;再不行就“大悔棋”,上上一个皇后也重新摆放:

      这种带回溯的方法就是我们熟知的深度优先搜索——只管埋头前进,撞到墙才后退。

      虽然我们知道怎么摆放棋子,但计算机并不知道,在编写代码之前必须先完成从现实世界到软件设计的映射。

      对于棋盘问题,一个有效的数据结构是8×8的二维列表,列表中的每个元素代表棋盘上的一个方格;方格有三种状态,闲置、落子、是否处于被攻击状态,分别用0、1、2表示,这些构成了八皇后问题的数据模型。

      接下来是摆放棋子的行为。我们按行来摆放,每行摆放一个皇后,每次落子后都将把棋盘的部分方格设置为“被攻击”。代码:

     1 import copy
     2 
     3 class EightQueen:
     4     def __init__(self):
     5         # 棋盘单元格的初始状态, 被皇后占据状态, 被皇后攻击状态
     6         self.s_init, self.s_queen, self.s_attack = 0, 1, 2
     7         # 棋盘的行数和列数
     8         self.row_num, self.col_num  = 8, 8
     9         # 棋盘
    10         self.chess_board = [[self.s_init] * self.row_num for i in range(self.row_num)]
    11         # 解决方案列表
    12         self.answer_list = []
    13 
    14     def start(self):
    15         self.put_down(self.chess_board, 0)
    16 
    17     def put_down(self, curr_board, row):
    18         ''' 在棋盘的第row行落子 '''
    19         if row == self.row_num:
    20             self.answer_list.append(curr_board)
    21             return
    22 
    23         for col in range(self.col_num):
    24             if self.enable(curr_board, row, col):
    25                 # 复制棋盘上的状态, 以便回溯
    26                 bord = copy.deepcopy(curr_board)
    27                 # 将皇后放在第row行第col列中
    28                 bord[row][col] = self.s_queen
    29                 # 设置第row行第col列的皇后的攻击范围
    30                 self.set_attack(bord, row, col)
    31                 # 继续在下一行落子
    32                 self.put_down(bord, row + 1)
    33 
    34     def enable(self, curr_board, row, col):
    35         '''是否可以在棋盘的第row行第col列落子'''
    36         return curr_board[row][col] == self.s_init
    37 
    38     def set_attack(self, curr_board, row, col):
    39         '''设置第row行第cell列的皇后的攻击范围'''
    40         # 最后一行没有必要设置攻击范围
    41         if row == self.row_num - 1:
    42             return
    43 
    44         # 正下方的攻击范围
    45         for next_row in range(row + 1, self.row_num):
    46             curr_board[next_row][col] = self.s_attack
    47         # 左斜下的攻击范围
    48         left_col = col - 1
    49         for next_row in range(row + 1, self.row_num):
    50             if left_col >= 0:
    51                 curr_board[next_row][left_col] = self.s_attack
    52                 left_col -= 1
    53             else:
    54                 break
    55         # 右斜下的攻击范围
    56         right_col = col + 1
    57         for next_row in range(row + 1, self.row_num):
    58             if right_col < self.col_num:
    59                 curr_board[next_row][right_col] = self.s_attack
    60                 right_col += 1
    61             else:
    62                 break
    63 
    64     def display(self):
    65         '''打印所有方案'''
    66         length = len(self.answer_list)
    67         if length == 0:
    68             print('No answers!')
    69             return
    70 
    71         print('There are %d answers!' % length)
    72         for i in range(0, length):
    73             print('-' * 20, 'answer', i + 1, '-' * 20)
    74             bord = self.answer_list[i]
    75             for row in bord:
    76                 for c in row:
    77                     if c == self.s_queen:
    78                         print('%4d' % 1, end='')
    79                     else:
    80                         print('%4d' % 0, end='')
    81                 print()
    82 
    83 if __name__ == '__main__':
    84     eq = EightQueen()
    85     eq.start()
    86     eq.display()

      

      在set_attack()中,由于是逐行落子,所以只需要处理位于皇后下方的单元格。每次set_attack后,棋盘上的安全位置就又少了一些,下次落子只能落在下一行的“安全”位置上。

      enable()用来判断是否安全,方法很简单,只需检查方格的状态是否是初始状态。

      在put_down()中,我们以一种“顺序”的方式逐行落子,如果正好摆满了八个皇后,则该种摆法是八皇后问题的一个解;如果没有任何“安全”位置能够摆放下一个皇后,则进行“悔棋”操作。每落一子都要记住棋盘的状态,只有这样才能回溯,以便进行“悔棋”。每落一子都相当于在解空间内进行了一次搜索,如果加入计数器的话,会发现最终只进行了15720次搜索,这可比之前少了两个数量级。

      一共有92种解,其中一种:

      高斯认为八皇后问题有76种方案,1854年在柏林的象棋杂志上不同的作者发表了40种不同的解。看来没有计算机的帮助,带有穷举性质的盲目搜索还真是一种不可尝试的方法。

    同根同源的另一种方法

      在EightQueen中,我们的方案是每次落子都重置棋盘的“安全”状态,与之对应的另一种思路是“先检查,再落子”,从而省去了方格的“被攻击”状态。

      仍然是按行来摆放,每行摆放一个皇后,摆放前需要检查待摆放的棋子是否处于其它皇后的攻击范围内,只有不在攻击范围内时才允许摆放,否则“缓棋”,重新摆放上一个皇后,代码如下:

    import copy
    
    class EightQueen_2:
        def __init__(self):
            # 棋盘单元格的初始状态, 被皇后占据状态
            self.s_init, self.s_queen = 0, 1
            # 棋盘的行数和列数
            self.row_num, self.col_num = 8, 8
            # 棋盘
            self.chess_board = [[self.s_init] * self.row_num for i in range(self.row_num)]
            # 解决方案列表
            self.answer_list = []
    
        def start(self):
            self.put_down(self.chess_board, 0)
    
        def put_down(self, curr_board, row):
            ''' 在棋盘的第row行落子 '''
            if row == self.row_num:
                self.answer_list.append(curr_board)
                return
    
            for col in range(self.col_num):
                # 是否会和已经在棋盘上的皇后互相攻击
                if self.enable_attacked(curr_board, row, col) == False:
                    # 复制棋盘上的状态, 以便回溯
                    bord = copy.deepcopy(curr_board)
                    # 将皇后放在第row行第col列中
                    bord[row][col] = self.s_queen
                    # 继续在下一行落子
                    self.put_down(bord, row + 1)
    
        def enable_attacked(self, curr_board, row, col):
            ''' 第row行第col列的皇后是否会和已经在棋盘上的皇后互相攻击 '''
            # 是否会和第col列的皇后互相攻击
            for last_row in range(row - 1, -1, -1):
                if curr_board[last_row][col] == self.s_queen:
                    return True
            # 是否会和左斜上的皇后互相攻击
            left_col = col - 1
            for last_row in range(row - 1, -1, -1):
                if left_col >= 0 and curr_board[last_row][left_col] == self.s_queen:
                    return True
                left_col -= 1
            # 是否会和右斜上的皇后互相攻击
            right_col = col + 1
            for last_row in range(row - 1, -1, -1):
                if right_col < self.col_num and curr_board[last_row][right_col] == self.s_queen:
                    return True
                right_col += 1
    
            return False
    
        def display(self):
            '''打印所有方案'''
            length = len(self.answer_list)
            if length == 0:
                print('No answers!')
                return
            print('There are %d answers!' % length)
            for i in range(0, length):
                print('-' * 20, 'answer', i + 1, '-' * 20)
                bord = self.answer_list[i]
                for row in bord:
                    for c in row:
                        print('%4d' % c, end='')
                    print()
    
    if __name__ == '__main__':
        eq = EightQueen_2()
        eq.start()
        eq.display()

      

      enable_attacked()用于判断待摆放的棋子是否处于其它皇后的攻击范围内,由于是逐行落子,下方没有皇后,所以只需要考虑上方的皇后即可

      EightQueen_2仅仅是用比较代替了修改,和EightQueen并没有本质的区别,只是因为EightQueen更符合人类的行为,所以看起来也更高级一点。

      


       作者:我是8位的

      出处:http://www.cnblogs.com/bigmonkey

      本文以学习、研究和分享为主,如需转载,请联系本人,标明作者和出处,非商业用途! 

      扫描二维码关注公众号“我是8位的”

    展开全文
  • trans.py盲目搜索

    2021-01-02 17:48:04
    搜索技术
  • 人工智能07 盲目搜索

    千次阅读 2019-07-09 10:46:31
    盲目搜索 我们将学习两类主要的搜索过程。其中之一,我们没有指定问题的任何推理信息,例如要搜索这一部分而不是另一部分,就像到目前为止的只要发现一条到目标的路径即可。这种搜索是盲目的。另一种,我们指定了要...
  • 第3章盲目搜索 31一般搜索过程 3.2回溯策略 33宽度(广度优先搜索 34代价树的宽度优先搜索 35深度优先搜索 搜索推理与人工智能 搜索是人工智能中的一个基本问题,是推理不可分 割的一部分,它直接关系到智能系统的性能...
  • 分支限界算法,即统一代价搜索 3.n拼图问题 深度优先搜索 广度优先搜索 4.传教士和食人魔问题 DFS,BFS 5.DFS和BFS的比较 优先DFS:树很深,分支因子不大,解出现的位置较深 反之优先BFS DFS既不优选也不完备,空间...
  • 搜索很快的推进到搜索树的最深处的结点,该结点称之为叶子结点,它没有后继,当这些结点扩展完之后,就从边缘结点中去掉,然后回溯到下一个未扩展后继的深度稍浅的结点,搜索过程如下图所示。 与宽度优先搜索使用 ...
  • 盲目搜索算法(DOC).doc
  • 这篇文章的意义在于哪里呢? 1)向大家展示如何形式化定义一个搜索问题,又如何去求解; 2)通过讲述各种盲目搜索算法,帮大家梳理无信息搜索的脉络。
  • 盲目搜索算法

    千次阅读 2019-01-16 09:54:14
    盲目搜索算法指的是不使用领域知识的不知情搜索算法。主要包括三种算法:深度优先搜索(DFS)、广度优先搜索(BFS)和迭代加深(DFS-ID)的深度优先搜索。 深度优先搜索:1-&gt;2-&gt;3 1-&gt;2-&...
  • 通过这个文件可以了解盲目搜索算法的基础知识,对后续的人工学习有很大的帮助
  • 人工智能基础 搜索问题 介绍 一般的问题都可以归为下面三个步骤 问题求解 问题求解中最主要的就是搜索问题了,下面就来介绍搜索问题 搜索问题 如魔方的还原问题 如转动次数最少的魔方还原 特征 四个典型的搜索...
  • 人工智能第1章盲目搜索.pptx
  • 与或树的盲目搜索和启发式搜索

    千次阅读 2017-11-20 21:25:57
    与或树的盲目搜索 与或树的一般搜索过程如下 (1)把原始问题作为初始节点S0,并把它作为当前节点 (2)应用分解或等价变换操作对当前节点进行扩展 (3)为每个子节点设置指向父节点的指针 (4)选择合适的子...
  • 盲目搜索策略和在实际中的应用研究.doc
  • 人工智能--状态空间的盲目搜索

    千次阅读 2019-06-09 21:51:34
    文章目录状态空间的盲目搜索广度优先算法算法描述:总结深度优先算法总结 状态空间的盲目搜索 根据状态空间所采用的数据结构的不同,可分为图搜索算法和树搜索算法。由于图搜索算法且一般问题都可用树搜索算法解决,...
  • 第3章(确定性推理1-图盲目搜索)
  • 一、终点未知的搜索(Uninformed search strategies) 深度优先搜索(DFS)和广度优先搜索(BFS) 深度限制搜索 迭代加深搜索 根据以下维度评估策略:
  • 人工智能 —— 状态空间的盲目搜索

    千次阅读 2019-06-12 22:39:32
    若出现,则搜索成功,找到了问题的解;若没出现,则再按照某种搜索策略从已生成的子结点中选择一个结点作为当前扩展结点。 (3)重复上述过程,直到目标状态出现在子结点中或者没有可供操作的结点为止。所谓对一个...
  • C-盲目搜索--人工智能(AI).ppt
  • 分析人工智能中盲目搜索的课件,有详细描述和范例讲解
  • 目搜索盲目搜索又叫做无信息搜索,一般只适用于求解比较简单的问题。我们将学习的宽度优先搜索和深度优先搜索,属于盲目搜索方法。一、宽度优先搜索回顾上一节的寻找寿命为X的人的例子,如果搜索时,从节点A开始,对...
  • 人工智能 —— 代价树的盲目搜索

    千次阅读 2019-06-12 22:53:46
    代价树搜索的目的是为了找到最佳解,即找到一条代价最小的解路径。 代价树的广度优先搜索算法 (1)搜索算法的过程 把初始结点S0放入Open表中,置S0的代价g(S0)=0; 如果Open表为空,则问题无解 ,失...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,492
精华内容 10,996
关键字:

盲目搜索

友情链接: xml1.rar