在某些条件下找到最短路径

Question

让我介绍一下问题:

你有一个像这个这样的二维码（二维码在这个问题中总是一个正方形）。
one http://img11.hostingpics.net/pics/514457code.png
您可以从 QR 码顶部的任何位置开始（因此在第一行的任何位置），并且您必须找到一条路径以到达底部行的任何位置（因此在最后一行的任何位置）。

你必须尽量减少路径中黑色案例的数量，如果你有几条路径具有相同数量的黑色案例，你必须找到最短的一条。

solution 示例：

找到一种算法来找到满足这些条件的最短路径。

我的解决方案

首先，我将问题视为有向网格图，其中每个像素都是一个顶点，每个顶点的边数与邻居的边数一样多。

例如，左上角的顶点可以到达它的右邻居和它的下邻居。

我将边的权重归为如下：

• 对于从白色案例到黑色案例的边缘 -> 权重 1
• 对于从白色案例到白色案例的边缘 -> 权重 0 + 一个小值
• 对于从黑色案例到白色案例的边缘 -> 0 的权重 + 一个小值
• 对于从黑色案例到黑色案例的边缘 -> 权重 1

这里有一个小值（<<1），用于在我们有几条路径具有相同数量的黑色案例的情况下找到最短路径。

因此，对于这种表示，设 V 为顶点数，W 为直线中的顶点数，E 为边数，我们有 E = W(W-1)*2*2。

然后我创建 2 个子集：第一个包含所有可能的起始顶点（QR 码的第一行，所以 W 个顶点），另一个包含可能的最终目的地（最后一行，所以 W 个顶点）。

我使用 Dijkstra 计算 O(V lg(V)) 中的最短路径（使用我使用的库），我为所有起始节点计算了 W 次，然后寻找到每个目的地的最短路径顶点。

所以我在 O(V*W lg(V)) = O(V^3/2 Lg(V)) 中找到最短路径。

问题

你有更好的解决这个问题的方法吗？用网格图表示或其他什么？

Answer 1

这是一个更快的解决方案：

1. 让我们找出包含最少黑色单元格的路径。我们可以使用 0-1 广度优先搜索。通向白色单元格的边的权重应为 0，通向黑色单元格的边的权重应为 1。没有必要分别从顶行的每个顶点 运行 它：我们可以在开始时将它们全部添加到队列中，然后 运行 一次广度优先搜索（我们应该不要忘记在黑色单元格之前添加第一行的所有白色单元格）。

2. 让我们称从 u 到 v 的有向边是好的，如果 dist[v] == dist[u] + weight(u, v)。现在我们可以 运行 在仅包含 "good" 条边（这次所有边的权重都为 1).

3. 现在我们可以从最后一行中选择最好的单元格。

这个解决方案需要 O(V) 时间（它只是两个广度优先搜索）并且它总是产生一个最佳答案（不需要小的幻数）。