大师作文网启发式搜索全局择优搜索和局部择优搜索的区别是什么
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/10 11:47:19
启发式搜索全局择优搜索和局部择优搜索的区别是什么
根据问题的实际情况不断寻找可利用的知识,从而构造成一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索.
寻找问题的解的一种可靠的方法是首先列出所有候选解,然后依次检查每一个解,即可以找到所需要的问题的答案.这是一种“万能”的方法,理论上,当候选解的数量可以穷尽并且通过检查所有或部分候选解能够得到所需解时,问题就能得到解决.
但是,在实际应用中,因为候选解的数量通常都非常大（比如指数级）,并且计算机的速度和内存都有限制,因此对问题不加分析的穷尽算法通常只能解决规模很小的问题.
在实际运用中常采用回溯和分枝定界法对问题进行求解.按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）.这二种方法由于都是按规定的路线进行,基本没有使用与问题有关的启发性信息,属于盲目搜索策略.在涉及人工职能的有些问题如博弈问题时,还会用到启发是搜索策略,如A*算法等.
一、回溯法和分枝限界法
问题的表示
状态空间表示法是表示问题及其搜索过程的一种形式表示方法.可以用解空间树来表示问题的结构. 对于一棵树,树中的每一个结点确定所求问题的一个问题状态,由根结点到其它结点的所有路径确定了这个问题的状态空间.解状态是一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这解空间的一个元组.答案状态则是由解状态到根的路径.
对于一种状态空间树,可以先系统地生成问题的状态,接着确定问题状态的解状态,最后确定那些解状态是答案状态从而将这些问题解出.
从根结点开始解问题,如果已经生成一个结点而它的所有儿子结点还没有全部生成,则这个结点叫做活结点.当前正在生成其儿子的活结点叫E结点,不再进一步扩展或者其儿子结点已经全部生成的生成结点就是死结点.
回溯算法使用深度优先方法搜索树结构,而分枝定界一般用宽度优先方法来搜索这些树.
回溯方法的步骤如下：
1) 定义一个解空间,它包含问题的解.
2) 用适于搜索的方式组织该空间.
3) 用深度优先法搜索该空间,利用限界函数避免移动到不可能产生解的子空间.
回溯算法的特性是在搜索执行的同时产生解空间.在搜索期间的任何时刻,仅保留从开始节点到当前E -节点的路径.因此,回溯算法的空间需求为O（从开始节点起最长路径的长度）.
分枝限界法的步骤和回溯的唯一区别是采用了宽度优先的方法来搜索树,因此分枝法消耗的空间比回溯法要多.
这二种搜索策略从本质上来讲都是属于穷尽法的搜索,由于在搜索路径上的不同也造成这二种方法各自都有其优缺点、适用的求解问题也就不同.
宽度优先占有优势的问题：
九宫重排问题
九宫重排问题是一个可以回溯法和分枝法都能解决的问题.但是,对于这个问题运用分枝法是有利的.
九宫重排问题,在3*3的方格棋盘上放置标由数字1、2、3、4、5、6、7、8共8个棋子,初始状态为S 0 ,目标状态为Sg ,当找到一个解时结束搜索.
从根结点到叶子结点的路径即为解,算法为空格左移,空格上移,空格右移,空格下移.
S0
Sg
2
8
3
1
2
3
1
4
8
4
7
6
5
7
6
5
用宽度优先搜索,如下图：
f'(x) = g(x) + h(x)
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
1 4
7 6 5
8 2
2 1 4
7 6 5
2 3 4
1 8
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
3 8 2
1 4
7 6 5
2 8 3
1 6
7 5 4
2 8 3
6 4
1 7 5
2 8 3
1 4 5
7 6
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
2 8
1 4 3
7 6 5
2 8 3
7 1 4
6 5
2 8 3
7 4
6 1 5
8 1 3
2 4
7 6 5
8 3 2
2 1 4
7 6 5
1 2 3
8 4
7 6 5
16
26
9
8
7
6
2
1
S0
4
3
5
Sg
图示解的路径是 S0-3-8-16-26(Sg)
宽度优先搜索的盲目性较大,当目标结点距离初始结点较远时将会产生许多无用结点,空间浪费较大,搜索效率低,但是只要问题有解,用宽度优先搜索总可以得到解,而且得到的路径最短的解.
用深度优先策略搜索,如下图：
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
1 6
7 5 4
1
S0
2
2 8
1 6 3
7 5 4
2 8 1 6 3
7 5 4
2 8
1 6 3
7 5 4
3
4
5
6
在深度优先搜索中,搜索一旦进入某个分枝,就将沿着该分枝一直向下搜索,如果该节点恰好在此分支上,则可较快地得到解.但是,如果目标节电不在此分支上,而该分支又是一个无穷分支,则就不可能得到解.
显然该问题用宽度优先搜索的策略是较好的.
经典的N皇后问题
N皇后问题要求求出N个皇后在棋盘上的所有摆法,（该问题很多书籍上都有详细介绍,这儿图表省略）,该问题是适合用回溯法来描述和解决的问题,通过深度优先搜索至多需要检索N!个元组,而如果用分枝法,因为要生成所有问题的解,则必须储存检索过程中的E结点,造成储存空间的极度膨胀,这类问题明显是用回溯法占优势的.
回溯法和分枝法是基本的搜索策略,大多数情况下如果找不到更好的解决方案,总是可以用这二种方法尝试.
但是它们有一个很大的缺陷就是都是在一个给定的状态空间中穷举.这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了.它的效率实在太低,甚至不可完成.
二、启发式搜索算法
通常在搜索中能直接运用回溯、分枝法的问题并不多,回溯和分枝的过程中,施加一定的条件,对搜索过程中出现的结点进行判断,可以提高效率.
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标.这样可以省略大量无畏的搜索路径,提到了效率.在启发式搜索中,对位置的估价是关键.采用了不同的估价可以有不同的效果.
启发式搜索有很多的算法,如：局部择优搜索法、最好优先搜索法等等.A*也是.这些算法都使用了启发函数,但在具体的选取最佳搜索节点时的策略不同.
局部择优搜索法,就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点,父亲节点,而一直得搜索下去.这种搜索的结果很明显,由于舍弃了其他的节点,可能也把最好的节点都舍弃了,因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳.
局部择优搜索法它是对深度优先搜索方法的一种改进.
全局择优搜索是 局部择优搜索的一种改进,试图克服局部择优搜索的的局限性.再搜索时,每次总是从全体的活结点中选取一个估价值最小的节点,
在搜索过程中,启发式搜索的关键是要确定下一个要考察的节点,用于估价节点重要性的函数称为估价函数
f'(x) = g(x) + h(x)
其中g(x)为从初始节点So到节点X已经实际付出的代价；h(x)是从节点X到节点Sg的最优路径的估计代价.h(x)称为启发函数.
九宫重排
当用全局择优搜索求解该问题时,可以设估价函数为 f'(x) = d(x) + h(x)
d(x)表示节点x的深度,h(x)表示节点x的棋局与目标节点棋局位置不相同的棋子数.
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
1 4
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
4
6
4
6
6
4
1
S0
4
4
5
Sg
1 2 3
7 8 4
6 5
5
5
S3
S2
S1
图中节点旁标明的数字是该节点的估价函数值.
该问题的解路径为： So-S1-S2-S3-Sg
以上论述一些树型问题基本的搜索的策略,当问题的状态空间是有向图时,节点的重复将导致大量冗余的搜索,甚至时搜索过程陷入无效的循环而无法找到解,这时就需要对估价函数进行限制,A*算法就是针对图的有序搜索的算法.
问题的求解可以有很多方法,而如何建立数学模型,选择问题的求解方式是十分重要的,方法的好坏是面向一个具体的问题的,需要具体问题具体分析
寻找问题的解的一种可靠的方法是首先列出所有候选解,然后依次检查每一个解,即可以找到所需要的问题的答案.这是一种“万能”的方法,理论上,当候选解的数量可以穷尽并且通过检查所有或部分候选解能够得到所需解时,问题就能得到解决.
但是,在实际应用中,因为候选解的数量通常都非常大（比如指数级）,并且计算机的速度和内存都有限制,因此对问题不加分析的穷尽算法通常只能解决规模很小的问题.
在实际运用中常采用回溯和分枝定界法对问题进行求解.按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）.这二种方法由于都是按规定的路线进行,基本没有使用与问题有关的启发性信息,属于盲目搜索策略.在涉及人工职能的有些问题如博弈问题时,还会用到启发是搜索策略,如A*算法等.
一、回溯法和分枝限界法
问题的表示
状态空间表示法是表示问题及其搜索过程的一种形式表示方法.可以用解空间树来表示问题的结构. 对于一棵树,树中的每一个结点确定所求问题的一个问题状态,由根结点到其它结点的所有路径确定了这个问题的状态空间.解状态是一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这解空间的一个元组.答案状态则是由解状态到根的路径.
对于一种状态空间树,可以先系统地生成问题的状态,接着确定问题状态的解状态,最后确定那些解状态是答案状态从而将这些问题解出.
从根结点开始解问题,如果已经生成一个结点而它的所有儿子结点还没有全部生成,则这个结点叫做活结点.当前正在生成其儿子的活结点叫E结点,不再进一步扩展或者其儿子结点已经全部生成的生成结点就是死结点.
回溯算法使用深度优先方法搜索树结构,而分枝定界一般用宽度优先方法来搜索这些树.
回溯方法的步骤如下：
1) 定义一个解空间,它包含问题的解.
2) 用适于搜索的方式组织该空间.
3) 用深度优先法搜索该空间,利用限界函数避免移动到不可能产生解的子空间.
回溯算法的特性是在搜索执行的同时产生解空间.在搜索期间的任何时刻,仅保留从开始节点到当前E -节点的路径.因此,回溯算法的空间需求为O（从开始节点起最长路径的长度）.
分枝限界法的步骤和回溯的唯一区别是采用了宽度优先的方法来搜索树,因此分枝法消耗的空间比回溯法要多.
这二种搜索策略从本质上来讲都是属于穷尽法的搜索,由于在搜索路径上的不同也造成这二种方法各自都有其优缺点、适用的求解问题也就不同.
宽度优先占有优势的问题：
九宫重排问题
九宫重排问题是一个可以回溯法和分枝法都能解决的问题.但是,对于这个问题运用分枝法是有利的.
九宫重排问题,在3*3的方格棋盘上放置标由数字1、2、3、4、5、6、7、8共8个棋子,初始状态为S 0 ,目标状态为Sg ,当找到一个解时结束搜索.
从根结点到叶子结点的路径即为解,算法为空格左移,空格上移,空格右移,空格下移.
S0
Sg
2
8
3
1
2
3
1
4
8
4
7
6
5
7
6
5
用宽度优先搜索,如下图：
f'(x) = g(x) + h(x)
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
1 4
7 6 5
8 2
2 1 4
7 6 5
2 3 4
1 8
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
3 8 2
1 4
7 6 5
2 8 3
1 6
7 5 4
2 8 3
6 4
1 7 5
2 8 3
1 4 5
7 6
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
2 8
1 4 3
7 6 5
2 8 3
7 1 4
6 5
2 8 3
7 4
6 1 5
8 1 3
2 4
7 6 5
8 3 2
2 1 4
7 6 5
1 2 3
8 4
7 6 5
16
26
9
8
7
6
2
1
S0
4
3
5
Sg
图示解的路径是 S0-3-8-16-26(Sg)
宽度优先搜索的盲目性较大,当目标结点距离初始结点较远时将会产生许多无用结点,空间浪费较大,搜索效率低,但是只要问题有解,用宽度优先搜索总可以得到解,而且得到的路径最短的解.
用深度优先策略搜索,如下图：
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
1 6
7 5 4
1
S0
2
2 8
1 6 3
7 5 4
2 8 1 6 3
7 5 4
2 8
1 6 3
7 5 4
3
4
5
6
在深度优先搜索中,搜索一旦进入某个分枝,就将沿着该分枝一直向下搜索,如果该节点恰好在此分支上,则可较快地得到解.但是,如果目标节电不在此分支上,而该分支又是一个无穷分支,则就不可能得到解.
显然该问题用宽度优先搜索的策略是较好的.
经典的N皇后问题
N皇后问题要求求出N个皇后在棋盘上的所有摆法,（该问题很多书籍上都有详细介绍,这儿图表省略）,该问题是适合用回溯法来描述和解决的问题,通过深度优先搜索至多需要检索N!个元组,而如果用分枝法,因为要生成所有问题的解,则必须储存检索过程中的E结点,造成储存空间的极度膨胀,这类问题明显是用回溯法占优势的.
回溯法和分枝法是基本的搜索策略,大多数情况下如果找不到更好的解决方案,总是可以用这二种方法尝试.
但是它们有一个很大的缺陷就是都是在一个给定的状态空间中穷举.这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了.它的效率实在太低,甚至不可完成.
二、启发式搜索算法
通常在搜索中能直接运用回溯、分枝法的问题并不多,回溯和分枝的过程中,施加一定的条件,对搜索过程中出现的结点进行判断,可以提高效率.
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标.这样可以省略大量无畏的搜索路径,提到了效率.在启发式搜索中,对位置的估价是关键.采用了不同的估价可以有不同的效果.
启发式搜索有很多的算法,如：局部择优搜索法、最好优先搜索法等等.A*也是.这些算法都使用了启发函数,但在具体的选取最佳搜索节点时的策略不同.
局部择优搜索法,就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点,父亲节点,而一直得搜索下去.这种搜索的结果很明显,由于舍弃了其他的节点,可能也把最好的节点都舍弃了,因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳.
局部择优搜索法它是对深度优先搜索方法的一种改进.
全局择优搜索是 局部择优搜索的一种改进,试图克服局部择优搜索的的局限性.再搜索时,每次总是从全体的活结点中选取一个估价值最小的节点,
在搜索过程中,启发式搜索的关键是要确定下一个要考察的节点,用于估价节点重要性的函数称为估价函数
f'(x) = g(x) + h(x)
其中g(x)为从初始节点So到节点X已经实际付出的代价；h(x)是从节点X到节点Sg的最优路径的估计代价.h(x)称为启发函数.
九宫重排
当用全局择优搜索求解该问题时,可以设估价函数为 f'(x) = d(x) + h(x)
d(x)表示节点x的深度,h(x)表示节点x的棋局与目标节点棋局位置不相同的棋子数.
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
1 4
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
4
6
4
6
6
4
1
S0
4
4
5
Sg
1 2 3
7 8 4
6 5
5
5
S3
S2
S1
图中节点旁标明的数字是该节点的估价函数值.
该问题的解路径为： So-S1-S2-S3-Sg
以上论述一些树型问题基本的搜索的策略,当问题的状态空间是有向图时,节点的重复将导致大量冗余的搜索,甚至时搜索过程陷入无效的循环而无法找到解,这时就需要对估价函数进行限制,A*算法就是针对图的有序搜索的算法.
问题的求解可以有很多方法,而如何建立数学模型,选择问题的求解方式是十分重要的,方法的好坏是面向一个具体的问题的,需要具体问题具体分析