求图中所有所需点的最短路径

Question

我在一次面试中被问到以下问题

你会得到一个4×4的网格。电网上的一些地方蕴藏着宝藏。您的任务是访问所有的地点，其中包含宝藏和收集它。您可以在四个相邻的单元格上移动(上、下、左、右)。每一个移动和行动的“宝藏收集”是一个单一的单位成本。您需要遍历整个网格，并收集网格上的所有宝藏，将成本降到最低。

如果我能正确地回忆起，这里有一个给出的样本图：

U..X
..X.
X..X
..X.

在哪里，U是我目前的位置，X标志着宝藏的位置。

我提出的解决方案是使用广度优先搜索，遍历图表，同时“收集宝藏”。然而，面试官坚持认为，有一个更好的方法，以尽量减少成本。我希望你能帮我解决这个问题。

Answer 1

你应该意识到这是一个小伪装的旅行推销员问题。使用宽度优先，您可以确定不同顶点之间的最短路径，这将给出一个包含这些方法的派生图，作为顶点之间的加权边。从那时起，这就是经典的TSP。

Answer 2

单靠BFS并不能为您解决这个问题，因为您不能同时向各个方向移动。这不是一个单一来源的最短路径问题，因为一旦你收集了宝藏，你就从你现在的地点开始你的下一个路径，而不是从原来的地点开始。

收集所有宝藏所需的时间取决于您使用X访问这些箱子的顺序。因为只有五个订单，所以您可以尝试所有120个订单，计算成本，并选择最佳的订单。

注意，如果顺序是固定的，那么解决方案是微不足道的:您可以按顺序在单元格之间添加曼哈顿距离，并选择最小的结果。