algorithm - 回溯算法中操作顺序的重要性

Question

回溯算法的每个递归步骤中的操作顺序对该特定算法的效率有多重要？

例如

在骑士之旅问题中。

The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once.

在每一步中，(通常)有 8 种可能的移动方式。

int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };

如果我像这样改变这个顺序......

int xmove[8] = {  -2, -2, 2, 2, -1, -1,  1,  1};
int ymove[8] = {  -1,  1,-1, 1, -2,  2, -2,  2};

现在， 对于 n*n 板 最多 n=6 两者的操作顺序不影响执行时间的任何可见变化，

但是如果是n >= 7

第一个操作(移动)订单的执行时间比后面的少很多。 在这种情况下，生成所有 O(m!) 操作顺序并测试算法是不可行的。那么我如何确定此类算法在特定移动顺序上的性能，或者更确切地说，如何才能达到一个(或一组)操作顺序，以便算法在执行时间方面更有效。

Answer 1

从数学/CS 的角度来看，这是一个有趣的问题。对于给定的 n ，肯定存在一个最有效的排列(或一组排列)。我不知道是否有一个排列在所有 n 中是最有效的。我猜不会。在所有 n 中，可能存在一个“平均”(无论您如何定义)更好的排列。

如果我的任务是找到一个有效的排列，我可能会尝试执行以下操作:我将生成固定数量的 x 随机生成的移动顺序。衡量他们的效率。对于每个随机生成的移动集，随机创建固定数量的接近原始排列的排列。计算它们的效率。现在你有比开始时更多的排列。选择表现最好的 x 并重复。这将提供一些局部最大化算法，但我不知道它是否会导致全局最大化算法。