Jam*_*ton 8 algorithm graph-algorithm
我正在寻找算法上的线索,以推断出一系列小说的时间表/年表.我把文本拆分成几天并创建了一个关系数据库,例如:X是Y,Y和Z连续前的一个月,Z的日期已知,X是星期二,等等.有不确定性( '月'实际上只意味着大约30天),也是矛盾.我可以将某些关系标记为比其他关系更可靠,以帮助解决歧义和矛盾.
有哪种算法可以从这类数据中推导出最合适的年表,为每天分配最高概率的日期？至少时间是一维的,但处理具有不一致性的复杂关系图似乎是非平凡的.我有一个CS背景,所以我可以编写代码,但对适用算法的名称有所了解会有所帮助.我猜我所拥有的是一个图表,其中天为节点,关系为边缘.
约束编程正是您所需要的。在基于传播的 CP 中，您可以交替执行 (a) 在搜索树中的当前选择点做出决策和 (b) 尽可能远地传播该决策的结果。D理论上，您可以通过为每个问题变量维护一个可能值的域来实现此目的x，该域是当前搜索路径中尚未排除的D(x)值集。x在您的问题中，您也许可以将其简化为一大组布尔变量 ，x_ij其中x_ijiff eventi先于 event ，其中 为 true j。最初D(x) = {true, false}适用于所有变量。决策只是减少未确定变量的域（对于布尔变量，这意味着将其域减少为单个值，true 或 false，这与赋值相同）。如果搜索路径上的任何一点D(x)对于任何 都变为空x，则您已到达死胡同并且必须原路返回。
如果你很聪明，你会尝试从每次失败中学习，并根据需要向后退到搜索树以避免冗余搜索（这称为回跳- 例如，如果你发现你到达了死胡同）第 7 级的问题是由您在第 3 级所做的选择引起的，仅回溯到第 6 级是没有意义的，因为考虑到您在第 3 级所做的选择，此子树中不存在解决方案！）。
现在，考虑到您对数据有不同程度的置信度，您实际上遇到了优化问题。也就是说，您不仅要寻找一种满足所有必须正确的约束的解决方案，而且还要根据您对其他“软”约束的信任程度，最好地满足其他“软”约束。您在这里需要做的是确定一个目标函数，为一组给定的满足/违反的部分约束分配分数。然后，每当您发现当前搜索路径无法改进先前找到的最佳解决方案时，您就需要修剪搜索。
如果您确实决定采用布尔方法，那么研究 SAT 求解器可以有效解决此类问题。但我首先要考虑的是MiniZinc，这是一种 CP 语言，它映射到各种最先进的约束求解器。
祝你好运！