推箱子路径长估计问题随想

这个算法是我自己想出来的一个随机算法，能够平衡效率与时间

随机路径长估计适用于 IDA* 等算法的启发式函数

算法目的

在搜索算法中，启发式函数常常被设定为 Box 到 BoxTarget 的曼哈顿距离，然而这种启发式函数并不算精准

传统的路径长估计也不可行。例如，在每一次计算 loss 时，都使用 A* 算法进行路径长估计，就会造成本末倒置：

1. 作为离散问题，最优解往往不一定让箱子直接推入目标点，这只是局部最优而非全局最优
2. A* 把一个 $O(1)$ 的算法变成 $O(k^n)$，造成算法的瓶颈，这是不可接受的

因此，这里提出随机路径估计的算法进行路径的估计

算法内容

算法需要一段时间的预处理，这个预处理需要用 A*

预处理

1. 从地图中随机采样一对点，这一对点的曼哈顿距离不太近，也不太远
2. 如果采样点有墙壁，弃去，重采
3. 利用 A* 或 BFS（如果距离不算远）计算这一对点的真实距离
4. 重复以上过程 $k$ 次

正式计算

假定对于两个点 A B，使用以下算法估计 A 和 B 之间的距离：

1. 分别找到离 A B 两点最近的采样点 A' B'
2. 计算曼哈顿距离 $d(A,A')+d(B,B')$，然后加上预先计算好的采样点距离 $d(A',B')$
3. 结果就是 A B 两点的近似距离
4. 如果需要平滑，可以和 A B 两点之间的曼哈顿距离做加权平均

为什么能凑效？

这个算法基于一个重要的假设：一对比较近的点，其曼哈顿距离对真实距离的近似程度，总是高于一对比较远的点，其曼哈顿距离对真实距离的近似程度