c++ - 广度优先搜索的效率

Question

在无界/无限棋盘上计算从 x1, y1 到 x2, y2 所需的最少跳数的最有效方法是什么？假设我们总能从 x1, y1 生成一组合法的着法。

这听起来是为 BFS 量身定做的，我已经成功实现了一个。但如果 x2, y2 任意大，它的空间和时间复杂度似乎很糟糕。

我一直在研究各种其他算法，如 A*、双向搜索、迭代加深 DFS 等，但到目前为止，我对哪种方法会产生最佳(和完整)解决方案一无所知。我是否缺少一些见解？

Answer 1

如果合法移动集独立于当前空间，那么这似乎是整数线性规划 (ILP) 问题的理想选择。您基本上可以解决每种类型的移动次数，从而使移动总数最小化。例如，对于一个只能向上和向右移动的骑士(因此每次移动都是 x+=1, y+=2 或 x+=2, y+=1，你会最小化 a1+a2，服从 2*a1+a2 == x2-x1, a1+2*a2 == y2-y1, a1 >= 0, a2 >= 0。虽然 ILP 通常是 NP 完全的，但我希望标准的爬山算法能够非常有效地解决它。