寻找最小/最大重量斯坦纳树

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快速教程。您可以将模糊逻辑应用到该建模中，以尝试考虑现实生活中的可变性（因为不是每个人都患有肺癌）。