计算通过杂货店的最短路径

Question

我正试图找到一种方法来找到通过杂货店的最短路径,访问一个位置列表(购物清单).路径应该从指定的起始位置开始,并且可以在多个结束位置结束(有多个结账计数器).此外,我在路径上有一些预定义的约束,例如"购物清单上的项目x需要是路径上的最后一个,倒数第二个或第三个最后一个项目".有一个函数将返回给定路径的true或false.最后,这需要使用有限的CPU功率(在智能手机上)和大约一秒左右来计算.如果这是不可能的,那么最佳路径的近似值也是可以的.

这可能吗？到目前为止,我认为我需要首先使用像A*或Dijkstra这样的东西来计算列表中每个项目之间的距离.在那之后,我应该像旅行推销员那样对待它吗？因为在我的问题中有一个指定的起始节点,指定的终端节点和一些约束,这些约束不在旅行商问题中.

Answer 1

好吧，基本上这是一个旅行推销员问题，但是根据您的要求，您很好地限制了搜索空间。如果位置不是太多，您可以尝试计算所有可能的选项，但如果这不可行，则需要进一步限制搜索空间。

您可以限制搜索时间，以便返回 1 秒内可以找到的最短路径，但这可能不是所有路径中最短的，但无论如何也很短。

您还可以应用贪心算法来查找下一个最近的位置，然后使用回溯选择下一个最近的位置等。

可能的解决方案的伪代码：

def find_shortest_path(当前路径, 最佳路径):
  如果时间限制（）
    返回

  如果 len(当前路径) == NUM​​_LOCATIONS:
      # 到达目的地
      如果 calc_len(当前路径) < calc_len(最佳路径):
          最佳路径 = 当前路径
      返回

  # 你需要对可能的位置进行很好的排序，以最大限度地提高找到位置的机会
  # 最短解
  排序（可能的位置）

  对于 possible_locations 中的位置：
      find_shortest_path（当前路径+位置，最佳路径）