我在 reddit 上问过这个问题，但还没有找到解决方案。由于我的许多搜索都将我带到了 Stack Overflow，因此我决定尝试一下。这是我的问题的简单表述：
给定一个加权无向图 G(V,E,w) 和 G 中顶点 S 的子集，找到跨越 S 的最小/最大权重树。不允许添加顶点。基本模型的扩展是添加权重为 0 的边和必须排除的顶点。这似乎类似于这里提出的问题：
还可以更深入地了解边缘可以采用的值。每条边实际上是一个相关概率，我可以用几种方式对其进行编码，所以我想问图表的主要问题是：
- 给定 k 个必须连接的顶点，连接它们的顶部 X 最小/最大生成树是什么，它们通过哪些顶点？据我了解，这与询问图表连接所有 k 个顶点的最高概率是多少是同一个问题。
- 越来越模糊，是否有一种合乎逻辑的方式来集群节点？
至于实现，我安装了 boost 库，一旦我让框架解决了这个问题，我就可以处理如何多线程处理它（如果合适的话），使用什么样的图形，以及如何存储/缓存数据，因为顶点和边的数量将非常大。
更新 看看我要解决的问题，它是 NP-complete 是有道理的。我试图解决的现实世界问题涉及医学诊断；特别是当医学界正在考虑一个特定想法的问题时，他们需要退后一步，重新考虑他们是如何到达那里的。我想要从我试图设计的程序中得到的是：
- 鉴于多种情况、测试、症状、年龄、性别、季节、确诊诊断、时间线，您如何将它们联系起来？触及了哪些细胞/组织/器官/系统？他们甚至有关系吗？
- 除了条件/症状可以属于的已定义组之外，有没有办法对条件/症状进行逻辑分组？
例如 流感样症状、红眼、早期肺炎和一些糖尿病症状。有没有办法把所有的症状联系起来？是否可以进行一些测试以使其更容易确定？涉及哪些系统？
尝试将其映射到一个图表或几个图表，并使用概率作为不同症状/条件之间的相关性似乎很自然。