主页 / 问题 / 1335259
Accepted
Oleg Chaika
Asked:2022-10-05 22:04:33 +0000 UTC2022-10-05 22:04:33 +0000 UTC

直线上 m 个点到 n 个固定点的最小距离

  • 772

问题的正式表述如下：给定直线上的 N 个点，并且序列是非n1, n2, n3 ...递减的。排列 M 个点，使得从最近点ni, n (i + 1) ...到该点的距离之和对于mi最小i = 1 ... M。

问题的非正式解释：在路上安排M个加油站，让住在路边的N个人花尽可能少的时间到达加油站。对于一个加油站来说，条件很简单：加油站左右的人数必须相同。

M<=N

随着加油站数量的增加，任务变得更加复杂。我举了一个在 10 个点中放置 3 个加油站的例子。他们每个人都创建了一个段，并且在加油站左右的这个段上的人数相同。

但是，这不是最佳解决方案。我的假设：为了达到最优，需要一个额外的条件：在右边和左边，这个加油站最近的点数必须相同。下图显示了这种布置的一个示例，实际上，这种情况下的距离总和更小。

问题是我不明白如何在加油站安排阶段检查哪个点最近。这可以在第一张图片中看到：我们将点排列成两边的人数相同，但排列后发现离他们最近的加油站并不是我们预期的加油站。

python

2 个回答

  1. 使用动力学的解决方案O(N^3)。calc_median_distance可以预先对所有可能的值进行预计算。我确信有一个更快的解决方案，但它应该非常简单。

    array = [2, 8, 14, 17, 19, 20, 24, 30, 35, 39]
n = len(array)
m = 3

# считает сумму растояний до медианы на подмассиве [fr, to)
def calc_median_distance(fr, to):
    median_index = (fr + to) // 2
    distance = 0
    for i in range(fr, to):
        distance += abs(array[i] - array[median_index])
    return distance

# d[i1][i2] - лучшее решение (сумма растояний) для точек [0..i1) и i2 заправок
# изначально заполнен каким-то большим значением
# заведомо больше любого возможного решения
maxr = 1000000000
d = [[maxr] * (m + 1) for _ in [0] * (n + 1)]

# s - двумерный массив такого же самого размера
# s[i1][i2] - это длина последнего отрезка для решения d[i1][i2]
# используется для восстановления решения в конце
s = [[0] * (m + 1) for _ in [0] * (n + 1)]

d[0][0] = 0 # решение длиной 0, для 0 заправок

for i2 in range(1, m + 1):
    for i1_from in range(i2 - 1, n):
        for i1_to in range(i1_from + 1, n + 1):

            # решение для подотрезка [0..i1_from) и (i2 - 1) заправок
            prev = d[i1_from][i2 - 1]
            if prev == maxr:
                continue

            # решение для подотрезка [0..i1_to) и i2 заправок
            # строится как {[0..i1_from) для (i2 - 1)} + {[i1_from..i2_to) для 1}
            next = prev + calc_median_distance(i1_from, i1_to);
            if next < d[i1_to][i2]:
                d[i1_to][i2] = next
                s[i1_to][i2] = i1_to - i1_from

print("Best distance = " + str(d[n][m]))

segments = []
i1 = n
i2 = m
while i2 > 0:
    seg = s[i1][i2]
    segments.insert(0, seg)
    i1 -= seg
    i2 -= 1

print("Segments = " + ' '.join(str(x) for x in segments))
    • 6
  2. Best Answer

    理论

    第一个事实。如果有一个加油站，客户想多少就多少，那么最佳的解决方案之一就是将加油站放置在客户阵列的中间位置。

    这里有两个说法：首先，加油站的位置与其中一个客户的位置相吻合，其次，给出了如何选择这个位置的确切方法。

    第二个事实。如果有多个加油站，那么当所有加油站都与客户的坐标重合时，仍然存在最优解。

    一个简单的解决方案

    第二个事实使解决问题变得非常容易：

    # xs - координаты клиентов, ys - координаты АЗС
# возвращает сумму наименьших расстояний от клиентов до АЗС
def dist(xs, ys):
    return sum(min(abs(x - y) for y in ys) for x in xs)

