排序点算法

Question

简要说明我想做什么：
假设我们有 14 个数据点，每个数据点的随机坐标在 (-10, -10) 和 (10, 10) 之间，并且它们被分配了一种颜色——红色或蓝色。我希望能够形成必须满足 4 个条件的最多 7 个点的簇：
一个指定集群中可以包含的红色数据点的最大数量，一个指定集群中的最大点数，另一个指定集群中点的最大数量，另一个表示它们的位置必须靠近 - 即我们不能在簇内有 2 个点 (-10, -10) 和 (10, 10).

老实说，我什至不知道从哪里开始，我尝试使用 k-means 排序将数据点组织成簇，但这不满足最大红点数约束。

Answer 1

这里有一些示例 Python 使用 OR-Tools 帮助您入门。

import collections
import math
import random

from ortools.linear_solver import pywraplp


Point = collections.namedtuple("Point", ["x", "y", "is_red"])


def random_point():
    return Point(random.uniform(-10, 10), random.uniform(-10, 10), random.randrange(2))


def close_enough(p, q):
    return math.hypot(p.x - q.x, p.y - q.y) <= 5


def assign(points, max_clusters, max_overall, max_red):
    solver = pywraplp.Solver.CreateSolver("SCIP")
    variables = {
        (i, j): solver.BoolVar("")
        for i in range(len(points))
        for j in range(max_clusters)
    }
    for i in range(len(points)):
        solver.Add(sum(variables[i, j] for j in range(max_clusters)) == 1)
    for i1, p1 in enumerate(points):
        for i2, p2 in enumerate(points):
            if not close_enough(p1, p2):
                for j in range(max_clusters):
                    solver.Add(variables[i1, j] + variables[i2, j] <= 1)
    for j in range(max_clusters):
        solver.Add(sum(variables[i, j] for (i, p) in enumerate(points)) <= max_overall)
    for j in range(max_clusters):
        solver.Add(
            sum(variables[i, j] for (i, p) in enumerate(points) if p.is_red) <= max_red
        )
    status = solver.Solve()
    if status == pywraplp.Solver.OPTIMAL:
        groups = [[] for j in range(max_clusters)]
        for i, p in enumerate(points):
            for j in range(max_clusters):
                if variables[i, j].SolutionValue():
                    groups[j].append(p)
        return groups


if __name__ == "__main__":
    print(assign([random_point() for i in range(14)], 7, 7, 3))

排序点算法

Sorting points algorithm

sorting

algorithm

grouping

constraints