修改后的最短路径算法 - 顶点具有点

Question

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

我现在在考虑可能要通过动态规划来解决问题，但我不确定如何设置问题。

如果您能告诉我如何设置它/使用正确的算法，我将非常感激！

- dtong

---

你能使用递归函数来构建通过这些顶点的路径列表，然后进行比较吗？或者由于你有太多的点而不可行？ - bcdan

此外，这是什么编程语言，还是一个一般性的问题？ 这是英语，需要翻译成中文。 - bcdan

@bcdan 这是Java语言。我们大约有600个点需要考虑。 - dtong

Answer 1

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

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)

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

距离是通过基本上制作每个坐标到其他所有坐标的距离矩阵来生成的。

此方法使用贪婪式推销员算法。

- bcdan

---

没有特定的点与每个点连接。该点可以连接图上的任意600个点。我只想最大化得分和最小化距离。除了暴力破解，我真的想不出算法了。按您的方式进行递归将意味着我必须检查每个可能的点，这将使运行时间为O(n*n!)。 - dtong

@DanGoldstein591 好的，我明白了。我会在那方面添加一些内容。 - bcdan

Answer 2

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

- dtong

Answer 3

我认为一个好的方法是在图上构建最小生成树。之后，您可以选择一个根节点（选择是算法/启发式算法本身），并遍历树。然而，这可能不会是最优解，因为我认为问题是 NP 完全的。 或者，您可以尝试搜索 TSP（旅行推销员问题）的解决方案算法，并提取给出最多点数的路径。

- Pedro Isaaco