在回溯中，即用于解决 n-queens 问题的算法，基本上有两种方法可以进行递归调用：
- 复制父板以制作子板，通过放置新皇后来修改子板，然后在子板上进行递归调用。
- 直接修改板子，递归调用，然后撤消修改。
第二种是首选，因为它避免了昂贵的复制。
这种选择也存在于其他算法中，例如游戏中的极小极大。
与模式 1 相比，模式 2 有名称吗？
问问题
63 次
3 回答
3
在约束编程和 SAT 求解（你的 n-queens 示例通常来自哪里）中，我认为这些概念被描述为：
- 基于复制
- 基于跟踪的
参见例如：
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.
前者的摘录：
约束传播求解器交错传播，从变量域中删除不可能的值，并进行搜索。求解器状态在传播过程中被修改。但是搜索需要求解器返回到先前的状态。因此，传播求解器必须确定如何在传播以及前向和后向搜索期间保持状态。[...] 本文还首次对用于状态恢复的尾随与复制进行了现实比较。
两者各有优缺点，在参考文献中进行了分析。
请记住，轨迹通常不仅是关于存储您的决定（棋盘布局），而且还发生了传播（由于传播不同，这种布局导致了这些现在不可能的布局：这些影响也必须恢复！）。有关此类实现的概述，请参阅：MiniCP
于 2021-07-27T16:05:01.947 回答
1
我会说这两者是相同的算法，只是有一个可变或不可变的板。
我还要说，对于n -queens 的特定情况，副本一点也不贵，因为你可以只使用 64 位来表示一个板......你可能花费比调用堆栈的每一级更多的钱:)
于 2021-07-27T16:08:55.963 回答
0
与此相关的一个主题是面向对象编程中的一种设计模式，称为“命令模式”。它有助于根据命令堆栈撤消最近的命令。
于 2021-07-27T16:04:27.010 回答