# xs - координаты клиентов, m - число АЗС
# возвращает минимальное расстояние от клиентов до АЗС и расположение АЗС
def baseline(xs, m):
    return min((dist(xs, ys), ys) for ys in itertools.combinations(xs, m))

    该解决方案具有复杂性n * m * Cnk(n, m)，其中n是客户端的数量 ( len(xs))，Cnk-“tse from en po ka”是k尺寸集中的尺寸组合数量n。

    前两个乘数是计算时间dist，最后一个是搜索组合的时间（加油站设置为不同的客户端）。

    我不会优化，这个解决方案仅用于测试。

    递归问题解决

    走向动态规划。为了解决m列的问题，需要将客户端分为两组。右组分配一列，左组分配一m - 1列。在所有此类分区中，需要选择最小值。为简单起见，此函数仅返回距离的总和，不保存加油站的位置：

    @functools.cache
def recursive(xs, m):
    if m == 1:
        ys = xs[len(xs) // 2],
        return dist(xs, ys)

    return min(
        recursive(xs[:j], m - 1) + recursive(xs[j:], 1)
        for j in range(m - 1, len(xs))
    )

    复杂性n * (n * n * m)。左项是计算一列情况下的距离，右项是递归的复杂度。我们用 填满表格n * m。每个单元格都需要n操作来填充。n你可以摆脱一个乘数。更多关于下面的内容。

    快速计算到一列的距离总和

    客户端的坐标xs以非递减顺序给出。从中选择一个子列表xs[j1:j2]。需要找到一个加油站的最佳位置并计算到它的距离之和。

    从第一个事实可以得出，加油站必须放在中间xs[(j1 + j2) // 2]。您可以计算到它的距离总和O(j2 - j1)。有没有办法计算这个金额O(1)。

    的累积和被考虑xs。在他们的帮助下，距离被计算为一个常数。代码不是最愉快的，对不起。

    def make_min_dist1(xs):

    def accumulate(a):
        s = 0
        yield s
        for v in a:
            s += v
            yield s

    sums = tuple(accumulate(xs))

    def min_dist1(j1, j2):
        assert j1 < j2
        j = (j1 + j2) // 2
        y = xs[j]

        # hi_dist = (sums[j2] - sums[j]) - (j2 - j) * y
        # lo_dist = (j - j1) * y - (sums[j] - sums[j1])
        # return lo_dist + hi_dist
        return -((j1 + j2) % 2) * y + sums[j2] + sums[j1] - 2 * sums[j]

    return min_dist1

    动态规划

    动态编程与Zergatul提出的没有区别。缓存更加复杂和紧凑，一列的距离计算是作为一个常数完成的。计算加油站的距离和位置。代码很复杂，再次抱歉：

    def dynamics(xs, m):

    min_dist1 = make_min_dist1(xs)

    n = len(xs)

    if m == 1:
        return min_dist1(0, n), (xs[n // 2], )

    # min_dist(i, j) best solution is in cache[i - 1][j - i + 1]
    cache = []

    def min_dist(i, j):
        # cache[i - 2][j - i + 1] stores best solution for min_dist(i - 1, k) task
        return min(
            (cache[i - 2][k - i + 1][0] + min_dist1(k, j), k)
            for k in range(i - 1, j)
        )
    
    # min_dist(1, j) best solution is in cache[0][j]
    cache.append(tuple((min_dist1(0, j), 0) for j in range(1, n - m + 2)))
    for i in range(2, m):
        # min_dist(i, j) best solution is in cache[i - 1][j - i + 1]
        cache.append(tuple(min_dist(i, j) for j in range(i, n - m + i + 1)))

    d, k = min_dist(m, n)

    def min_point(k):
        yield xs[(k + n) // 2]
        for i in reversed(range(1, m)):
            _, k1 = cache[i - 1][k - i]
            yield xs[(k1 + k) // 2]
            k = k1

    return d, tuple(min_point(k))[::-1]

    这个n * n * m决定的复杂性

    抛物线测试——500个客户，10个加油站0.7秒完成：

    print(*dynamics(tuple(i * i for i in range(500)), 10))

    2803416（2500、17689、36864、59049、84100、110889、139129、168921、199809、232324）

    • 5

相关问题