查找具有曼哈顿距离的最近元素效率不高

Question

我有一个带有障碍物的迷宫，在地图上有不同的"power-ups"。它们只是最终需要到达的目标目的地。但是，到达它们的顺序很重要，因为我们想要节省时间。

让我们模拟以下情况：

   0  1  2  3
0 [ ][X][ ][ ]
1 [ ][▣][▣][ ]
2 [ ][P][ ][ ]
3 [ ][▣][Y][▣]
4 [ ][▣][ ][ ]

[▣] is an obstacle.
[X] with position (0,1) is a power-up
[Y] with position (3,2) is a power-up
[P] with position (2,1) is the player. In other words, the starting position

[P] 需要达到加电。

为了决定哪一个，目前，我正在使用曼哈顿距离来查找最近的项目：

abs(a1[0] - a2[0]) + abs(a1[1] - a2[1])

曼哈顿距离会计算[P]和[X]之间的距离为2，[P]和[Y]之间的距离也是2。所以它会随机选择一个下次访问。

但是，曼哈顿距离不会考虑[P]和[X]之间有障碍物，因此实际距离会更长。

因此，需要四步才能达到 [X]:

(2,1) first step-> (2,0) second step-> (1,0) third-> (0,0) fourth-> (0,1)

达到 [Y] 时，只需走 2 步：

(2,1) first step-> (2,2) second step-> (3,2)

由于曼哈顿距离在某些情况下会为我完成这项工作，所以这不是最省时的方法。此外，时间对我来说很关键，因为我想在尽可能短的时间内获得所有能量提升以赢得比赛。

有人可以建议我如何优化这个，或者我应该使用什么其他方法来计算最近的项目，同时考虑到我遇到的障碍？

Answer 1

为了知道哪个能量提升实际上是最接近的，您需要计算每个能量提升的实际距离（考虑到障碍物）。在获得这些距离后，您可以比较它们并查看哪一个实际上是最近的。但是，这似乎不是您问题的最佳解决方案，因为您必须进行所有计算才能采取行动。

你现在做的很好，但是我们有办法改进它。您可以使用此方法确定曼哈顿距离及其上的障碍物数量：

def manhattan_d_obstacles(grid, x1, y1, x2, y2):
    obs_count = 0
    if x1 > x2:
        x_range = range(x2, x1)
    else:
        x_range = range(x1, x2)
    if y1 > y2:
        y_range = range(y1, y2)
    else:
        y_range = range(y2, y1)
    for i in x_range:
        for j in y_range:
            if grid[i, j] == 'obstacle':
                obs_counter += 1
    return {
        "dist": abs(x1 - x2) + abs(y1 - y2),
        "obs": obs_counter
    }

现在您可以简单地使用此方法比较曼哈顿距离和该路径上的障碍物数量。所以：

best = {
    "dist": float("inf"), # int("inf") does not exist
    "obs": float("inf") # int("inf") does not exist
}
for pwu in power_ups:
    path = manhattan_d_obstacles(P['x'], P['y'], pwu['x'], pwu['y'])
    if path['dist'] < best['dist']:
        best = path
    elif path['dist'] == best['dist'] and path['obs'] < best['obs']:
        best = path

如果实际路线不同于曼哈顿路线（即您示例中的 P -> Y 是什么），此函数通常比计算实际距离运行得更快。否则，它运行相同的速度。

查找具有曼哈顿距离的最近元素效率不高

Finding closest element with Manhattan distance not efficient

python

distance

coordinates