algorithm - 算法：距离变换 - 任何更快的算法？

Question

我正在尝试解决距离变换问题（使用曼哈顿的距离）。基本上，给矩阵 0 和 1，程序必须将每个位置的距离分配到最近的 1。例如，对于这个

距离变换矩阵是

我头脑中可能的解决方案是：

最慢的（最慢的，因为我试图实现它们——它们在非常大的矩阵上落后）：

蛮力 - 对于程序读取的每 1，从开始到结束相应地更改距离。
从 0 开始的广度优先搜索 - 对于每个 0，程序从内到外查找最近的 1。
与 2 相同，但从 1 的标记开始，每个距离由内向外。

更快（从其他人的代码中读取）

从 1 开始的广度优先搜索

1. Assign all values in the distance matrix to -1 or very big value.
2. While reading matrix, put all positions of 1's into queue.
3. While queue is not empty
    a. Dequeue position - let it be x
    b. For each position around x (that has distance 1 from it)
        if position is valid (does not exceed matrix dimensions) then
            if distance is not initialized or is greater than (distance of x) + 1 then
                I. distance = (distance of x) + 1
                II. enqueue position into queue

我想问是否有更快的解决方案来解决这个问题。我试图搜索距离变换的算法，但它们中的大多数都在处理欧几里德距离。

提前致谢。

score 5 · Accepted Answer

广度优先搜索将执行矩阵的宽度和高度的Θ(n*m)操作。nm

您需要输出Θ(n*m)数字，因此从理论的角度来看，您无法获得比这更快的速度。

我假设您对讨论缓存和此类优化不感兴趣。

请注意，此解决方案适用于更有趣的情况。例如，想象同样的问题，但可能有不同的“来源”：

使用 BFS，您将以相同的时间复杂度获得以下到最近源的距离：

但是，对于单一来源，还有另一种解决方案在实践中可能具有稍微更好的性能（即使复杂性仍然相同）。

在此之前，让我们观察以下属性。

属性：如果源位于 (a, b)，则点 (x, y) 具有以下曼哈顿距离：

d(x, y) = abs(x - a) + abs(y - b)

这应该很容易证明。所以另一种算法是：

for r in rows
  for c in cols
    d(r, c) = abc(r - a) + abs(c - b)

这是非常简短和容易的。

除非您编写和测试它，否则没有简单的方法来比较这两种算法。假设一个有效的有界队列实现（使用数组），每个单元格有以下主要操作：

BFS：队列插入/删除，每个节点访问5次（邻居4次，出队1次）
直接公式：两次减法和两次ifs

这实际上取决于编译器及其优化以及特定的 CPU 和内存架构来说明哪个性能更好。

也就是说，我建议你选择对你来说更简单的那个。但是请注意，对于多个源，在第二种解决方案中，您需要对阵列进行多次传递（或一次传递多次距离计算），对于足够多的源，这肯定会比 BFS 具有更差的性能。

score 2 · Accepted Answer

您根本不需要队列或类似的东西。请注意，如果 (i,j) 与 (k,l) 的距离为 d，实现该距离的一种方法是向左或向右 |ik| 次，然后向上或向下 |jl| 次。

1所以，用大数字初始化你的矩阵，并在你输入的任何地方都贴上一个零。现在做这样的事情：

for (i = 0; i < sx-1; i++) {
  for (j = 0; j < sy-1; j++) {
    dist[i+1][j] = min(dist[i+1][j], dist[i][j]+1);
    dist[i][j+1] = min(dist[i][j+1], dist[i][j]+1);
  }
  dist[i][sy-1] = min(dist[i][sy-1], dist[i][sy-2]+1);
}
for (j = 0; j < sy-1; j++) {
  dist[sx-1][j] = min(dist[sx-1][j], dist[sx-2][j]+1);
}

至此，您已经找到了所有仅涉及向下或向右的最短路径。如果您对向上和向左做类似的事情，dist[i][j]将为您提供从 (i, j) 到1输入矩阵中最近的距离。

algorithm - 算法：距离变换 - 任何更快的算法？

2 回答 2

Related

Reference