首页 文章

找到一些条件最短的路径

提问于
浏览 次
2

让我来介绍一下这个问题：

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

您必须最小化路径中的黑色案例数，如果您有多个路径具有相同数量的黑色案例，则必须找到最短的案例 .

solution的示例：

找到一个算法来找到这些条件的最短路径 .

My 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））的最短路径 .

Question

你有更好的解决方案吗？使用网格图表示或其他什么？

algorithm graph graph-algorithm

1 回答

  • 1

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

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

    • 如果 dist[v] == dist[u] + weight(u, v) ，让我们调用从 u 到 v 的有向边 . 现在，我们可以在仅包含"good"边的图上运行简单的广度优先搜索（再次，从批处理中的顶行的所有单元格）（此时所有边都具有权重 1 ） .

    • 现在我们可以从最后一行中选择最佳单元格 .

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

    回复于

相关问题