我想不出一种能找到最佳解决方案的高效算法,但是假设您的输入图很密集,那么下面的方法可能会很好地起作用:
将输入图转换G(V, E)
为加权图G'(N, D)
,其中N
是您要覆盖的顶点的子集,并且D
是原始图中相应顶点之间的距离(路径长度)。这会将所有不需要的顶点“折叠”到边中。
计算的最小生成树G'
。
通过以下过程“扩展”最小生成树:对于d
最小生成树中的每个边缘,采用图中的相应路径,G
并将路径上的所有顶点(包括端点)添加到结果集V'
,并将路径中的所有边缘添加到结果集。结果集E'
。
该算法很容易跳闸,给出次优的解决方案。示例情况:等边三角形,其中在角,边的中点和三角形的中间有顶点,并且沿边且从角到三角形的中间有边。为了覆盖角,选择三角形的单个中点就足够了,但是此算法可以选择边。尽管如此,如果图形密集,它应该可以正常工作。