找到在给定半径内服务最多其他城市的城市

Question

我需要解决的主要问题是：

给定一个覆盖半径 r（单位是英里），我需要找到最少数量的设施，每个设施都要设置在数据集中128个城市中的一个位置，以确保这128个城市中的每一个都在某个设施的 r 英里范围内。

data=[Cities, Population, Coordinates, Distances]

对于这个问题，我只关心数据中的城市和距离两个子列表（如上所述）。城市列表包含128个城市，距离列表包含128个子列表，每个子列表里有128个城市之间的距离。

举个例子，假设

Cities= [cityA, cityB, cityC, cityD]

那么

Distances= [[0,25,50,75],[25,0,30,40], [50,30,0,45], [75,40,45,0]]

（这些距离是完全虚构的）在距离列表的每个子列表中，距离对应于城市列表中的城市索引，所以子列表中的第一个距离总是该城市到第一个城市（cityA）的距离，第二个距离是该城市到第二个城市（cityB）的距离。

我已经有一个看起来像这样的辅助函数：

def nearbyCities(name, r, data) :
''' Returns a list of cities within distance r of named city
    sorted in alphabetical order.
    Returns an empty list if city name is invalid. '''

cities = data[0]
distances = data[3]

result = []
if name in cities :                # If the city name is valid
    i = cities.index(name)           # Get the index of the named city
    for j in range(len(cities)) :      # For every other city
        if distances[i][j] <= r :      # If within r of named city
            result = result + [cities[j]]  # Add to result
result.sort() 
return result

我需要写一个名为 def locateFacilities(data, r) 的函数。这个函数返回的城市列表应该按字母顺序排列。这个函数应该实现描述的贪心算法：

设施位置的贪心算法：

1. 最开始所有城市都没有服务
2. 当还有城市没有服务时：选择一个城市 c，使其能服务最多的未服务城市，标记城市 c 和所有在 c 半径 r 英里内的城市为已服务。

在 locateFacilities 函数中，你可能需要使用一个额外的数据结构，叫做 served，用来跟踪哪些城市已经被设施服务过。served 数据结构可以简单地是一个长度为128的布尔列表，初始值全为 False。这个列表中位置 i 的元素表示城市 i（即城市列表中位置 i 的城市）是否已经被服务过。一旦定义了这样的数据结构，你就可以找出对于任何给定城市 c，在半径 r 内有多少个尚未服务的城市（你应该为此写一个函数！）。如果你实现了这一点，贪心算法就会反复选择一个城市 c，使得在 c 半径 r 内的“未服务”城市数量最大。

我能在脑海中用英语理清我需要做的事情，但在把它写成代码时真的很挣扎。

Answer 1

从问题描述中，你已经可以写出一部分的 locateFacilities 函数了，这并不需要太多复杂的思考（当然，写这个代码的方法有很多，但我们还是按照作业中推荐的数据结构来做吧）：

def locateFacilities(data, r):
    n = len(data[0])

    served = [False] * n
    facilities = []
    while not all(served):
        # 1. Find city with most unserved neighbors
        # 2. Place a facility in this city, i.e.:
        #   - Mark city and neighbors as served
        #   - Put city name in list of facilities
        # 3. Repeat

    facilities.sort()
    return facilities

你已经知道如何在 while 循环中处理一部分代码，不过我觉得用城市的索引来工作会比用城市名称更简单。

Answer 2

如果不知道具体的数据结构，那就有点难搞了。所以下面这个getDistance函数就显得很神奇。

下面的代码我没有测试，因为我没有数据，但也许可以给你一些灵感：

def getDistance (city1, city2):
    #magic happens here
    #maybe return data [3] [city1.dix] [city2.idx]
    return #the distance between cities

class City:
    def __init__ (self, idx, name):
        self.idx = idx
        self.name = name

    def makeNeighbours (self, cities, radius):
        self.neighbours = [city for city in cities
            if city is not self and getDistance (self, city) <= r]

    def removeNeighbour (self, city):
        if city not in self.neighbours: return
        self.neighbours.remove (city)

    def __eq__ (self, other):
        return self.idx == other.idx


def locateFacilities (cities, radius):
    cities = [City (idx, name) for idx, name in enumerate (data [0] ) ]
    for city in cities: city.makeNeighbours (cities, radius)
    facilities = []
    while cities:
        mostNeighbours = sorted (cities, key = lambda c: -len (c.neighbours) ) [0]
        for city in cities:
            city.removeNeighbour (mostNeighbours)
        for city in mostNeighbours.neighbours:
            cities.remove (city)
        cities.remove (mostNeighbours)
        facilities.append (mostNeighbours)
    print ('Place facilities at:')
    for facility in facilities:
        print (facility.name)