我需要帮助使用包裹递送列表调整算法以找到最短路径

Question

我正在从事一个关于数据结构和算法的大型项目，该项目将获取带有特殊注释的包裹清单，并将它们组织到 3 辆卡车上，找到最短的运送路线，然后运送。

我已经使用 Dijkstra 创建了一个字典来优化数据，该字典包含两个位置之间的最短距离，由位置 ID 表示。

我现在正在研究的部分是创建一个算法，该算法将获取卡车的位置 ID 列表，并从中心 ID 开始，找到最近的邻居。然后我需要从最近的邻居开始并找到下一个集线器，并继续直到我交付了所有包裹，然后再回到集线器。我需要保存此订单和总里程。

我已经擦除和重写了很多次，我觉得我已经很接近了，但我在缩小范围方面遇到了一些困难，我希望能就我遗漏的内容提供指导。

我不想包含太多代码，所以只是快速概述一下； Locations 是一个包含 16 个位置 ID 的列表，其中一些是重复的。

# This is to set the initial location to the hub, where all trucks 
start. 
current = hubID 
path = []
totalMileage = 0

def findPath(locations):
    tempList = []

    for i in locations:
        # d.dijkstraSearch(fromid, toid) returns an optimized 
        distance in miles 
        dist = d.dijkstraSearch(current, i)
        tempList.append([dist], [i])

    tempList.sort()
    min = tempList[0]
    current = closest location?
    total mileage += distance of closest location?
    locations.remove(location ID of closest location)
    findPath(locations)

findPath(locations)

我的目标是找到距当前位置的最短距离，然后将该距离添加到总里程和距路径最近的位置。但是，现在我不确定如何单独访问 tempList，以便我可以将每个相应的索引添加到正确的 list/total。然后我还需要将当前变量更改为最近的位置，而不是再次递归调用它，以便我一直到达列表的末尾，然后返回到集线器。我认为我在错误地处理二维数组，并且没有适当地循环遍历列表，但我无法确定修复它的方法。任何关于下一步去哪里的建议或意见都将非常感谢！

Answer 1

当您只是在寻找最低限度时，您不需要跟踪所有内容和分类业务。

否则，您确实非常接近可行的东西，例如：

current = hubID 
path = []
totalMileage = 0

def findPath(locations):
  # We need to tell Python that this is defined in the global scope
  global current, totalMileage

  # Make sure you always have a base case when defining a recursive function!
  # We don't want to recurse for ever.
  if len(locations) == 0: 
    return

  # We will keep track of the closest location encountered and its distance
  closest_location = -1
  closest_location_dist = float("inf")

  # We need to update the closest location if we see a closer one
  for i in locations:
    dist = d.dijkstraSearch(current, i)
    if dist < closest_location_dist:
      closest_location = i
      closest_location_dist = dist

  current = closest_location
  path.append(current)
  totalMileage += closest_location_dist
  locations.remove(closest_location)
  findPath(locations)

findPath(locations)

注意不要在位置中包括枢纽（否则枢纽将是离自己最近的邻居）并且这将不包括返回枢纽的旅行。此外，起始节点未在 "path" 中列出（我将其保留原样，我不知道这是否是一个选择）。最后，知道 "locations" 列表在调用该函数后将为空，因此如果您之后还需要它，您将需要 make/pass 一个副本。

即使它有效，让您的函数依赖全局变量来完成工作通常是不好的做法（它可能导致名称冲突并变得非常混乱）。以下可能会好一点：

def findPath(locations, current):
  if len(locations) == 0: 
    return [], 0

  closest_location = -1
  closest_location_dist = float("inf")

  for i in locations:
    dist = d.dijkstraSearch(current, i)
    if dist < closest_location_dist:
      closest_location = i
      closest_location_dist = dist

  current = closest_location
  locations.remove(current)
  path_todo, mileage_todo = findPath(locations, current)

  path = [current] + path_todo
  totalMileage = closest_location_dist + mileage_todo

  return path, totalMileage

path, totalMileage = findPath(locations, hubID)

（警告与之前相同）

最后但同样重要的是，该算法并不总是给出最佳路径。在某些边缘情况下，它甚至可能导致 worst 可能路径。对于您想做的事情，它可能仍然足够。最佳可能路径可能不可能始终在 "reasonable" 时间内计算，因为公制距离的 Travelling Salesman Problem is NP-Hard, but there exists algorithms which guarantee to be somewhat close to the best tour in a well behaved graph, such as the Christofides algorithm。

我需要帮助使用包裹递送列表调整算法以找到最短路径

I need help adjusting an algorithm with a list of package deliveries to find the shortest path

python

algorithm

nearest-neighbor

data-structures