修正的最短路径算法——顶点有点

Question

现在我有一个无向图。每条边代表顶点之间的距离。每个顶点都包含一个数字（我们称它们为点）。我试图在使用最小距离的同时获得最大数量的点。我对我可以走的最大距离有限制，因此我不需要到达每个顶点。我可以从任何一个顶点开始，也可以在任何一个顶点结束（我不需要回到原点）。

现在我认为可以通过动态规划实现，但我不完全确定如何设置问题。

任何有关如何设置它的帮助up/the将不胜感激！

Answer 1

我认为一个好的方法是在图上构建最小生成树。之后你可以选择一个根节点（我猜选择是它自己的 algorithm/heuristic）并遍历树。然而，这可能不是最佳解决方案，因为我认为问题是 NP 完全的。或者，您可以尝试搜索 TSP（旅行商问题）的解决算法，并提取给出最多分数的路径。

Answer 2

使用 recursive function，您可以遍历点，并对第一个点连接到的每个点执行相同的函数，依此类推。

pts = [[(1,8), (2,5), (3,6)...]...] //each sublist of points needs to be sorted by the second index in each value contained
paths = []
def Branch(history, distance):
  for index, dist in pts[history[-1]][1:tree_branches_per_iteration]: //make the shorter distances go first
    if not index in history: //check for repetition
      new_distance = distance + dist
      if new_distance > limit: //check for distance limit
        paths.append((history + [index], new_distance))
      else:
        Branch(history + [index], new_distance)
    else:
      paths.append((history, distance))

Branch([0], 0)

此函数调用自身，在所有可能的方向上组装点链（并且不会两次到达同一点）并在两次到达相同点或达到距离限制时终止。

这些距离基本上是由每个坐标到彼此的所有距离组成的矩阵生成的。

这种方法使用了贪婪的销售人员。

Answer 3

所以在这次经历之后，我发现你应该研究一下蚁群算法并将其应用于旅行商问题。您也可以使用修改后的贪婪算法方法，该方法从随机点开始，然后根据给您最佳点的位置选择基于随机双面骰子的下一个位置。然后您可以进一步修改您的算法以存储以前的结果并迭代以获得更好的结果。

修正的最短路径算法——顶点有点

Modified shortest path algorithm - vertices have points

algorithm

graph

graph-algorithm