algorithm - 回溯中是否有 do -> recurse -> undo 模式的名称？

Question

在backtracking ，即用于解决 n 皇后问题的算法，基本上有两种方法可以进行递归调用:

1. 复制父板做子板，修改子板放置新皇后，然后递归调用子板。
2. 直接修改板子，递归调用，然后撤销修改。

第二种是首选，因为它避免了昂贵的复制。

这种选择也存在于其他算法中，例如游戏中的 minimax。

模式 2 是否有与模式 1 相对的名称？

Answer 1

在约束规划和 SAT 求解(您的 n 皇后示例通常来自哪里)中，我认为这些概念被描述为:

• 基于副本
• 基于追踪

例如:

Reischuk, Raphael M., et al. "Maintaining state in propagation solvers." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2009.

Schulte, Christian. "Comparing Trailing and Copying for Constraint Programming." ICLP. Vol. 99. 1999.

前者摘录:

Constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. The solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a propagation solver must determine how to maintain state during propagation and forward and backward search.[...] This paper also provides the first realistic comparison of trailing versus copying for state restoration.

两者各有优缺点，在引用文献中进行了分析。

请记住，线索通常不仅是关于存储您的决定(棋盘布局)，而且还发生了传播(由于alldifferent<，此布局导致了这些现在不可能的布局/em> 传播:这些影响也必须恢复!)。有关此类实现的概述，请参阅:MiniCP