益智编程 - 无法优化？

发布于 2024-12-25 11:21:30 字数 706 浏览 0 评论 0原文

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

例如，在一个谜题中，您将获得一个由数字 1 到 9 组成的 3x3 网格，如下所示：

123
456
789

您可以在任意方向上循环任意行或列中的数字。下面是将顶行数字移至右侧的示例。如果数字位于网格边缘，则数字将循环。

123 -> 312
456    456
789    789

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

我编写了一个 DFS 强力算法测试所有可能的移动序列，尽管每回合可用的移动数量呈指数增长（大约 12 ^ [当前回合]），使其毫无用处。

看来 BFS 是找到正确动作的最佳选择，但这需要我存储数百甚至数千个网格副本才能回溯！

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

编辑：

我的固定算法就像一个魅力。学习如何对排列进行编号至关重要。谢谢大家！

原文

I've been writing programs to solve various number puzzles, but I'm constantly designing unreasonably complex search algorithms that I can't optimize.

For example, in one puzzle, you are given a 3x3 grid of numbers 1 through 9 below:

123
456
789

You're allowed to cycle the numbers in any row or column in any direction. Below is an example of shifting the top row of numbers to the right. The numbers will loop if they are at the edge of the grid.

123 -> 312
456    456
789    789

You must move the numbers in this manner until you create a magic square in which the sum of the numbers in each column, row, and diagonal is 15.

I've written a DFS brute-force algorithm to test all possible sequences of moves, though the number of available moves at each turn increases exponentially (approx. 12 ^ [current turn]), rendering it useless.

It seems a BFS would be optimal to find the correct moves, but that would require me to store hundreds if not thousands of copies of the grid in order to backtrack!

I run into these kinds of problems all the time. Both BFS and DFS algorithms use too much memory and time, respectively. I need help optimizing algorithms like these so they run faster and efficiently. Maybe recognizing patterns and relations of the numbers or giving the algorithm logic to work towards a goal would help? (I don't know what that would entail).

EDIT:

My fixed algorithm works like a charm. Learning how to number my permutations was essential. Thank you all!

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

寒江雪… 2025-01-01 11:21:30

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

对于一般的 DFS 和 BFS 问题，称为分支定界的技术可能会很有趣。边界部分可以让你在某些问题上获得实质性的收获。与不太复杂的边界相比，修剪子树高一代会消除搜索树中的许多新分支（替代措辞：由于树随深度呈指数增长，因此尽早修剪搜索很重要）。

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

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

但是，您可能会发现您不想要经历许多排列只是为了发现你还没有解决问题。回溯实际上可能会有所帮助。或者......

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

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

现在您有一个目标：

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

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

I'd suggest looking up memoization (caching the results of a function call based on the inputs so that the function is not recomputed for identical subsequent calls). Having understood memoization, I'd look up dynamic programming (still saving the results of the function, but also reordering computations to eliminate unnecessary calls). Some explanations of dynamic programming use a recursive definition of fibonacci, then fibonacci + memoization, and finish with computation reordering.

For DFS and BFS problems in general, the technique known as Branch and Bound might be of interest. The bounding part can give you substantial gains in some problems. Trimming a subtree one generation higher than with a less sophisticated bound eliminates many new branches in your search tree (alternate wording: since trees grow exponentially with depth, pruning your search early is important).

For your particular problem, I believe that optimizations are possible.

First, let's consider the DFS. I believe that all permutations of your board are reachable from any configuration of the board. As a consequence. DFS can be implemented without backtracking (though I'm guessing you knew that). Depth only search? (EDIT: per Daniel Fischer, this is wrong. Half of states are reachable, though it doesn't impact the no-backtracking statement since backtracking won't help you reach your unreachable states)

But, you might find that you don't want to move through many permutations simply to find that you haven't yet solved the problem. Backtracking might actually help. Or...

