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

Question

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

对于前。

在骑士巡回赛问题中。

骑士被放置在空棋盘的第一个格子上，根据国际象棋规则走棋，他必须在每个格子里走一趟。

在每个步骤中，有 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=6 的 *n 板，操作顺序不会影响执行时间的任何可见变化，

但如果是 n >= 7

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

Answer 1

从数学/计算机科学的角度来看，这是一个有趣的问题。对于给定的 ，肯定存在一个最有效的排列（或一组排列）n。我不知道是否存在最有效的排列n。我猜不会。在所有n.

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