algorithm - 遍历所有区域的最短路径

Question

我有一个计算问题，给定一组观察结果，我想确定解释所有观察结果的最小现象(解释)集。现象可以相互因果，即所有现象都可以表示为一个无权有向图，因果关系为边。

我得到以下信息:

• 所有可能观察结果的详尽列表 O_1 ... O_N
• 所有可能现象(原因/解释)的详尽列表 C_1，... C_N
• 对于每个观察结果 O_N，列出可能导致该观察结果的现象
• 对于每种现象 C_N，列出可能导致该现象的其他现象

该问题以图表形式表示如下(对于图片质量表示抱歉)。每个节点都是一种现象，每条边代表现象之间的因果关系。边缘未加权。由更大的“气泡”勾勒出的每个区域都代表一个可能的观察结果，气泡内的所有现象都是已知导致该观察结果的现象的子集。

重申一下，问题是找到穿过图中所有区域的最短路径。 (为简单起见，假设有一条唯一的路径可以解释所有观察结果 - 没有分支，不需要多个路径)。

我的问题如下:

1. 这是一个已知的计算问题，还是已知计算问题的变体？
2. 是否有已知的算法可以解决这个特定问题(不仅仅是“使用现有的最短路径”算法)？
3. 如果不是，我该如何解决这个问题？具体来说，如何将问题分解为更简单(即简单的最短路径)问题？

如果对计算可行性有帮助的话，观测数量约为 10,000 个，可能现象的数量约为 100,000 个。

Answer 1

既不引起观察也不引起其他现象的现象不会出现在任何最小答案中，因此我们可以假设其中不存在任何一个。换句话说，通过任何一种算法就可以摆脱这些“无用”的现象。

有了这个假设，我们就像对待任何其他顶点一样对待观察结果。由于观察不会产生任何结果，因此所有观察都是叶顶点。由于所有现象都会导致某些现象(参见步骤 1)，因此没有现象是叶顶点。这样我们就可以简化问题陈述，简单讨论有向图的叶顶点。

一般来说，不会有一条路径能够到达每片叶子的至少一个分支顶点。相反，提出问题的更好方法是寻找某种跨越所有叶顶点的最小图，但不需要跨越现象。

这是 Steiner Tree Problem 的变体在图表上。它是 NP 完全的。大多数变体也是 NP 完全的。您最大的希望就是有足够好的东西，即近似算法。

您没有明确说明这个假设，但您似乎假设现象不存在循环因果关系(例如 A 导致 B 导致 C 再次导致 A)。在这种情况下，您的问题是有向无环图，但这没有帮助。有向问题和无向问题一样难。