遍历所有区域的最短路径
Shortest path that traverses all regions
我有一个计算问题，在给定一组观察结果的情况下，我想确定能解释所有观察结果的最小现象（解释）集。现象可以相互引起，即所有现象都可以表示为一个未加权的有向图，因果关系为边。
我得到以下信息：
- 所有可能观察结果的详尽列表O_1 ... O_N
- 所有可能现象的详尽列表 (causes/explanations) C_1, ... C_N
- 对于每个观察 O_N，可能导致它的现象列表
- 对于每种现象 C_N，可能导致它的其他现象的列表
问题如下图所示（对图片质量表示歉意）。每个节点都是一种现象，每条边代表现象之间的因果关系。边缘未加权。由更大 "bubble" 勾勒出的每个区域代表一个可能的观察结果，气泡内的所有现象都是已知导致该观察结果的现象的子集。
重申一下，问题是找到穿过图中所有区域的最短路径。 （为简单起见，假设有一条唯一路径可以解释所有观察结果——没有分支，不需要多条路径）。
我的问题如下：
- 这是已知计算问题，还是已知计算问题的变体？
- 是否有解决此特定问题的已知算法（不仅仅是 "use existing shortest path" 算法）？
- 如果没有，我该如何解决这个问题？具体来说，我如何将问题分解为更简单的（即简单的最短路径）问题？
如果对计算可行性有帮助，观察数量为 10,000 数量级，可能现象数量为 100,000 数量级。
一个既不引起观察也不引起另一个现象的现象不会出现在任何最小答案中，所以我们可以假设它们都不存在。换句话说，通过任何算法之一就是摆脱这些"useless"现象。
根据这个假设，我们像对待任何其他顶点一样对待观察结果。由于观察没有任何原因，因此所有观察都是叶顶点。由于所有现象都会引起某种事物（见步骤 1），因此没有现象是叶顶点。因此我们可以简化问题陈述并简单地讨论有向图的叶顶点。
一般来说，不会有一条路径至少到达每片叶子的一个分支顶点。相反，提出问题的更好方法是寻找某种跨越所有叶顶点但不需要跨越现象的最小图。
这是图表 Steiner Tree Problem 的变体。它是 NP 完全的。大多数变体也是 NP 完全的。你最大的希望就是足够好，即近似算法。
你没有明确说明这个假设，但你似乎在假设现象没有循环因果关系（比如 A 导致 B 导致 C 再次导致 A）。在这种情况下，您的问题出在有向无环图上，但这无济于事。有向问题和无向问题一样难。
这是一个结合哈密顿路径问题的集合覆盖问题。让我解释一下：由于每个现象都与一组观察结果相关，因此您可以将每个现象视为集合覆盖问题中的一个集合。我们需要检查每组现象是否一起覆盖了所有观察，看看是否存在该组的哈密顿路径，即 - 存在一条包含该组中所有现象的简单路径。
一种方法是找到最小的集合覆盖（=一组现象）并检查该组是否存在哈密顿路径。然后继续下一个（等于或更大的）集合覆盖，并进行相同的检查，依此类推，直到找到具有哈密顿路径的集合覆盖。这将是最小的现象组，它涵盖了所有观察结果，并且具有遍历该组中所有现象的简单路径。
我有一个计算问题，在给定一组观察结果的情况下，我想确定能解释所有观察结果的最小现象（解释）集。现象可以相互引起，即所有现象都可以表示为一个未加权的有向图，因果关系为边。
我得到以下信息：
- 所有可能观察结果的详尽列表O_1 ... O_N
- 所有可能现象的详尽列表 (causes/explanations) C_1, ... C_N
- 对于每个观察 O_N，可能导致它的现象列表
- 对于每种现象 C_N，可能导致它的其他现象的列表
问题如下图所示（对图片质量表示歉意）。每个节点都是一种现象，每条边代表现象之间的因果关系。边缘未加权。由更大 "bubble" 勾勒出的每个区域代表一个可能的观察结果，气泡内的所有现象都是已知导致该观察结果的现象的子集。
我的问题如下：
- 这是已知计算问题，还是已知计算问题的变体？
- 是否有解决此特定问题的已知算法（不仅仅是 "use existing shortest path" 算法）？
- 如果没有，我该如何解决这个问题？具体来说，我如何将问题分解为更简单的（即简单的最短路径）问题？
如果对计算可行性有帮助，观察数量为 10,000 数量级，可能现象数量为 100,000 数量级。
一个既不引起观察也不引起另一个现象的现象不会出现在任何最小答案中，所以我们可以假设它们都不存在。换句话说，通过任何算法之一就是摆脱这些"useless"现象。
根据这个假设，我们像对待任何其他顶点一样对待观察结果。由于观察没有任何原因，因此所有观察都是叶顶点。由于所有现象都会引起某种事物（见步骤 1），因此没有现象是叶顶点。因此我们可以简化问题陈述并简单地讨论有向图的叶顶点。
一般来说，不会有一条路径至少到达每片叶子的一个分支顶点。相反，提出问题的更好方法是寻找某种跨越所有叶顶点但不需要跨越现象的最小图。
这是图表 Steiner Tree Problem 的变体。它是 NP 完全的。大多数变体也是 NP 完全的。你最大的希望就是足够好，即近似算法。
你没有明确说明这个假设，但你似乎在假设现象没有循环因果关系（比如 A 导致 B 导致 C 再次导致 A）。在这种情况下，您的问题出在有向无环图上，但这无济于事。有向问题和无向问题一样难。
这是一个结合哈密顿路径问题的集合覆盖问题。让我解释一下：由于每个现象都与一组观察结果相关，因此您可以将每个现象视为集合覆盖问题中的一个集合。我们需要检查每组现象是否一起覆盖了所有观察，看看是否存在该组的哈密顿路径，即 - 存在一条包含该组中所有现象的简单路径。
一种方法是找到最小的集合覆盖（=一组现象）并检查该组是否存在哈密顿路径。然后继续下一个（等于或更大的）集合覆盖，并进行相同的检查，依此类推，直到找到具有哈密顿路径的集合覆盖。这将是最小的现象组，它涵盖了所有观察结果，并且具有遍历该组中所有现象的简单路径。