python - 加权遍历算法(广度优先更好？)

Question

我在设计遍历问题的算法时遇到问题。

我有一艘在二维网格上控制的飞船，它从网格的最底部开始。网格的每个图 block 都有一个值(介于 0 和 1000 之间)，等于该图 block 中有多少“资源”。

飞船可以go_left()、go_up()、go_right() 或stay_still()

如果飞船stay_still()，它会收集当前图 block 资源的 25%(四舍五入到最接近的整数)。

如果飞船使用移动命令，它需要花费当前方格资源值的 10%(向下舍入)。成本高于船舶收集的移动是非法的。 (因此，如果一艘船在 100 上，则离开 100 需要花费 10，如果它在 9 或更少，则移动是免费的)。

目标是找到一条合法收集 1000 资源的相对较短的路径。返回对应路径的移动顺序列表。

我很自然地尝试了递归的方法:

在 sudo 代码中，算法是:

alg(position, collected, best_path):
  if ship has 1000:
    return best_path
  alg(stay still)
  if ship has enough to move:
    alg(try left)
    alg(try up)
    alg(try right)

如果你想仔细看看 python3 中的实际语法，它是:

    def get_path_to_1000(self, current_position, collected_resource, path, game_map):
        if collected_resource >= 1000:
            return path

        path_stay = path.copy().append(stay_still())
        self.get_path_to_1000(current_position, collected_resource + 
                 math.ceil(0.25 * game_map[current_position].value),
                 path_stay, game_map.copy().collect(current_position))

        cost = math.floor(0.1 * game_map[current_position].value)
        if collected_resource >= cost:
            direction_list = [Direction.West, Direction.North, Direction.East]
            move_list = [go_left(), go_up(), go_right()]
            for i in range(3):
                 new_path = path.copy().append(move_list[i])
                 self.get_path_to_1000(
                      current_position.offset(direction_list[i]), 
                      collected_resource - cost, new_path, game_map)

我的方法的问题是算法永远不会完成，因为它一直在尝试越来越长的船舶静止列表。

我怎样才能改变我的算法，让它实际上尝试不止一个选项，返回到 1000 的相对较短(或最短)的路径？

Answer 1

此问题的本质(忽略向下舍入的确切机制/移动的可变成本)是找到最短数量的节点以获取 1,000 个资源。看待这个目标的另一种方式是，这艘船在每一次转弯时都试图找到最有效的移动。

这个问题可以通过对 Dijksta 算法稍作修改来解决。我们不会贪婪地选择权重最小的移动，而是选择权重最大(资源数量最多)的移动，并将此值添加到运行计数器，以确保我们达到 1000 资源总数。通过贪婪地添加最有效的边缘权重(低于 1000)，我们将找到最少的移动次数来获得总共 1000 个资源。

简单地保留一个用算法进行的移动列表，并在资源计数器达到 1000 时返回该列表。

这是有关如何最好地实现 Dijkstra 算法的有用资源:

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

经过少量修改，这应该是您最好的选择!