时间戳

首页 > 解决方案 > K中心问题的特定变体的实现

python - K中心问题的特定变体的实现

问题描述

我正在尝试在 python 中实现 K 中心问题的特定变体（如果我没记错的话）。在互联网上的一些帮助下，我能够实现其中的一部分（不完整），但我在完全实现算法方面遇到了困难。这是我要解决的问题的完整定义。

输入：整数n、p、s、p路径（元组）列表和 s 场景列表。

任务：对于每个场景，任务是确定新医院的位置，以使任何位置与其最近的医院之间的最大距离最小。如果有多个最佳位置，则选择数量最多的一个。此外，不要选择任何已经包含医院的位置。

输出： s 个整数的列表（每个场景的最佳位置）。

例子

输入 ：

n = 10, m = 11, s = 5

roads =
[(1, 3)
 (3, 8)
 (8, 9)
 (9, 7)
 (8, 7)
 (7, 0)
 (0, 6)
 (6, 4)
 (4, 5)
 (4, 2)
 (1, 4)]
 
scenarios =
[[0,2,3,4,5,6,7,8,9],
 [],
 [4],
 [6,8],
 [9,1,8]]

输出：

ret = [1, 6, 9, 4, 7]

场景0：

[0,2,3,4,5,6,7,8,9]

在此处输入图像描述

输入对应上图。位置是圆圈，道路是线段。已经包含医院的位置以灰色阴影显示。在第一个场景（场景 0）中，已经建立了 n-1 家医院。因此，只有一个位置没有医院：位置 1。

场景一：

[]

在此处输入图像描述

在第二种情况下，还没有医院建设。如果我们在位置 0、1、3 或 6 上建造我们的医院，那么到任何其他位置的最大距离最多为 3。请注意，更小的距离是不可能的。由于 6 是 {0, 1, 3, 6} 中最大的数字，我们选择位置 6。

场景二：

[4]

在此处输入图像描述

在第三种情况下，位置 4 上已经有一家医院。如果我们在位置 0、3、7、8 或 9 上建造医院，那么从任何位置到最近的医院的最大距离最多为 2。请注意，更小的距离是不可能的。由于 9 是 {0, 3, 7, 8, 9} 中最大的数字，我们选择位置 9。

场景 3：

[6,8]

在此处输入图像描述

在第四个场景中，已经有两家医院：一个在位置 6，另一个在位置 8。与 6 或 8 相邻的所有位置与某个医院的距离为 1。唯一距离较大的位置是 1、2 和 5。如果我们在位置 4 上建立我们的医院，那么它们的距离变为 1。如果医院的总数小于 n，则距离小于 1 是不可能的。因此，我们选择位置 4。

场景四：

[9,1,8]

在此处输入图像描述

在第五个场景中，已经有 3 家医院：位置 1、8 和 9。任何位置与最近的医院的距离最多为 2。独立地，我们在哪里建造下一个医院，最大距离不会减少。因此，就距离而言，任何位置都是最佳的。因此，我们选择尚未包含医院的具有最高优先级的位置：7。

以下是我到目前为止的代码，它不完整，也可能不正确。

def create_adjacency_matrix(roads,size):
  a = [[0 for j in range(size)] for i in range(size)]
  for i, j in roads:
    a[i][j] = a[j][i] = 1
  return a

def maxindex(dist, n):
    mi = 0
    for i in range(n):
        if (dist[i] > dist[mi]):
            mi = i
    return mi
 
def selectKcities(n, weights, k,scenario):
    dist = [0]*n
    centers = []
 
    for i in range(n):
        dist[i] = 10**9
         
    # index of city having the
    # maximum distance to it's
    # closest center
    max = 0
    for i in range(k):
        centers.append(max)
        for j in range(n):
 
            # updating the distance
            # of the cities to their
            # closest centers
            dist[j] = min(dist[j], weights[max][j])
 
        # updating the index of the
        # city with the maximum
        # distance to it's closest center
        max = maxindex(dist, n)
 
    # Printing the maximum distance
    # of a city to a center
    # that is our answer
    # print()
    print(dist[max])
    for i in centers:
        print(i, end = " ")


def buildHospital(n,m,s,roads,scenarios):
    ret = [-1 for _ in range(0,s)]

    a = create_adjacency_matrix(roads,n)
    for sc in scenarios:
        selectKcities(n, a,1, sc)
    return ret

你可以假设

如果你们能帮助我完成我的代码（或帮助重写它的更好版本）并提供一些解释，我将非常感激。如果您帮助使解决方案尽可能节省时间，我也将不胜感激。谢谢！

标签： pythonpython-3.xalgorithmtime-complexity

解决方案

推荐阅读