首页 文章

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

提问于
浏览 次
14

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

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

algorithm graph graph-theory

5 回答

  • 0

    起始节点的要求是虚构的 . 使用TSP，您最终可以选择所需的起始节点，而无需更改解决方案成本 .

    当谈到计数器时，它有点棘手：您需要的是在有向图上解决问题，其中缺少一些弧（或者，这是相同的，其中一些弧具有非常高的成本） .

    从完整的有向图开始，您应该修改正确弧的成本，以便：

    • 拒绝从项目到开始节点

    • 拒绝从柜台到物品

    • 拒绝从起始节点到计数器

    • 允许以零成本从计数器到起始节点（这只需要关闭路径）
      在把事情搞砸之后

    • 告诉我，如果我错过了什么:)

    HTH

    回复于
  • 0

    似乎将其视为TSP问题使其变得更加困难 . 有人指出，杂货店的故事并不复杂 . 在我熟悉的杂货店（在美国），没有那么多合理的路线 . 特别是如果你有一个给定的起点 . 我认为一个经过深思熟虑的启发式技术可能会成功 .

    例如：我通常从一端开始 - 如果这是一次大旅行，我确保我最后通过冷冻食品，但这通常没关系，我会从我进入商店的地方开始 . 我一般在外面走动，如果我需要那个东西，只能沿着个人通道走下去 . 一旦你走进过道，就拿起那个过道里的一切 . 有了一些过道，最好放到一端， grab 物品，然后回到起点，而其他人只需要承担整个过道 - 这是你需要的最后一个项目的功能，你需要的地方下一步 - 如何走出过道取决于所需的下一个项目 - 它可能会或可能不会涉及回溯 - 但计算机可以轻松计算到下一个项目的最短路径 .

    所以我同意上面其他问题的有用提示，但也许一般不太通用的算法会起作用 . 有限的资源可能会更好地工作 . 然而，TSP告诉我们，你无法证明这是最佳方法，但我怀疑这不是必要的......

    回复于
  • 1

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

    您可以限制搜索时间，以便返回1秒内可以找到的最短路径，但这可能不是最短路径，但无论如何都要短 .

    您也可以应用Greedy algorithm查找下一个最近的位置，然后使用Backtracking选择下一个最近的位置等 .

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

    def find_shortest_path(current_path, best_path):
  if time_limit()
    return

  if len(current_path) == NUM_LOCATIONS:
      # destionation reached
      if calc_len(current_path) < calc_len(best_path):
          best_path = current_path
      return

  # You need to sort the possible locations well to maximize your chances of finding the
  # the shortest solution
  sort(possible_locations)

  for location in possible_locations:
      find_shortest_path(current_path + location, best_path)
    回复于
  • 0

    那么，您可以使用有关商店布局的信息来限制搜索空间 . 例如，一个典型的商店（至少在德国这里）有许多货架，可以被认为是形成车道 . 在它们之间有正交的车道连接货架车道 . 现在，您将交叉定义为节点，将通道定义为图形中的边 . 边缘标有车道部分货架上的所有物品 . 现在，即使是大商店，这个图表也会非常小 . 您现在必须找到包含所需边缘标签（项目）的最短路径 . 这应该可以通过使用贪婪/回溯方法Tuomas Pelkonen suggested来实现 .

    这只是一个想法，我不知道它是否真的有效，但也许你可以从这里开始 .

    回复于
  • 0

    只有广泛的第一次搜索才能确保您不会“错过”通过商店的路径，这比您当前的“最佳”解决方案更好，但您无需搜索路径中的每个节点 . “明显”长于当前“最佳”解决方案的节点可以稍后扩展 .

    这意味着您可以像“先呼吸”一样解决问题，但会根据当前行进的距离改变节点的扩展 . 搜索树的某些分支将比其他分支更快地扩展，因为管理在相同的时间内访问更多节点 .

    所以如果节点扩张不是真正的呼吸优先，为什么我一直在使用这个词？因为在找到解决方案之后，您仍必须扩展当前的“已考虑节点”集，直到每个搜索路径超出解决方案 . 这样可以避免错过一条路径，这条路径有很多耗时的初始支路，但是比当前的解决方案更快完成，因为最后一步是快速点亮 .

    回复于

相关问题