最小生成树移除所有额外的边

Question

额外边缘-由2个点组成的边缘，其中每个点与另一个边相连。我想通过删除这些边来断开MST。最小化新断开MST重量的最佳方法是什么?或者我应该以什么顺序删除这些边(删除一个边可能会影响另一个边)?我的方法是先删除权值最大的多余边?

https://prnt.sc/1xq1msp

在本例中，删除7(CD)->不能再删除任何边。但你也可以去掉B-C，然后去掉D-E这是更好的解决方案

Answer 1

下面是使用kd树的NumPy/SciPy/OR-Tools的精确解决方案枚举可能包含在的边的稀疏子集在求最优解的基础上，编制并求解了一个混合整数规划。但我不确定它是否能满足你的需求;你可以设置一个间隙如果你愿意接受一个近似值，那就限制一下。

import collections
import numpy
import scipy.spatial
from ortools.linear_solver import pywraplp

def min_edge_cover(points):
# Enumerate the candidate edges.
candidate_edges = set()
tree = scipy.spatial.KDTree(points)
min_distances = numpy.ndarray(len(points))
for i, p in enumerate(points):
if i % 1000 == 0:
print(i)
distances, indexes = tree.query(p, k=2)
# Ignore p itself.
d, j = (
(distances[1], indexes[1])
if indexes[0] == i
else (distances[0], indexes[0])
)
candidate_edges.add((min(i, j), max(i, j)))
min_distances[i] = d
for i, p in enumerate(points):
if i % 1000 == 0:
print(i)
# An edge is profitable only if it's shorter than the sum of the
# distance from each of its endpoints to that endpoint's nearest
# neighbor.
indexes = tree.query_ball_point(p, 2 * min_distances[i])
for j in indexes:
if i == j:
continue
discount = (
min_distances[i] + min_distances[j]
) - scipy.spatial.distance.euclidean(points[i], points[j])
if discount >= 0:
candidate_edges.add((min(i, j), max(i, j)))
candidate_edges = sorted(candidate_edges)
# Formulate and solve a mixed integer program to find the minimum distance
# edge cover. There's a way to do this with general weighted matching, but
# OR-Tools doesn't expose that library yet.
solver = pywraplp.Solver.CreateSolver("SCIP")
objective = 0
edge_variables = []
coverage = collections.defaultdict(lambda: 0)
for i, j in candidate_edges:
x = solver.BoolVar("x{}_{}".format(i, j))
objective += scipy.spatial.distance.euclidean(points[i], points[j]) * x
coverage[i] += x
coverage[j] += x
edge_variables.append(x)
solver.Minimize(objective)
for c in coverage.values():
solver.Add(c >= 1)
solver.EnableOutput()
assert solver.Solve() == pywraplp.Solver.OPTIMAL
return {e for (e, x) in zip(candidate_edges, edge_variables) if x.solution_value()}

def random_point():
return complex(random(), random())

def test(points, graphics=False):
cover = min_edge_cover(points)
if not graphics:
return
with open("out.ps", "w") as f:
print("%!PS", file=f)
print(0, "setlinewidth", file=f)
inch = 72
scale = 7 * inch
print((8.5 * inch - scale) / 2, (11 * inch - scale) / 2, "translate", file=f)
for x, y in points:
print(scale * x, scale * y, 1, 0, 360, "arc", "fill", file=f)
for i, j in cover:
xi, yi = points[i]
xj, yj = points[j]
print(
scale * xi,
scale * yi,
"moveto",
scale * xj,
scale * yj,
"lineto",
file=f,
)
print("stroke", file=f)
print("showpage", file=f)

test(numpy.random.rand(100, 2), graphics=True)
test(numpy.random.rand(10000, 2))