英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
保证中间相遇的双向搜索
拿山 R. 斯特蒂文特丹佛大学计算机科学系（sturtevant@cs.du.e du）
古尼·沙龙
本-古里安大学ISE系
以色列贝尔谢瓦
（gunisharon@gmail）.
com）
阿里尔·菲尔纳 本 - 古里安大学 ISE 系
色列贝尔谢瓦（felner@bgu.ac .il）
罗伯特 C. 霍特
加拿大艾伯塔大学计算科学系
加拿大埃德蒙顿T6G 2E8 （rholte@ualberta.ca ）
摘要
我们提出MM，它是第一个双向启发式搜索算法，其前向和后向搜索保证“在中间相遇”，即从不将节点扩展到中点解之外。我们还提出了一个新框架来比较MM、A*和蛮力搜索，并确定了有利于每种算法的条件。最后，我们提出支持我们的理论分析的实验结果。
（Bi-BS）的比较有两个主要结论，请参阅第3节）：
BK1：如果Uni-HS扩展的节点中有一半以上的节点具有Uni-HS，节点数将比Bi-HS少。gle; Clowast;/ 2，其中Clowast;是最佳解决方案成本。
BK2：如果少于一半的节点由UniHS扩展
使用启发式h有gle;Clowast;/ 2，那么将h添加到Bi-BS不会减少它扩展的节点数量。
Barker和Korf所做的一个中心假设是，包含双向搜索的前向和后向搜索决不会扩展一个节点的g值（在给定的di-反应）超过Clowast;/ 2。我们说如果双向搜索有这个属性，它就会“在中间相遇”。
这个假设在应用它们的理论时产生了一个困难，因为在所有情况下都不能保证已知的Bi-HS算法在中间相遇。关于“从前到前”1Bi-HS的论文通常声称他们的搜索符合。但他们当中没有一个具有这种效果的定理。（Arefin and Saha 2010; de Champeaux 1983; de Champeaux and Sint 1977; Davis，Pollack，and Sudkamp 1984; Eckerle 1994; Politowski and Pohl 1984）
Bi-HS算法（Auer and Kaindl 2004; Ikeda et al.1994; Kaindl and Khorsand 1994; Kwa 1989; Pohl 1969; Sad-hukhan 2012）没有专门设计用于在中间相遇，并且他们通常不会。 例如，在河内的Barker和Korf#39;s Towers实验中，BS *（Kwa 1989）经常在每个方向的深度13处扩展节点，尽管溶液长度Clowast;最多为16。为了弥补这一点，我们提出了一种新的前端到端Bi-HS al- gorithm，MM，保证在中间相遇。MM0是MM的蛮力（h（s）= 0 s）版本。我们还提出了一个比较MM0，单向蛮力搜索（Uni-BS），MM和A *的新框架，该框架允许精确表征状态空间的区域将通过一种方法而不是另一种扩大。 我们用它来确定一种方法将扩展节点的条件，以及保证BK1正确性的条件。我们还表明，与单向搜索不同，向Bi-BS添加非零启发式（对于每个非目标节点= 0）可能会导致它扩展更多节点。 例如，MM比MM0 /中的一个扩展节点多4倍我们的煎饼拼图实验。总的来说，我们的实验Pancake Puzzle和Rubik#39;s Cube上表明，根据所使用的启发式，扩展最少节点的算法可以是Uni-HS，MM0或MM中的任何一种。虽然我们引入了一种新算法（MM），但我们不这样做 提出了MM与现有Bi-HS算法的实验比较，并且我们没有声称MM0和MM是最小化运行时间或扩展节点数量方面的最佳双向搜索算法。 这些问题超出了本文的范围。 像巴克和科夫的论文一样， 本文是理论性的。MM的意义在于它是 只有我们的分析和Barker和Bi-HS算法Korf#39;s适用。 这些理论为在中间相遇的双向搜索算法提供了强有力的理由。 作为其第一个品种，MM代表了一种新的方向，开发具有竞争力的Bi-HS算法。 对MM进行全面的实证评估是我们今后将要进行的一项重要研究。
图1：不同地区的图示
注释：版权所有Qc2016，人工促进协会 （www.aaai.org）
在双向启发式搜索中，有两种不同的方法来定义启发式函数（Kaindl and Kainz 1997）。 用于前向搜索的“前端到端”启发式hF（n）和用于后向搜索的hB（n）直接估计从节点n到搜索目标的距离（前向搜索的目标是目标，向后搜索的目标是开始状态）。 相比之下，“前端到前端”启发式方法间接估计从n到搜索目标的距离。 对于前向搜索，它被定义为h（n）= minmisin;OpenB{h（n，m） gB（m）}其中OpenB是后向搜索的开放列表，h（n，m）是函数估计
任意两个节点之间的距离，gB（m）是后向搜索中节点m的g值。 类似地定义向后搜索的前端启发式。
2 定义和术语
问题实例是一个状态空间中的状态对（开始，目标），其中所有边权重都是非MM在两个方向上执行类似A *的搜索，除了MM以新颖的方式对打开列表中的节点进行排序。 打开F，prF（n）上的节点n的优先级被定义为：负的。搜索算法1：MM的伪代码的目的是找到从开始到目标的最低成本路径。d（u，v）是距离状态的距离（最低成本路径的成本）v。Clowast;= d（start，goal）是最佳解决方案的代价。 我们使用通常的符号-f，g，Open等，并使用gmin和f min作为Open上的最小g-和f-值。 我们有两个搜索方向的变量的单独副本，下标（F或B）表示方向：正向搜索：fF，gF，hF，OpenF，Closed TF67）等。 向后搜索：fB，gB，hB，OpenB，ClosedB等。我们假设每个搜索方向使用可接受的前端到端（Kaindl和Kainz 1997）启发式。
如果d（s，goal）Clowast;/ 2，并且“远离目标”，我们说状态s是“接近目标”。 如果Clowast;/ 2 lt;d（开始，s）le;Clowast;/ 2， “远离开始”，我们做一个三方面的区分：s是“接近开始” ）Clowast;和“远程”if le;
d（start，s）gt; Clowast;。 这些类别划le;分了状态空间划分为图1所示的6个不相交区域。我们表示这些地区由两个字母缩写。第一个字母表示从开始的距离（N =近，F =远，R =远程），第二个字母表示距离目标的距离（N =近，F =远）。 例如，FN是远离开始和接近目标的一组状态。 神经网络仅包含那些处于最佳解决方案中点的状态。 本文中没有一种搜索算法扩展了RF中的状态。
在第4-7节中，我们比较MM0，MM，Uni-BS和A *，主要基于它们在每个区域中扩展的节点。 res名称表示状态集合和数量在该地区的国家。 我们将使用等式和不等式中的名称。包含两个算法的不等式，例如A * lt;MM，表示一个算法（本例中为A *）比另一个算法扩展更少的节点。
3 MM：一种新颖的Bi-HS算法
MM在两个方向上执行类似A *的搜索，除了MM以新颖的方式对打开列表中的节点进行排序。 打开F，prF（n）上的节点n的优先级被定义为：prF（n）= max（fF（n），2gF（n））。
算法1：MM的伪代码
gF (start) := gB(goal) := 0; OpenF := {start};
OpenB := {goal}; U := infin;
while (OpenF = empty;) and (OpenB = empty;) do
C := min(prminF , prminB)
if U le; max(C, fminF , fminB, gminF gminB ) then
return U
if C = prminF then
// Expand in the forward direction
choose n isin; OpenF for which prF (n) = prminF and gF (n) is minimum
move n from OpenF to ClosedF
for each child c of n do
if c isin; OpenF cup; ClosedF and gF (c) le; gF (n) cost(n, c) then
continue
if c isin; OpenF cup; ClosedF then
remove c from OpenF cup; ClosedF
gF (c) := gF (n) cost(n, c) add c to OpenF
if c isin; OpenB then
U := min(U, gF (c) gB(c))
Else
// Expand in the backward direction, analogously
return infin;
prB（n）的定义是类似的。 我们使用prminF和prminB分别为OpenF和OpenB的最低优先级，C = min
（prminF，prminB）。 在每一次迭代中，MM以优先级C扩
展节点。U是到目前为止找到的最便宜的解决方案的成
本。 最初是无限的，只要找到更好的解决方案，U就会更新。 当U时MM停止 U le; max(C, fminF , fminB, gminF gminB )
其中E是状态空间中最便宜的边的成本。
最大值内的最后三项中的每一项都是通过继续搜索，可能找到的任何解决方案的成本的下限。 因此，如果U小于或等于它们中的任何一个，则其最优性得到保证并且MM可以安全地进行
停止。当U le; C因C le; Clowast;直到找到所有最优解而停止时是安全的。 ( (Holte et al. 2015)第十条定理). 因此, U le; C 表明 U = Clowast;.
MM具有以下属性：
（P1）MM的向前（向后）搜索永远不会扩展远离或远离开始（目标）的状态，即其向前和向后搜索在中间相遇。
（P2）MM永远不会扩展f值超过C的节点lowast;。
（P3）MM返回Clowast;。
（P4）如果存在从开始到目标和MM的路径
启发式是一致的，MM永远不会将状态扩展两次。
(Holte et al. 2015)给出了MM具有这些属性的完整证明。 在这里，我们提供P1，MM独特性质的证明简图。 当g（n）gt; h（n）时，2g（n）大于f（n）。 如果n远离或远离开始（目标），这使得prF（n）gt; Clowast; （prB（n）gt; Clowast;）。 如果m即将开始（目标），在任何最优路径上，prF（m）le;Clowast;（prB（m）le;Clowast;）。 从而，
图2：MM0不需要扩展具有gF (n) lt; Clowast;/2 或 gB (n) lt; Clowast;/2.的所有节点。
在MM扩展远离或远离开始和远离目标的任何节点之前，将找到最佳解决方案。 2g（n）项还保证远离或远离开始（目标）但接近目标（开始）的节点将通过MM的向后（向前）搜索（如果它完全展开）进行扩展。 因此，pr（n）中的2g（n）项保证了性质P1。 全文共13014字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11845]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
