人工智能/搜索/启发式搜索/双向搜索
双向搜索是一种算法，它使用两个同时发生的搜索来到达目标目标。双向搜索通常被认为是一种有效的图搜索，因为它不是在大型树中搜索，而是从目标开始进行反向搜索，从起点开始进行正向搜索。这样做的原因是树木会随着其深度的增加而呈指数增长，因此两棵较小的树的面积比一棵大的树要小。一旦两个搜索都完成，它们将在中间交叉以完成路径。搜索相遇之前的部分称为主阶段，而交叉之后的部分称为后处理阶段。重要的是要注意，大多数双向搜索使用启发式方法，这意味着无法确认找到的解决方案是否是最优解决方案。
图搜索算法会系统地遍历图中的节点，直到找到最优解，而启发式搜索只会在短时间内确认某种解决方案。双向搜索的路径通常基于几种不同的其他搜索类型，包括
- 广度优先：每次使用树结构检查目标节点时，将节点添加到列表中，直到找到目标节点
- 最佳优先：将使用节点的评分（通常是 f 值）来选择下一个节点，该评分会考虑其成本和长度
- A*：类似于最佳优先，但会考虑从起点到指定节点的路径成本以及从该节点到目标的成本
路线图
最有效的路线图搜索将是双向搜索与 A* 算法的结合。
- posA(x, y, f) 和 posB (x, y, f)
- 创建一个位置来演示你在两棵搜索树中的当前位置，它将具有一个 x 坐标、一个 y 坐标和一个 f 值来解释路径的成本。
- startPoint (coordX, coordY)
- 从起点节点开始，并带有进一步行进的选项：还提供坐标列表，其中节点演示了朝向目标交点的移动选项。
- endPoint (coordX, coordY)
- 从一个结束位置（节点）开始，它有几个通往它的选项 -
还提供坐标列表，其中节点演示了朝向起始交点的移动选项。
- if posA= posB(x, y)
- 这意味着交叉点，因此结束搜索。
- else 从 startPoint 将 posA 移动到具有最小 f 值的下一个节点，并将 posB 从 endPoint 移动到具有最小 f 值的下一个节点，直到两个点交叉。
注释
- 绿色节点显示应采取的路径，红色节点显示希望的交叉点。
- 更粗的线显示更高的成本，虚线显示 posA 运动和 posB 运动之间的分隔线。
- f-valueA 将考虑从 startPoint 到 posA 的成本以及从 posA 到 posB 的成本。
- f-valueB 将考虑从 endPoint 到 posB 的成本以及从 posB 到 posA 的成本。
1- 需要有关目标状态的具体信息。
2- 当有多个选项时，很难保证交叉点。
3- 计算存储。
虽然双向搜索似乎是最快的搜索选项之一，但在很多情况下它并不实用。例如，如果你正在寻找一个丢失的物品，你无法从你的位置开始搜索，也无法从物品所在的位置开始搜索，因为你不知道它的位置。上面的示例中，如果要从一个地址到达另一个已知位置，则可以使用双向搜索设计。一个可以使用的场景如上面示例所示。
Des Champeaux (1983) 创建了一种算法来克服交叉点问题。该解决方案基本上是进行两次从前到前的搜索，这两个搜索理想情况下会相互指向。然而，这种双向启发式从前到前算法 (BHFFA) 最终被证明在计算上占用太多空间。Politowisky 和 Pohl (1984) 设计了另一种模型来克服 Champeaux 提出的问题。这种称为 d-Node 重新定位的算法能够使用更少的计算空间，并找到一种有效的在中间相遇的方法。Politowisky 和 Pohl 使用 Champeaux 模型提出的想法，使用了一种从前到前的设计，其中起点节点的路径指向目标路径中最有希望的节点，反之亦然。不幸的是，这种算法出现了更多问题，因为它只能用于不可接受的启发式方法，即使这样，解决方案也不总是足够明确。当搜索算法是可接受的时，这意味着搜索将以最低成本的分支结束。
Ghosh 和 Mehanti (1991) 随后尝试解决这些问题，建议使用另一种用于双向搜索的从前到前的启发式算法。这种算法使用预定义的参数来减少计算机存储。他们的算法结合了广度优先搜索和最佳优先搜索。15-puzzle 被用来测试他们的算法。15-puzzle 包含一个棋盘，棋盘上有随机排列的数字的瓷砖，搜索系统必须遍历并按顺序排列瓷砖。结果表明，在判断解决方案质量时，他们的算法比以前提到的算法更成功。
Champeaux, D.D. (1983)。再次进行双向启发式搜索。J. ACM 30, 22-32
Davis, H.W., Pollack, R.B., Sudkamp, T. (1984)。更好地理解双向搜索。AAAI-84 论文集
Ghosh, S., Mahanti, A. (1991)。资源有限的双向启发式搜索。信息处理快报 40, 335-340。
Pijils, W., Post, H. (2006)。一种具有缩短后处理的新型双向搜索算法。欧洲运筹学杂志。
Pohl, I., (1970)。启发式搜索被视为图中的路径查找。人工智能 1 193-204。
Pohl, I., Politowiski, G. (1984)。双向启发式搜索中的 d-Node 重新定位。AAAI-84, 274-277