时间戳

首页 > 解决方案 > 最小生成树删除所有额外的边

python - 最小生成树删除所有额外的边

问题描述

额外的边 - 由 2 个点组成，每个点都与另一条边相连。我想通过删除这些边缘来断开 MST。将新断开的 MST 的权重最小化的最佳方法是什么，或者我应该以什么顺序删除这些边（删除一个可能会影响另一个）？我的做法是先删除权重最大的额外边？

https://prnt.sc/1xq1msp

在这种情况下，删除 7(CD)-> 不能删除更多的边。但是您也可以删除 BC，然后删除 DE，这是更好的解决方案

标签： pythonalgorithmoptimizationminimum-spanning-tree

解决方案

这是 NumPy/SciPy/OR-Tools 的精确解决方案，它使用 kd-tree 枚举可能包含在最佳解决方案中的边缘的稀疏子集，然后制定并求解混合整数程序。不确定它是否会满足您的需求；如果你愿意接受一个近似值，你可以设置一个间隙限制。

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))

推荐阅读