1、盲目搜索算法的内容与优缺点？启发式搜索算法的内容与优缺点

盲目搜索算法，也称为无信息搜索，是一种只依据预定的搜索策略进行搜索，而不考虑问题特性的方法。通常适用于简单的问题求解，其中较为常见的包括宽度优先搜索算法和深度优先搜索。

宽度优先搜索算法（BFS）以队列实现，从根节点开始遍历，遍历完再按照同样的方式遍历下一层节点。其优点在于能够找到最短路径，并且如果最短路径存在，则可以保证最先找到。但其缺点在于可能需要遍历许多无用节点，导致时间开销高。

深度优先搜索算法（DFS）以栈实现，从根节点开始遍历至最深层，直至找到目标节点或无节点可扩展为止。其优点在于空间复杂度低，但其缺点在于可能会漏掉最短路径，因此不适合用于求最短路径的问题。

启发式搜索算法则是基于具有启发性的搜索策略，例如利用问题领域知识，结合评估函数来指导搜索方向，从而更加高效地求解复杂问题。其中典型的启发式搜索算法包括A*搜索算法等。

相比盲目搜索算法，启发式搜索算法具有更高的效率和准确性，但会涉及到问题领域的先验信息和评估函数设计等问题，因此也存在一些缺点和局限性，例如易受局部最优解影响、评估函数的不确定性和复杂度高等。

2、启发式搜索是什么

PASCAL中的启发式搜索是什么?能举几个例子吗?还有,启发式搜索和双向搜索是NOIP必须要学的吗?

3、启发式搜索全局择优搜索和局部择优搜索的区别是什么

根据问题的实际情况不断寻找可利用的知识，从而构造成一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。

寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个解，即可以找到所需要的问题的答案。这是一种“万能”的方法，理论上，当候选解的数量可以穷尽并且通过检查所有或部分候选解能够得到所需解时，问题就能得到解决。

但是，在实际应用中，因为候选解的数量通常都非常大（比如指数级），并且计算机的速度和内存都有限制，因此对问题不加分析的穷尽算法通常只能解决规模很小的问题。

在实际运用中常采用回溯和分枝定界法对问题进行求解。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。这二种方法由于都是按规定的路线进行，基本没有使用与问题有关的启发性信息，属于盲目搜索策略。在涉及人工职能的有些问题如博弈问题时，还会用到启发是搜索策略，如A*算法等。

一、回溯法和分枝限界法

问题的表示

状态空间表示法是表示问题及其搜索过程的一种形式表示方法。可以用解空间树来表示问题的结构。 对于一棵树，树中的每一个结点确定所求问题的一个问题状态，由根结点到其它结点的所有路径确定了这个问题的状态空间。解状态是一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间的一个元组。答案状态则是由解状态到根的路径。

对于一种状态空间树，可以先系统地生成问题的状态，接着确定问题状态的解状态，最后确定那些解状态是答案状态从而将这些问题解出。

从根结点开始解问题，如果已经生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子的活结点叫E结点，不再进一步扩展或者其儿子结点已经全部生成的生成结点就是死结点。

回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先方法来搜索这些树。

回溯方法的步骤如下：

1) 定义一个解空间，它包含问题的解。

2) 用适于搜索的方式组织该空间。

3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。

回溯算法的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E -节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。

分枝限界法的步骤和回溯的唯一区别是采用了宽度优先的方法来搜索树，因此分枝法消耗的空间比回溯法要多。

这二种搜索策略从本质上来讲都是属于穷尽法的搜索，由于在搜索路径上的不同也造成这二种方法各自都有其优缺点、适用的求解问题也就不同。

宽度优先占有优势的问题：

九宫重排问题

九宫重排问题是一个可以回溯法和分枝法都能解决的问题。但是，对于这个问题运用分枝法是有利的。

九宫重排问题，在3*3的方格棋盘上放置标由数字1、2、3、4、5、6、7、8共8个棋子，初始状态为S 0 ，目标状态为Sg ，当找到一个解时结束搜索。

从根结点到叶子结点的路径即为解，算法为空格左移，空格上移，空格右移，空格下移。

用宽度优先搜索，如下图：

图示解的路径是 S0-3-8-16-26(Sg)

