algorithm - 使用回溯算法找到获得至少 x 奖励积分的最快周期

Question

有一张带点的地图：

每个点旁边的绿色数字是该点的 ID，红色数字是该点的奖励。我必须找到在 #1 点开始和结束的最快周期，并且至少获得 x（在这种情况下为 15）加分。我可以多次使用城市；但是，我只会获得一次奖励积分。我必须使用回溯算法来做到这一点，但我真的不知道从哪里开始。我已经对此进行了研究，但我看不出这与回溯之间的联系。

输出将如下所示：

(1,3,5,2,1) (11.813 length)

Answer 1

Backtracking是一种用于减少问题搜索空间的技术。所以，你有一个问题，你有一个有最优和非最优解的空间，你必须选择一个最优解。

在您的问题中，一个简单的策略是生成所有可能的解决方案。但是，此解决方案将遍历整个解决方案空间，并且有时会意识到不会找到最佳解决方案。

这是 的主要作用backtracking：您遍历解决方案的空间，并且当您到达一个给定点时，如果您知道如果在同一路径上继续搜索将不会获得最佳答案，您可以简单地悔改所采取的步骤，返回遍历，然后选择您发现无助的步骤之后的步骤。

在您的问题中，由于可以多次访问节点，因此想法是为每个顶点维护一个顶点列表，该列表按与列表的顶点所有者的距离递减排序。

然后，您可以简单地从其中一个顶点开始，逐个顶点地在图上进行遍历，始终检查目标是否仍然可以实现，并在发现无法解决某个问题时回溯解决方案观点。

Answer 2

您可以使用递归回溯算法列出所有可能的循环并保留最佳答案：

visitCycles(list<Int> cycleSoFar)
{
  if cycle formed by closing (cycleSoFar) > best answer so far
  {
    best answer so far = cycle formed by closing (cycleSoFar)
  }
  if (cannot improve (cycleSoFar))
  {
    return
  }
  for each point that makes sense
  {
    add point to cycleSoFar
    visitCycles(cycleSoFar)
    remove point from cycleSoFar
  }
}

添加更多细节：

1) 一个循环是不好的，除非它至少有 15 个奖励点。如果它有任何好处，那么它比迄今为止最好的答案更好，如果它更短的话。

2）当您向循环添加更多点时，您只会使其更长，而不是更短。因此，如果您找到了可能的答案并且 cycleSoFar 已经至少与该可能的答案一样长，那么您无法改进它，您还不如返回。

3）由于重复使用循环中的积分不会获得任何奖励积分，因此尝试两次添加积分是没有意义的。

4）您可以通过以合理的顺序迭代“每个有意义的点”来加速程序，例如首先选择离当前点最近的点。您可以通过为每个点预先计算按距离升序排列的所有其他点的列表来节省时间（或者您可能不会 - 您可能必须通过实验尝试不同的方案）。