performance - 拼图编程 - 无法优化？

Question

我一直在编写程序来解决各种数字难题，但我一直在设计无法优化的不合理复杂的搜索算法。

例如，在一个谜题中，给你一个 3x3 的网格，下面是数字 1 到 9:

123
456
789

您可以沿任何方向循环任何行或列中的数字。下面是将数字的顶行 移到右边 的示例。如果数字位于网格的边缘，它们将循环。

123 -> 312
456    456
789    789

您必须以这种方式移动数字，直到您创建一个幻方，其中每列、每行和对角线上的数字总和为 15。

我已经编写了一个 DFS 蛮力算法来测试所有可能的移动序列，尽管每个回合可用移动的数量呈指数增长(大约 12 ^ [当前回合])，使其变得无用。

BFS 似乎是找到正确着法的最佳选择，但这需要我存储数百甚至数千个网格副本以便回溯!

---

我经常遇到这类问题。 BFS 和 DFS 算法分别使用过多的内存和时间。我需要帮助优化这些算法，以便它们运行得更快、更高效。也许识别数字的模式和关系或为实现目标提供算法逻辑会有所帮助？ (我不知道那会带来什么)。

编辑:

我的固定算法非常有效。学习如何为我的排列编号是必不可少的。谢谢大家!

Answer 1

我建议查找内存(根据输入缓存函数调用的结果，以便不会为相同的后续调用重新计算该函数)。了解内存后，我会查找动态编程(仍然保存函数的结果，但也重新排序计算以消除不必要的调用)。一些动态规划的解释使用斐波那契的递归定义，然后是斐波那契 + 内存，并以计算重新排序结束。

对于一般的 DFS 和 BFS 问题，称为“分支定界”的技术可能很有趣。边界部分可以让你在某些问题上有实质性的收获。修剪比不那么复杂的边界高一级的子树会消除搜索树中的许多新分支(换句话说:由于树随深度呈指数增长，因此尽早修剪搜索很重要)。

对于您的特定问题，我相信优化是可能的。

首先，让我们考虑 DFS。我相信您的电路板的所有排列都可以从电路板的任何配置中获得。作为结果。 DFS 可以在没有回溯的情况下实现(尽管我猜你知道这一点)。深度搜索？ (编辑:根据 Daniel Fischer，这是错误的。一半的状态是可到达的，尽管它不会影响无回溯声明，因为回溯不会帮助您达到无法到达的状态)

但是，您可能会发现您不想仅仅为了发现您尚未解决问题而进行许多排列。回溯实际上可能有所帮助。或者……

考虑一下您的最终目标。幻方有一些特殊的属性，您可以利用这些属性来更仔细地选择您的操作。例如，由于行和列的总和必须为 15，因此您知道 9、8 和 7 不能彼此共享一行或一列。 9 和 6 也不能。6 可以与 8 和 1 或 7 和 2 一起使用。6 不能与 5 和 4 共享一列/行，即使它们总和为 15，因为鸽巢原理(每行/列包含 9 、8 或 7)。事实上，您可能会发现您的问题有一个唯一的解决方案，对所有行、所有列、反射和转置中的某种循环排列取模。对角线要求进一步限制了有效解。

旁白:上一段中使用的逻辑与基于约束的编程没有什么不同。它并不是真正的优化技术(尽管如果不是运行时，它可能被认为是对实现时间的优化)，但您也可能会感兴趣(另请注意，幻方和数独经常用于说明基于约束的编程) .

现在你有了一个目标:

1. 描述解决方案状态。
2. 以最少的步数达到已知解状态之一。

与搜索各种排列直到问题得到解决相比，这是一种根本不同的方法。我会尝试找到一个动态编程解决方案。对于使用增量操作从起始状态移动到目标状态的稍微简单的动态规划问题，请查看 Levenshtein 编辑距离问题。