algorithm - 寻找最小/最大权重 Steiner 树

Question

我在 reddit 上问过这个问题，但还没有找到解决方案。由于我的许多搜索都将我带到了 Stack Overflow，因此我决定尝试一下。这是我的问题的简单表述:

给定一个带权无向图 G(V,E,w) 和 G 中顶点 S 的子集，找到跨越 S 的最小/最大权重树。不允许添加顶点。基本模型的扩展是添加权重为 0 的边和必须排除的顶点。这似乎与此处提出的问题类似:

Algorithm to find minimum spanning tree of chosen vertices

还有更多关于边缘可以取什么值的见解。每条边实际上是一个相关概率，我可以用几种方式对其进行编码，所以我想问这个图的主要问题是:

1. 给定 k 个必须连接的顶点，连接它们的前 X 个最小/最大生成树是什么，它们经过哪些顶点？据我了解，这与询问图形连接所有 k 个顶点的最高概率是多少是同一个问题。
2. 变得更加模糊，是否有一种合乎逻辑的方式来对节点进行集群？

至于实现，我已经安装了 boost 库，一旦我的框架开始解决这个问题，我就可以处理如何对其进行多线程处理(如果合适的话)，使用什么样的图，以及如何存储/缓存数据，因为顶点和边的数量会非常大。

更新看看我试图解决的问题，它是 NP 完全的是有道理的。我试图解决的现实世界问题涉及医学诊断；特别是当医学界正在考虑一个特定的想法来解决一个问题时，他们需要退后一步并重新考虑他们是如何到达那里的。我想从我尝试设计的程序中得到的是:

• 给定几个条件、测试、症状、年龄、性别、季节、确诊诊断、时间表，你如何将它们联系起来？触及了哪些细胞/组织/器官/系统？他们甚至有关系吗？
• 除了条件/症状所属的已定义组之外，是否有一种方法可以对条件/症状进行逻辑分组？

例子流感样症状、红眼、早期肺炎和一些糖尿病征兆。有没有办法将所有症状联系起来？是否可以进行一些测试以使其更容易确定？涉及哪些系统？

尝试将其映射到一个或多个图表并使用概率作为不同症状/状况之间的相关性似乎很自然。

Answer 1

我看到您的问题的模型主要基于贝叶斯推理和模糊逻辑。贝叶斯推理网络表达因果关系，例如吸烟和肺癌。看here快速教程。您可以将模糊逻辑应用于该建模，以尝试考虑现实生活中的可变性(因为并非每个人都会患肺癌)。