我有一个朋友需要计算以下内容:
在完全图Kn(k<=13)中,有k*(k-1)/2条边。每条边可以指向两个方向,因此有2^[(k*(k-1))/2]种不同的情况。
她需要计算P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]
X !-> Y表示“从X到Y没有路径”,P[]表示概率。
因此,暴力算法是检查2^[(k*(k-1))/2]个不同的图形,并且由于它们是完整的,因此在每个图形中,由于对称性,只需要考虑A、B、C、D中的一组。
然后计算P[A !-> B]为“没有路径连接节点1和2的图形数”除以总图形数,即2^[(k*(k-1))/2]。
暴力方法在Mathematica中适用于K8,但她需要K9、K10……直至K13。
显然,我们不需要在这些情况下找到最短路径,只需要找出是否存在一条路径。
任何人有优化建议吗?(这听起来像一个典型的Project Euler问题)。
示例:
最小的图K4有4个顶点,给出6条边。因此,如果我们标记4个顶点A、B、C和D,则有2^6 = 64种可能的方式将边定向。
在某些图形中,从A到B没有路径(假设为X),在另一些图形中,从C到D没有路径(假设为Y)。但在某些图形中,既不存在从A到B的路径,也不存在从C到D的路径。这些是W。
因此,P[A !-> B]=X/64,P[C !-> D]=Y/64,P[A !-> B && C !-> D] = W/64。
更新:
A、B、C和D是4个不同的顶点,因此我们至少需要K4。
请注意,我们正在处理定向图,因此UT矩阵的正常表示不足以说明问题。
Mathematica中有一个函数可以找到定向图中节点之间的距离(如果返回无穷大,则表示没有路径),但这有点过度,因为我们只需要知道是否存在路径即可。
在完全图Kn(k<=13)中,有k*(k-1)/2条边。每条边可以指向两个方向,因此有2^[(k*(k-1))/2]种不同的情况。
她需要计算P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]
X !-> Y表示“从X到Y没有路径”,P[]表示概率。
因此,暴力算法是检查2^[(k*(k-1))/2]个不同的图形,并且由于它们是完整的,因此在每个图形中,由于对称性,只需要考虑A、B、C、D中的一组。
然后计算P[A !-> B]为“没有路径连接节点1和2的图形数”除以总图形数,即2^[(k*(k-1))/2]。
暴力方法在Mathematica中适用于K8,但她需要K9、K10……直至K13。
显然,我们不需要在这些情况下找到最短路径,只需要找出是否存在一条路径。
任何人有优化建议吗?(这听起来像一个典型的Project Euler问题)。
示例:
最小的图K4有4个顶点,给出6条边。因此,如果我们标记4个顶点A、B、C和D,则有2^6 = 64种可能的方式将边定向。
在某些图形中,从A到B没有路径(假设为X),在另一些图形中,从C到D没有路径(假设为Y)。但在某些图形中,既不存在从A到B的路径,也不存在从C到D的路径。这些是W。
因此,P[A !-> B]=X/64,P[C !-> D]=Y/64,P[A !-> B && C !-> D] = W/64。
更新:
A、B、C和D是4个不同的顶点,因此我们至少需要K4。
请注意,我们正在处理定向图,因此UT矩阵的正常表示不足以说明问题。
Mathematica中有一个函数可以找到定向图中节点之间的距离(如果返回无穷大,则表示没有路径),但这有点过度,因为我们只需要知道是否存在路径即可。