1

我正在解决 SCC 的两个可满足性问题，并且有一个关于拓扑排序的问题。我所基于的算法是以反向拓扑顺序处理 SCC，当它们全部连接时这很好。我的算法在这样的情况下被打破：

3 3
-2 3
1 -2
-2 -1

这使得图表看起来像这样： 问题图

此图中有两个源和两个汇，并且根据您从哪里开始有多个拓扑排序，因此有两个可能的最终节点。没有循环，因此每个节点都是一个 SCC。从源到接收器有多条路径，所以当我执行反向拓扑顺序时，我可以从接收器 x3 或接收器 !x2 开始。能给我正确答案的路径是从 !x2 开始，这将导致 1、-2、-3 或 -1、-2、-3，这两者都是解决方案。但如果我从 x3 开始，一个可能的结果是 -1、2、3，这不是解决方案。

所以当我查看我的两个接收器时，我如何从拓扑上决定哪个是最后一个？显然答案是！x2，但我试图弄清楚算法将如何确定它。我看到四个可能的想法：

  • !x2 是最后一个，因为它有更多的节点通向它
  • !x2 是最后一个，因为它位于较长路径的末端
  • 在我开始处理任何东西之前设置每个接收器的真值
  • 没有办法知道哪个是最后一个，所以创建所有可能的解决方案并测试它们中的每一个，看看它是否有效。

或者有什么关于拓扑排序 SCC 的问题吗？这是基于我在早期课程中通过强连通分量作业的算法，所以它不会完全错误。

4

1 回答 1

1

如果没有看到您的代码，我无法确定，但我的猜测是，当您处理文字时，您正在设置一个值，然后当您在拓扑顺序中更深地遇到它的否定时将其翻转。关键是一旦你设置了一个变量，你就不能再改变它了。跳过任何已经具有设定值的变量的文字。

编辑添加：从您的评论中我想我看到了问题。当 !x2 在反向拓扑排序中排在第一位时，您提到将变量 x2 设置为 true。您应该将文字!x2 设置为 true，这意味着您将变量x2 设置为 false。如果你这样做，那么无论你从哪个接收器开始，你的求解器都应该工作。

于 2017-04-02T19:19:25.230 回答