推导时间线/年表的算法

Question

我正在寻找关于算法的线索，以推断出一系列小说的时间线/年表。我将文本分成几天，并创建了它们之间的关系数据库，例如:X是Y之前的一个月，Y和Z是连续的，Z的日期是已知的，X是星期二，等等。有不确定性(‘月’实际上只意味着大约30天)和矛盾。我可以将一些关系标记为比其他关系更可靠，以帮助解决歧义和矛盾。

有什么算法可以从这类数据中推导出最适合的年表，将最高概率的日期分配给每一天？至少时间是一维的，但处理具有不一致性的复杂关系图似乎不是微不足道的。我有CS背景，所以我可以编写一些代码，但一些关于适用算法名称的想法将是有帮助的。我猜我得到的是一个以天为节点，以关系为边的图。

Answer 1

对于你的问题，一个简单粗略的近似方法是在一个有向图中存储像"A发生在B之前“这样的信息，并使用像"A -> B”这样的边。测试图形以查看它是否是有向无环图(DAG)。如果是，那么信息是一致的，因为在发生其他事情之前，有一个一致的年表。您可以通过打印DAG的“拓扑排序”(topsort)获得样本线性年表。如果事件C和D同时发生，或者没有信息说明哪个事件在另一个事件之前发生，则它们可能在顶层显示为ABCD或ABDC。您甚至可以让topsort算法打印所有的可能性(因此ABCD和ABDC)，以便使用更详细的信息进行进一步的分析。

如果您获得的图不是DAG，您可以使用类似Tarjan算法的算法来快速识别“强连接组件”，这些组件是图中包含循环形式的时间矛盾的区域。然后，您可以更仔细地分析它们，以确定可能会删除哪些不太可靠的边来解决矛盾。识别要移除的边缘以消除循环的另一种方法是搜索“最小反馈弧集”。这通常是NP难的，但如果您的强连接组件很小，那么搜索可能是可行的。

Answer 2

约束编程是您所需要的。在基于传播的CP中，您可以在(a)在搜索树中的当前选择点做出决策和(b)尽可能传播该决策的结果之间进行交替。理论上，您可以通过维护每个问题变量x的可能值的域D来实现这一点，这样D(x)就是x的一组值，这些值在当前搜索路径中尚未被排除。在您问题中，您可以将其简化为一大组布尔变量x_ij，其中x_ij为true仅当event i先于event j。对于所有变量，最初都是D(x) = {true, false}。决策就是减少未决定变量的域(对于布尔型变量，这意味着将其域减少到单个值，true或false，这与赋值相同)。

如果您很聪明，您将尝试从每次失败中吸取教训，并根据需要退回到搜索树上，以避免多余的搜索(这称为回跳--例如，如果您确定在级别7到达的死胡同是由您在级别3所做的选择造成的，那么只回溯到级别6是没有意义的，因为对于您在级别3所做的选择，该子树中不存在任何解决方案！)。

现在，如果您对数据有不同程度的置信度，那么您实际上遇到了优化问题。也就是说，您不仅要寻找一个满足所有必须为真的约束的解决方案，而且要根据您对它们的信任程度来最佳地满足其他“软”约束。这里您需要做的是确定一个目标函数，将分数分配给给定的满足/违反的部分约束集。然后，每当您发现当前搜索路径无法改进之前找到的最佳解决方案时，您就想要修剪搜索。

如果您确实决定使用布尔方法，那么您可以研究SAT求解器，它可以解决这些类型的问题。但我首先关注的是MiniZinc，这是一种映射到各种最先进的约束求解器上的CP语言。

祝你好运！