我一直在编写程序来解决各种数字难题，但我一直在设计无法优化的不合理复杂的搜索算法。
例如，在一个谜题中，给你一个 3x3 的网格，下面是 1 到 9 的数字：
123
456
789
您可以在任何方向上循环任何行或列中的数字。下面是一个将顶行数字向右移动的示例。如果数字位于网格边缘，则数字将循环。
123 -> 312
456 456
789 789
您必须以这种方式移动数字，直到创建一个幻方，其中每列、每行和对角线中的数字之和为 15。
我编写了一个 DFS 蛮力算法来测试所有可能的移动序列，尽管每回合可用移动的数量呈指数增长（大约 12 ^ [当前回合]），使其毫无用处。
BFS 似乎是找到正确移动的最佳选择，但这需要我存储数百个甚至数千个网格副本才能回溯！
我一直遇到这类问题。BFS 和 DFS 算法分别使用过多的内存和时间。我需要帮助优化这些算法，以便它们运行得更快、更有效。也许识别数字的模式和关系或赋予算法逻辑以实现目标会有所帮助？（我不知道那会带来什么）。
编辑：
我的固定算法就像一个魅力。学习如何给我的排列编号是必不可少的。谢谢你们！
我建议查找 memoization（根据输入缓存函数调用的结果，以便不会为相同的后续调用重新计算该函数）。了解了记忆后，我会查找动态编程（仍然保存函数的结果，但也重新排序计算以消除不必要的调用）。动态规划的一些解释使用斐波那契的递归定义，然后是斐波那契 + 记忆化，并以计算重新排序结束。
对于一般的 DFS 和 BFS 问题，称为分支定界的技术可能会引起人们的兴趣。边界部分可以让你在一些问题上获得可观的收益。修剪比不那么复杂的边界高一代的子树会消除搜索树中的许多新分支（替代措辞：由于树随着深度呈指数增长，因此尽早修剪搜索很重要）。
对于您的特定问题，我相信优化是可能的。
首先，让我们考虑 DFS。我相信您的电路板的所有排列都可以从电路板的任何配置中获得。作为结果。DFS 可以在没有回溯的情况下实现（尽管我猜你知道这一点）。仅深度搜索？（编辑：根据 Daniel Fischer，这是错误的。一半的状态是可以到达的，尽管它不会影响 no-backtracking 语句，因为回溯不会帮助您达到无法到达的状态）
但是，您可能会发现您不想通过许多排列来仅仅发现您尚未解决问题。回溯实际上可能会有所帮助。或者...
考虑看看你的最终目标。魔方有一些特殊的属性，您可以利用这些属性来更仔细地选择您的操作。例如，由于行和列的总和必须为 15，因此您知道 9、8 和 7 不能彼此共享行或列。9 和 6 也不能。6 不能与 8 和 1 或 7 和 2 一起使用。6 不能与 5 和 4 共享列/行，即使它们的总和为 15，因为鸽子洞原理（每行/列包含 9 , 8 或 7)。事实上，您可能会发现您的问题有一个独特的解决方案，以所有行、所有列、反射和转置中的某种循环置换为模。对角线要求进一步限制了有效解决方案。
另外：上一段中使用的逻辑与基于约束的编程没有什么不同。它并不是一种真正的优化技术（尽管如果不是运行时间，它可能被认为是对实现时间的优化），但您可能也会感兴趣（另请注意，魔方和数独经常用于说明基于约束的编程） .
现在你有一个目标：
这是一种与搜索各种排列直到问题解决的根本不同的方法。我会尝试找到一个动态编程解决方案。对于从开始状态移动到具有增量操作的目标状态的稍微简单的动态规划问题，请查看 Levenshtein 编辑距离问题。
除了 ccoakley 的好答案和 stubbscroll 的评论之外，还有一些关于具体示例和一些一般原则的评论。
关于 stubbscroll 说这个特定问题只有 9 个！= 362880 种不同的状态：
将排列编码为数字的一种（相当简单的）方法是通过字典顺序对排列进行索引。例如
0 1 2 3 --> 0
0 1 3 2 --> 1
0 2 1 3 --> 2
...
1 0 2 3 --> 6
1 0 3 2 --> 7
...
3 1 2 0 --> 21
3 2 0 1 --> 22
3 2 1 0 --> 23
诀窍是在阶乘基数中编写索引，
n = a_1 * 1! + a_2 * 2! + a_3 * 3! + a_4 * 4! + ...
哪里0 <= a_k <= k。如果您有s符号，则索引范围从 0 到 s!-1，因此您s-1在 n, 的阶乘基展开式中有系数(a_1,a_2,...,a_(s-1))。然后找到索引为 n 的排列如下
for i = 1 to s-1
the i-th symbol becomes the (a_(s-i)+1)-th smallest unused symbol
the last symbol is the left over one
既然不是特别清楚，举个例子。假设我们寻找索引 4231 为 {1,2,3,4,5,6,7,8} 的排列。首先我们将 4231 扩展为阶乘基数
4231 = 1 + 2*2115 : a_1 = 1
2115 = 0 + 3* 705 : a_2 = 0
705 = 1 + 4* 176 : a_3 = 1
176 = 1 + 5* 35 : a_4 = 1
35 = 5 + 6* 5 : a_5 = 5
5 = 5 + 7* 0 : a_6 = 5
所有进一步的系数（这里只是 a_7）都是 0。最好按照相反的顺序编写 a_i，（a_7，a_6，...a_1），所以
coefficients symbols choice
0,5,5,1,1,0,1 1,2,3,4,5,6,7,8 1
5,5,1,1,0,1 2,3,4,5,6,7,8 7
5,1,1,0,1 2,3,4,5,6,8 8
1,1,0,1 2,3,4,5,6 3
1,0,1 2,4,5,6 4
0,1 2,5,6 2
1 5,6 6
- 5 5
结果：17834265。
找到 246351 的索引：
symbols count perm index(head)
1,2,3,4,5,6 6 2,4,6,3,5,1 1 a_5 = 1
1,3,4,5,6 5 4,6,3,5,1 2 a_4 = 2
1,3,5,6 4 6,3,5,1 3 a_3 = 3
1,3,5 3 3,5,1 1 a_2 = 1
1,5 2 5,1 1 a_1 = 1
索引是`1 * 5！+ 2 * 4！+ 3 * 3！+ 1*2！+ 1 * 1！= 187。
所以现在我们有了一种相当简单的方法来在排列和它们的索引之间进行转换。转换速度不是很快 (O(s^2))，但您可以轻松快速地进行比较和查找（我以前见过这种状态吗？）。在每种情况下，这是否是一种收益仍有待决定。
现在，对于手头的特定情况，我们有一些进一步的限制来减少搜索空间。
因此，这些移动的所有组合也是偶数排列，这意味着一半的可能状态是不可达的。我们（最多）剩下 9!/2 = 181440 个可达状态。通过字典顺序索引甚至排列只是稍微复杂一些。关键点是，当且仅当其索引的阶乘展开中的系数 a_k 之和为偶数时，置换是偶数。
使用约束和对称性减少搜索空间。如果您使用具有所有可能状态的结构的搜索策略，这将相应地减少内存需求。如果您的搜索策略仅涉及可达状态，则约束不会减少步骤数，但由于内存占用较少，它们仍然可以加快搜索速度。对称性的使用可以通过识别等效状态来减少步骤数。
在示例问题中，我们有更好的情况，即 5 已经在正确的位置，并且最优解永远不会移动它。所以我们只需要考虑 8 个符号的偶数排列，将搜索空间减少到 8!/2 = 20160 个可能的状态。（虽然这并不明显。）
然而，一般来说，很难证明最优解永远不会留下可能状态的特定子集，因此您很少可以直接对搜索施加这样的限制。
但通常情况下，您可以使用这样的限制找到问题的良好解决方案，然后在您搜索无限制搜索空间中的最佳解决方案时使用该良好解决方案进行早期修剪。
人们经常使用的一种变体是通过贪心策略找到近似值，并将其用作穷举搜索早期修剪的界限。
尝试使用 A*。您可以使用曼哈顿距离的启发式方法，从数字所在的位置到它们应该在的位置。我假设您已经将幻方作为目标状态。
这个整体问题没有一般性的答案。对特定情况有特定的答案——但也有一些特定的情况，可以在数学上证明没有比蛮力算法要求的答案明显更好的答案。
在许多情况下，寻找最佳算法的问题是一个活跃的研究问题，非常聪明的人正在努力解决这个问题，但收效甚微。
您可能会发现阅读有关“NP 完整性”的内容很有趣，因为它只是这个问题的一小部分，但却是一个经过充分研究的问题。
