这是可能的吗?到目前为止,我认为我需要通过类似 A* 或 Dijkstra 算法计算列表中每个项目之间的距离。之后,我应该如何处理它,像旅行商问题一样吗?因为在我的问题中,存在指定的起始节点、指定的结束节点和一些约束条件,而这些条件并不在旅行商问题中。
将其视为TSP问题似乎会使它变得更加困难。有人指出,杂货店并不那么复杂。在我熟悉的杂货店(在美国),没有太多合理的路线,特别是如果你有一个给定的起点。我认为一个深思熟虑的启发式算法可能会解决这个问题。
例如:我通常从一端开始——如果是大购物,我会确保最后经过冷冻食品区,但通常并不重要,我会从最靠近入口的地方开始。我通常走到外面,只有在需要某个单独过道的东西时才下去。一旦你进入一个过道,就拿起那个过道里的所有东西。对于一些过道,最好从一端进入,拿起物品,然后返回起点,而对于其他过道,你只需致力于整个过道——这取决于你在该过道中需要的最后一个物品以及你需要去哪里——如何走出过道取决于下一个所需物品——它可能涉及回溯,也可能不涉及回溯——但计算机可以轻松地计算出到达下一个物品的最短路径。
我同意上面其他问题的有用提示,但也许更具体的算法会更加有效,尤其是在资源有限的情况下。TSP告诉我们,你不能证明它是最优的方法,但我认为这并不是必要的...
基本上这是一个旅行商问题,但是根据您的要求,您可以很好地限制搜索空间。如果地点不太多,您可以尝试计算所有可能的选项,但如果不可行,您需要进一步限制搜索空间。
您可以将搜索时间限制在1秒内,以便返回您能找到的最短路径,但这可能不是所有路径中最短的,但仍然相当短。
您还可以应用贪心算法来查找下一个最近的位置,然后使用回溯选择下一个最近的位置等。
可能解决方案的伪代码:
def find_shortest_path(current_path, best_path): if time_limit(): return你可以利用商店布局的信息来限制搜索空间。例如,在德国,一个典型的商店有许多货架,可以被认为是形成车道的货架。在它们之间,有连接货架车道的直角车道。现在,你可以将交叉口定义为节点,将车道定义为图中的边缘。边缘上标记着该车道部分货架中的所有物品。现在,即使对于一个大商店,这个图也会非常小。你现在需要找到包括你所需的所有边缘标签(物品)的最短路径。这应该可以通过使用贪婪/回溯方法Tuomas Pelkonen suggested来实现。
这只是一个想法,我不知道它是否真的有效,但也许你可以从这里开始。
只有广度优先搜索才能确保您不会“错过”一条比当前“最佳”解决方案更好的商店路径,但您无需搜索路径中的每个节点。明显比当前“最佳”解决方案长的节点可以稍后扩展。
这意味着您像“广度优先”搜索一样处理问题,但根据当前行程距离改变节点的扩展。搜索树的某些分支将比其他分支更快地扩展,因为它们在相同的时间内能够访问更多的节点。
那么,如果节点扩展并非真正的广度优先,为什么我还要使用那个词?因为在找到解决方案之后,您仍然必须扩展当前的“考虑节点”集,直到每个搜索路径都超过解决方案。这避免了错过具有耗时初始步骤但完成速度比当前解决方案更快的路径的情况,因为最后一步非常快速。
起始节点的要求是虚构的。使用TSP,您将得到一次旅行,您可以选择想要的起始节点,而不会改变解决方案的成本。
当涉及到计数器时,情况会有些棘手:您需要在具有某些弧缺失(或者说,某些弧具有非常高的成本)的有向图上解决问题。
从完整的有向图开始,您应该修改适当弧的成本,以便:
希望对您有所帮助