宽度优先搜索的盲目性较大，当目标结点距离初始结点较远时将会产生许多无用结点，空间浪费较大，搜索效率低，但是只要问题有解，用宽度优先搜索总可以得到解，而且得到的路径最短的解。

用深度优先策略搜索，如下图：

在深度优先搜索中，搜索一旦进入某个分枝，就将沿着该分枝一直向下搜索，如果该节点恰好在此分支上，则可较快地得到解。但是，如果目标节电不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。

显然该问题用宽度优先搜索的策略是较好的。

经典的N皇后问题

N皇后问题要求求出N个皇后在棋盘上的所有摆法，（该问题很多书籍上都有详细介绍，这儿图表省略），该问题是适合用回溯法来描述和解决的问题，通过深度优先搜索至多需要检索N!个元组，而如果用分枝法，因为要生成所有问题的解，则必须储存检索过程中的E结点，造成储存空间的极度膨胀，这类问题明显是用回溯法占优势的。

回溯法和分枝法是基本的搜索策略，大多数情况下如果找不到更好的解决方案，总是可以用这二种方法尝试。

但是它们有一个很大的缺陷就是都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。它的效率实在太低，甚至不可完成。

二、启发式搜索算法

通常在搜索中能直接运用回溯、分枝法的问题并不多，回溯和分枝的过程中，施加一定的条件，对搜索过程中出现的结点进行判断，可以提高效率。

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是关键。采用了不同的估价可以有不同的效果。

启发式搜索有很多的算法，如：局部择优搜索法、最好优先搜索法等等。A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。

局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。

局部择优搜索法它是对深度优先搜索方法的一种改进。

全局择优搜索是 局部择优搜索的一种改进，试图克服局部择优搜索的的局限性。再搜索时，每次总是从全体的活结点中选取一个估价值最小的节点，

在搜索过程中，启发式搜索的关键是要确定下一个要考察的节点，用于估价节点重要性的函数称为估价函数

其中g(x)为从初始节点So到节点X已经实际付出的代价；h(x)是从节点X到节点Sg的最优路径的估计代价。h(x)称为启发函数。

九宫重排

d(x)表示节点x的深度，h(x)表示节点x的棋局与目标节点棋局位置不相同的棋子数。

图中节点旁标明的数字是该节点的估价函数值。

该问题的解路径为： So-S1-S2-S3-Sg

以上论述一些树型问题基本的搜索的策略，当问题的状态空间是有向图时，节点的重复将导致大量冗余的搜索，甚至时搜索过程陷入无效的循环而无法找到解，这时就需要对估价函数进行限制，A*算法就是针对图的有序搜索的算法。

问题的求解可以有很多方法，而如何建立数学模型，选择问题的求解方式是十分重要的，方法的好坏是面向一个具体的问题的，需要具体问题具体分析

4、大连海事大学人工智能复试科目

数学科目主要包括高等数学、线性代数、概率论和数理统计等，要求考生具备良好的数学基础，能够熟练掌握数学基本概念和运算方法，并能够运用数学方法解决实际问题。

英语科目主要包括词汇、语法、阅读理解、写作等，要求考生具备良好的英语基础，能够熟练掌握英语基本语法，并能够运用英语进行阅读和写作。

计算机基础知识科目主要包括计算机组成原理、操作系统、数据库、网络、编程语言等，要求考生具备良好的计算机基础知识，能够熟练掌握计算机基本概念和技术，并能够运用计算机技术解决实际问题。

算法和程序设计科目主要包括算法分析、程序设计、数据结构等，要求考生具备良好的算法和程序设计基础，能够熟练掌握算法和程序设计的基本概念和方法，并能够运用算法和程序设计解决实际问题。

解决这些问题的方法和做法步骤主要有：首先，要求考生充分准备，熟悉考试科目的基本知识，并能够熟练掌握考试科目的基本概念和方法；其次，要求考生多做练习，多积累经验，多总结经验，以便在考试中取得好成绩；最后，要求考生在考试中保持良好的心态，充分发挥自己的能力，以便取得更好的成绩。

请添加微信号咨询：19071507959

在线报名

上一篇：启发式,启发式策略有哪些？

下一篇：启发的近义词,启发近义词是什么词