推导时间线/年表的算法

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-hard，但如果您的强连通组件很小，则搜索可能是可行的。