Consider looking at your end goal. Magic squares have some particular properties that you might exploit to choose your operations more carefully. For example, since the rows and columns must sum to 15, you know 9, 8, and 7 cannot share a row or a column with each other. Neither can 9 and 6. 6 can go with 8 and 1 or 7 and 2. 6 cannot share a column/row with 5 and 4 even though they sum to 15 because of the pigeon-hole principle (each row/column contains either 9, 8, or 7). In fact, you might find that your problem has a unique solution, modulo some sort of cyclic permutation in all-rows, all-columns, reflection, and transposition. The diagonal requirement further constrains the valid solutions.

Aside: the logic used in the previous paragraph is not unlike constraint-based-programming. It's not really an optimization technique (though it might be considered an optimization on implementation time if not run time), but might be of interest to you as well (also note that magic squares and sudoku are frequently used to illustrate constraint-based programming).

Now you have a goal:

Describe a solution state.
Reach one of the known solution states with the fewest moves.

This is a fundamentally different approach than searching the various permutations until the problem is solved. I'd try to find a dynamic programming solution. For a slightly easier dynamic programming problem that moves from a start state to a goal state with incremental operations, take a look at the Levenshtein edit distance problem.

回复收藏 0 原文

扭转时空 2025-01-01 11:21:30

除了 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，因此您在 n 的阶乘基础展开中具有 s-1 系数，(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 few remarks in addition to ccoakley's nice answer and stubbscroll's comment, concerning the specific example and a few general principles.

Regarding stubbscroll's remark that this particular problem has only 9! = 362880 different states:
One (fairly easy) way to encode permutations as numbers is indexing the permutations by lexicographic ordering. For example

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

The trick is writing the index in factorial base,

n = a_1 * 1! + a_2 * 2! + a_3 * 3! + a_4 * 4! + ...

where 0 <= a_k <= k. If you have s symbols, the indices range from 0 to s!-1, so you have s-1 coefficients in the factorial-base expansion of n, (a_1,a_2,...,a_(s-1)). The permutation with index n is then found as follows

 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

Since that's not particularly clear, an example. Say we look for the permutation with index 4231 of {1,2,3,4,5,6,7,8}. First we expand 4231 in factorial base

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

all further coefficients (here just a_7) are 0. It's better to follow writing the a_i in reverse order, (a_7,a_6,...a_1), so

 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

Result: 17834265.

Find the index of 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

index is `1*5! + 2*4! + 3*3! + 1*2! + 1*1! = 187.

So now we have a fairly simple way of converting between permutations and their indices. The conversion isn't super fast (O(s^2)), but you get easy and fast comparison and lookup (have I seen the state before?). Whether it's a gain remains to be decided in each case.

Now, for the particular case at hand, we have some further restrictions reducing the search space.

Each move is a cyclic permutation of three elements, thus an even permutation.

Hence all combinations of such moves are also even permutations, meaning half of the possible states are unreachable. We are left with (at most) 9!/2 = 181440 reachable states. Indexing even permutations by lexicographic ordering is only slightly more complicated. The crucial point is that a permutation is even if and only if the sum of the coefficients a_k in the factorial-base expansion of its index is even.

Reduce the search space using constraints and symmetries. If you're employing a search strategy using a structure with all possible states, this will reduce the memory requirements by a corresponding factor. If your search strategy only touches reachable states, the constraints don't reduce the number of steps, but they can still speed up the search due to the lower memory footprint. The use of symmetries can reduce the number of steps by identifying equivalent states.

In the example problem, we have the further nice situation that the 5 is already in the correct place, and that an optimal solution doesn't move it ever. So we need only consider even permutations of 8 symbols, reducing the search space to 8!/2 = 20160 possible states. (Though that is not obvious.)

In general, however, it is difficult to prove that an optimal solution never leaves a particular subset of the possible states, so you can rarely directly impose such a restriction to your search.
But it is often the case that you can find a good solution of the problem using such a restriction and then use the good solution to prune early in your search for the optimal solution in the unrestricted search space.

A variant one can often use is finding an approximation by a greedy strategy and using this as a bound to prune early in an exhaustive search.

回复收藏 0 原文