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

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. 如果 dist[v] == dist[u] + weight(u, v )。现在我们可以在只包含“好”边(这次所有边的权重都为 1)的图上运行简单的广度优先搜索(同样，从批处理中顶行的所有单元格开始)。

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

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