我在reddit上问过这个问题,但还没有收敛到解决方案。由于我的许多搜索将我带入Stack Overflow,因此我决定尝试一下。下面是我的问题的一个简单公式:寻找最小/最大重量斯坦纳树
给定一个加权无向图G(V,E,w)和G中顶点S的子集,找到跨越S的最小/最大权重树。添加顶点不是允许。基本模型的扩展是添加0重量的边,以及必须排除的顶点。这似乎类似的问题在这里问:
Algorithm to find minimum spanning tree of chosen vertices
也有更深入的了解什么值的边缘可以采取。每个边缘实际上是一个相关的概率,这是我可以通过多种方式进行编码,所以我想问一下图表中的主要问题是:
- 鉴于k个顶点必须连接,有什么顶的X最小/最大跨越连接它们的树,以及它们通过哪些顶点?据我了解,这是问问题图形相同的问题是什么是连接所有k个顶点的最高概率。
- 变得更模糊,有没有一种逻辑的方法来聚集节点?
至于实现,我已经安装了boost库,一旦我得到框架在这个问题上滚动,我可以处理如何多线程它(如果适当),使用什么样的图,以及如何存储/缓存数据,因为顶点和边的数量将非常大。
更新 看看我想解决的问题,这是有道理的,它将是NP完全。我试图解决的现实世界问题涉及医学诊断;特别是当医学界在考虑某个具体想法的问题时,他们需要退后一步并重新考虑他们如何到达那里。我想从我想要设计的程序中获得如下结果:
- 鉴于几种情况,测试,症状,年龄,性别,季节,确诊诊断,时间表,您如何与他们联系?什么细胞/组织/器官/系统被触摸?他们甚至有关系吗?
- 除了条件/症状可以属于的定义组之外,有没有办法将条件/症状进行逻辑分组?
例 流感样症状,目赤,早期肺炎,有的糖尿病的迹象。有没有办法将所有症状联系起来?是否有一些测试可以做,以便于确定?涉及哪些系统?
试图将其映射到一个图或几个图并将概率用作不同症状/条件之间的相关性似乎很自然。
这个问题是NP难的,所以没有已知的高效算法。你可能不得不蛮力寻找答案。 – templatetypedef 2013-02-13 17:31:12
不幸的是,这也是我想出来的。有关如何高效并行化的想法?你认为什么样的图表实现是最好的;可能是邻接矩阵? – NuclearAlchemist 2013-02-13 18:07:52