启发式最少圈数

发布于 2024-08-18 12:01:02 字数 468 浏览 3 评论 0原文

无论如何，是否有办法确保除广度优先搜索之外的任何方法都满足最少的轮数启发式？也许更多的解释会有帮助。

我有一个随机图，很像这样：

0 1 1 1 2
3 4 5 6 7
9 a 5 b c
9 d e f f
9 9 g h i

从左上角开始，我需要知道到达右下角所需的最少步数。每组连接的颜色都被假定为单个节点，因此例如在这个随机图中，顶行上的三个 1 都被视为单个节点，并且每个相邻（非对角线）连接的节点都是可能的下一个状态。因此，从一开始，可能的下一个状态是顶行中的 1 或第二行中的 3。

目前我使用双向搜索，但树大小的爆炸性增长很快。在我的一生中，我一直无法调整问题，以便我可以安全地为节点分配权重，并让它们确保最少数量的状态更改以达到目标，而不会变成广度优先搜索。将此视为城市地图，启发式将是达到目标的最少转弯数。

非常重要的是，最少的圈数是此搜索的结果，因为该值是更复杂问题的启发式的一部分。

原文

Is there anyway to ensure the that the fewest number of turns heuristic is met by anything except a breadth first search? Perhaps some more explanation would help.

I have a random graph, much like this:

0 1 1 1 2
3 4 5 6 7
9 a 5 b c
9 d e f f
9 9 g h i

Starting in the top left corner, I need to know the fewest number of steps it would take to get to the bottom right corner. Each set of connected colors is assumed to be a single node, so for instance in this random graph, the three 1's on the top row are all considered a single node, and every adjacent (not diagonal) connected node is a possible next state. So from the start, possible next states are the 1's in the top row or 3 in the second row.

Currently I use a bidirectional search, but the explosiveness of the tree size ramps up pretty quickly. For the life of me, I haven't been able to adjust the problem so that I can safely assign weights to the nodes and have them ensure the fewest number of state changes to reach the goal without it turning into a breadth first search. Thinking of this as a city map, the heuristic would be the fewest number of turns to reach the goal.

It is very important that the fewest number of turns is the result of this search as that value is part of the heuristic for a more complex problem.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夏夜暖风 2024-08-25 12:01:02

你自己说每组数字代表一个节点，每个节点都连接到相邻的节点。那么这是一个简单的最短路径问题，您可以使用（例如）Dijkstra 算法，每条边的权重为 1（1 圈）。

回复收藏 0 原文

落日海湾 2024-08-25 12:01:02

这听起来像 Dijkstra 算法。最难的部分在于正确设置图表（跟踪哪个节点获得哪个子节点），但如果您可以为此投入一些 CPU 周期，那么之后就可以了。

为什么不想要广度优先搜索？

在这里..我很无聊:-) 这是用 Ruby 编写的，但可能会让你开始。请注意，它未经测试。

class Node
  attr_accessor :parents, :children, :value
  def initialize args={}
    @parents = args[:parents] || []
    @children = args[:children] || []
    @value = args[:value]
  end

  def add_parents *args
    args.flatten.each do |node|
      @parents << node
      node.add_children self unless node.children.include? self
    end
  end

  def add_children *args
    args.flatten.each do |node|
      @children << node
      node.add_parents self unless node.parents.include? self
    end
  end
end

class Graph
  attr_accessor :graph, :root
  def initialize args={}
    @graph = args[:graph]
    @root = Node.new
    prepare_graph
    @root = @graph[0][0]
  end

  private

  def prepare_graph
# We will iterate through the graph, and only check the values above and to the
# left of the current cell.

    @graph.each_with_index do |row, i|
      row.each_with_index do |cell, j|
        cell = Node.new :value => cell #in-place modification!
        # Check above
        unless i.zero?
          above = @graph[i-1][j]
          if above.value == cell.value
            # Here it is safe to do this: the new node has no children, no parents.
            cell = above
          else
            cell.add_parents above
            above.add_children cell # Redundant given the code for both of those
            # methods, but implementations may differ.
          end
        end
        # Check to the left!
        unless j.zero?
          left = @graph[i][j-1]
          if left.value == cell.value
            # Well, potentially it's the same as the one above the current cell,
            # so we can't just set one equal to the other: have to merge them.
            left.add_parents cell.parents
            left.add_children cell.children
            cell = left
          else
            cell.add_parents left
            left.add_children cell
          end
        end
      end
    end
  end
end
     #j = 0, 1, 2, 3, 4
graph = [
         [3, 4, 4, 4, 2], # i = 0
         [8, 3, 1, 0, 8], # i = 1
         [9, 0, 1, 2, 4], # i = 2
         [9, 8, 0, 3, 3], # i = 3
         [9, 9, 7, 2, 5]] # i = 4

maze = Graph.new :graph => graph

# Now, going from maze.root on, we have a weighted graph, should it matter.
# If it doesn't matter, you can just count the number of steps.
# Dijkstra's algorithm is really simple to find in the wild.

This sounds like Dijkstra's algorithm. The hardest part would lay in properly setting up the graph (keeping track of which node gets which children), but if you can devote some CPU cycles to that, you'd be fine afterwards.

Why don't you want a breadth-first search?

Here.. I was bored :-) This is in Ruby but may get you started. Mind you, it is not tested.

class Node
  attr_accessor :parents, :children, :value
  def initialize args={}
    @parents = args[:parents] || []
    @children = args[:children] || []
    @value = args[:value]
  end

  def add_parents *args
    args.flatten.each do |node|
      @parents << node
      node.add_children self unless node.children.include? self
    end
  end

  def add_children *args
    args.flatten.each do |node|
      @children << node
      node.add_parents self unless node.parents.include? self
    end
  end
end

class Graph
  attr_accessor :graph, :root
  def initialize args={}
    @graph = args[:graph]
    @root = Node.new
    prepare_graph
    @root = @graph[0][0]
  end

  private

  def prepare_graph
# We will iterate through the graph, and only check the values above and to the
# left of the current cell.

    @graph.each_with_index do |row, i|
      row.each_with_index do |cell, j|
        cell = Node.new :value => cell #in-place modification!
        # Check above
        unless i.zero?
          above = @graph[i-1][j]
          if above.value == cell.value
            # Here it is safe to do this: the new node has no children, no parents.
            cell = above
          else
            cell.add_parents above
            above.add_children cell # Redundant given the code for both of those
            # methods, but implementations may differ.
          end
        end
        # Check to the left!
        unless j.zero?
          left = @graph[i][j-1]
          if left.value == cell.value
            # Well, potentially it's the same as the one above the current cell,
            # so we can't just set one equal to the other: have to merge them.
            left.add_parents cell.parents
            left.add_children cell.children
            cell = left
          else
            cell.add_parents left
            left.add_children cell
          end
        end
      end
    end
  end
end
     #j = 0, 1, 2, 3, 4
graph = [
         [3, 4, 4, 4, 2], # i = 0
         [8, 3, 1, 0, 8], # i = 1
         [9, 0, 1, 2, 4], # i = 2
         [9, 8, 0, 3, 3], # i = 3
         [9, 9, 7, 2, 5]] # i = 4

maze = Graph.new :graph => graph

# Now, going from maze.root on, we have a weighted graph, should it matter.
# If it doesn't matter, you can just count the number of steps.
# Dijkstra's algorithm is really simple to find in the wild.

回复收藏 0 原文

你另情深 2024-08-25 12:01:02

这看起来与此 projeceuler http://projecteuler.net/index.html 存在相同的问题。 php?section=problems&id=81

解决方案的复杂度为 O(n) n->节点数

你需要的是记忆。

每一步您最多可以从 2 个方向获得。因此，请选择更便宜的解决方案。

它就像（只需添加如果在边界上则取 0 的代码）

for i in row:
    for j in column:
         matrix[i][j]=min([matrix[i-1][j],matrix[i][j-1]])+matrix[i][j]

现在如果您向左或向下移动，您将获得最便宜的解决方案

解决方案在矩阵 [MAX_i][MAX_j] 中

如果您也可以向左和向上移动，那么BigO要高得多（我可以找出最佳解决方案）

This looks like same problem as this projeceuler http://projecteuler.net/index.php?section=problems&id=81

Comlexity of solution is O(n) n-> number of nodes

What you need is memoization.

At each step you can get from max 2 directions. So pick the solution that is cheaper.

It is something like (just add the code that takes 0 if on boarder)

for i in row:
    for j in column:
         matrix[i][j]=min([matrix[i-1][j],matrix[i][j-1]])+matrix[i][j]

And now you have lest expensive solution if you move just left or down

Solution is in matrix[MAX_i][MAX_j]

If you can go left and up too, than the BigO is much higher (I can figure out optimal solution)

回复收藏 0 原文

殊姿 2024-08-25 12:01:02

为了使 A* 始终找到最短路径，您的启发式需要始终低估实际成本（启发式是“可接受的”）。简单的启发式方法（例如在网格上使用欧几里得距离或曼哈顿距离）效果很好，因为它们计算速度快，并且保证小于或等于实际成本。

不幸的是，就您的情况而言，除非您可以对节点的大小/形状做出一些简化的假设，否则我不确定您可以做很多事情。例如，考虑在这种情况下从 A 到 B：

B 1 2 3 A
C 4 5 6 D
C 7 8 9 C
C e f g C
C C C C C

最短路径是 A -> B。 D-> C-> B，但使用空间信息可能会给 3 带来比 D 更低的启发式成本。

根据您的情况，您可能能够接受实际上不是最短路径的解决方案，只要您能更快地得到答案。 Christer Ericson（PS3 上《战神 3》的程序员）发表了一篇不错的博文，主题为：http ://realtimecollisiondetection.net/blog/?p=56

这是我关于不可接受的启发式的想法：从该点开始，水平移动，直到与目标持平，然后垂直移动，直到达到目标，然后计数您所做的状态更改的数量。您也可以计算其他测试路径（例如垂直然后水平），并选择最小值作为最终启发式。如果您的节点大小大致相等并且形状规则（与我的示例不同），那么这可能会效果很好。您执行的测试路径越多，获得的结果就越准确，但速度也会越慢。

希望这对您有帮助，如果有任何不明白的地方请告诉我。

In order for A* to always find the shortest path, your heuristic needs to always under-estimate the actual cost (the heuristic is "admissable"). Simple heuristics like using the Euclidean or Manhattan distance on a grid work well because they're fast to compute and are guaranteed to be less than or equal to the actual cost.

Unfortunately, in your case, unless you can make some simplifying assumptions about the size/shape of the nodes, I'm not sure there's much you can do. For example, consider going from A to B in this case:

B 1 2 3 A
C 4 5 6 D
C 7 8 9 C
C e f g C
C C C C C

The shortest path would be A -> D -> C -> B, but using spatial information would probably give 3 a lower heuristic cost than D.

Depending on your circumstances, you might be able to live with a solution that isn't actually the shortest path, as long as you can get the answer sooner. There's a nice blogpost here by Christer Ericson (progammer for God of War 3 on PS3) on the topic: http://realtimecollisiondetection.net/blog/?p=56

Here's my idea for an nonadmissable heuristic: from the point, move horizontally until you're even with the goal, then move vertically until you reach it, and count the number of state changes that you made. You can compute other test paths (e.g. vertically then horizontally) too, and pick the minimum value as your final heuristic. If your nodes are roughly equal size and regularly shaped (unlike my example), this might do pretty well. The more test paths you do, the more accurate you'd get, but the slower it would be.

Hope that's helpful, let me know if any of it doesn't make sense.

回复收藏 0 原文

沉溺在你眼里的海 2024-08-25 12:01:02

这种未经调整的广度优先搜索 C 实现可以在不到 1 毫秒的时间内遍历 100×100 网格。你也许可以做得更好。

int shortest_path(int *grid, int w, int h) {
    int mark[w * h];  // for each square in the grid:
                      // 0 if not visited
                      // 1 if not visited and slated to be visited "now"
                      // 2 if already visited
    int todo1[4 * w * h];  // buffers for two queues, a "now" queue
    int todo2[4 * w * h];  // and a "later" queue
    int *readp;            // read position in the "now" queue
    int *writep[2] = {todo1 + 1, 0};
    int x, y, same;

    todo1[0] = 0;
    memset(mark, 0, sizeof(mark));

    for (int d = 0; ; d++) {
        readp = (d & 1) ? todo2 : todo1;      // start of "now" queue
        writep[1] = writep[0];                // end of "now" queue
        writep[0] = (d & 1) ? todo1 : todo2;  // "later" queue (empty)

        // Now consume the "now" queue, filling both the "now" queue
        // and the "later" queue as we go. Points in the "now" queue
        // have distance d from the starting square. Points in the
        // "later" queue have distance d+1.
        while (readp < writep[1]) {
            int p = *readp++;
            if (mark[p] < 2) {
                mark[p] = 2;
                x = p % w;
                y = p / w;
                if (x > 0 && !mark[p-1]) {                // go left
                    mark[p-1] = same = (grid[p-1] == grid[p]);
                    *writep[same]++ = p-1;
                }
                if (x + 1 < w && !mark[p+1]) {            // go right
                    mark[p+1] = same = (grid[p+1] == grid[p]);
                    if (y == h - 1 && x == w - 2)
                        return d + !same;
                    *writep[same]++ = p+1;
                }
                if (y > 0 && !mark[p-w]) {                // go up
                    mark[p-w] = same = (grid[p-w] == grid[p]);
                    *writep[same]++ = p-w;
                }
                if (y + 1 < h && !mark[p+w]) {            // go down
                    mark[p+w] = same = (grid[p+w] == grid[p]);
                    if (y == h - 2 && x == w - 1)
                        return d + !same;
                    *writep[same]++ = p+w;
                }
            }
        }
    }
}

This untuned C implementation of breadth-first search can chew through a 100-by-100 grid in less than 1 msec. You can probably do better.

int shortest_path(int *grid, int w, int h) {
    int mark[w * h];  // for each square in the grid:
                      // 0 if not visited
                      // 1 if not visited and slated to be visited "now"
                      // 2 if already visited
    int todo1[4 * w * h];  // buffers for two queues, a "now" queue
    int todo2[4 * w * h];  // and a "later" queue
    int *readp;            // read position in the "now" queue
    int *writep[2] = {todo1 + 1, 0};
    int x, y, same;

    todo1[0] = 0;
    memset(mark, 0, sizeof(mark));

    for (int d = 0; ; d++) {
        readp = (d & 1) ? todo2 : todo1;      // start of "now" queue
        writep[1] = writep[0];                // end of "now" queue
        writep[0] = (d & 1) ? todo1 : todo2;  // "later" queue (empty)

        // Now consume the "now" queue, filling both the "now" queue
        // and the "later" queue as we go. Points in the "now" queue
        // have distance d from the starting square. Points in the
        // "later" queue have distance d+1.
        while (readp < writep[1]) {
            int p = *readp++;
            if (mark[p] < 2) {
                mark[p] = 2;
                x = p % w;
                y = p / w;
                if (x > 0 && !mark[p-1]) {                // go left
                    mark[p-1] = same = (grid[p-1] == grid[p]);
                    *writep[same]++ = p-1;
                }
                if (x + 1 < w && !mark[p+1]) {            // go right
                    mark[p+1] = same = (grid[p+1] == grid[p]);
                    if (y == h - 1 && x == w - 2)
                        return d + !same;
                    *writep[same]++ = p+1;
                }
                if (y > 0 && !mark[p-w]) {                // go up
                    mark[p-w] = same = (grid[p-w] == grid[p]);
                    *writep[same]++ = p-w;
                }
                if (y + 1 < h && !mark[p+w]) {            // go down
                    mark[p+w] = same = (grid[p+w] == grid[p]);
                    if (y == h - 2 && x == w - 1)
                        return d + !same;
                    *writep[same]++ = p+w;
                }
            }
        }
    }
}

回复收藏 0 原文

鱼窥荷 2024-08-25 12:01:02

本文有一个稍微更快的 Dijsktra 算法版本，它降低了常数项。不过仍然是 O(n)，因为你真的必须查看每个节点。

http://citeseerx. ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf

回复收藏 0 原文

顾北清歌寒 2024-08-25 12:01:02

编辑：之前的版本错误并已修复，

因为 Djikstra 已退出。我会推荐一个简单的 DP，它的优点是在最佳时间运行并且不需要您构建图表。

D[a][b] 是仅使用 x<> 的节点到 x=a 和 y=b 的最小距离。 =a 和 y<=b。

由于您无法对角移动，因此在计算 < 时只需查看 D[a-1][b] 和 D[a][b-1] code>D[a][b]

这将为您提供以下递归关系：

D[a][b] = min(if grid[a][b] == grid[a-1][b] then D[a-1][b] else D[a-1][b] + 1, if grid[a][b] == grid[a][b-1] then D[a][b-1] else D[a][b-1] + 1)

但是，在这种情况下仅执行上述操作会失败：

0 1 2 3 4
5 6 7 8 9
A b d e g
A f r t s
A z A A A
A A A f d

因此，您需要缓存迄今为止找到的每组节点的最小值。而不是查看D[a][b]，而是查看grid[a][b]处的组的最小值。

下面是一些 Python 代码：
注意 grid 是作为输入给出的网格，并且假设网格是 N by N

groupmin = {}

for x in xrange(0, N):
    for y in xrange(0, N):
        groupmin[grid[x][y]] = N+1#N+1 serves as 'infinity'

#init first row and column
groupmin[grid[0][0]] = 0
for x in xrange(1, N):
    gm = groupmin[grid[x-1][0]]
    temp = (gm) if grid[x][0] == grid[x-1][0] else (gm + 1)
    groupmin[grid[x][0]] = min(groupmin[grid[x][0]], temp); 

for y in xrange(1, N):
    gm = groupmin[grid[0][y-1]]
    temp = (gm) if grid[0][y] == grid[0][y-1] else (gm + 1)
    groupmin[grid[0][y]] = min(groupmin[grid[0][y]], temp); 

#do the rest of the blocks
for x in xrange(1, N):
    for y in xrange(1, N):
        gma = groupmin[grid[x-1][y]]
        gmb = groupmin[grid[x][y-1]]
        a = (gma) if grid[x][y] == grid[x-1][y] else (gma + 1)
        b = (gmb) if grid[x][y] == grid[x][y-1] else (gma + 1)
        temp = min(a, b)
        groupmin[grid[x][y]] = min(groupmin[grid[x][y]], temp); 

ans = groupmin[grid[N-1][N-1]]

这将在 O 中运行(N^2 * f(x))，其中 f(x) 是哈希函数所花费的时间，通常是 O(1) 时间，而这个是您可以期望的最好的函数之一，它的常数因子比 Djikstra 的常数因子低得多。

您应该能够轻松地在一秒钟内处理高达几千个的 N。

EDIT: THE PREVIOUS VERSION WAS WRONG AND WAS FIXED

Since a Djikstra is out. I'll recommend a simple DP, which has the benefit of running in the optimal time and not having you construct a graph.

D[a][b] is the minimal distance to x=a and y=b using only nodes where the x<=a and y<=b.

And since you can't move diagonally you only have to look at D[a-1][b] and D[a][b-1] when calculating D[a][b]

This gives you the following recurrence relationship:

D[a][b] = min(if grid[a][b] == grid[a-1][b] then D[a-1][b] else D[a-1][b] + 1, if grid[a][b] == grid[a][b-1] then D[a][b-1] else D[a][b-1] + 1)

However doing only the above fails on this case:

0 1 2 3 4
5 6 7 8 9
A b d e g
A f r t s
A z A A A
A A A f d

Therefore you need to cache the minimum of each group of node you found so far. And instead of looking at D[a][b] you look at the minimum of the group at grid[a][b].

Here's some Python code:
Note grid is the grid that you're given as input and it's assumed the grid is N by N

groupmin = {}

for x in xrange(0, N):
    for y in xrange(0, N):
        groupmin[grid[x][y]] = N+1#N+1 serves as 'infinity'

#init first row and column
groupmin[grid[0][0]] = 0
for x in xrange(1, N):
    gm = groupmin[grid[x-1][0]]
    temp = (gm) if grid[x][0] == grid[x-1][0] else (gm + 1)
    groupmin[grid[x][0]] = min(groupmin[grid[x][0]], temp); 

for y in xrange(1, N):
    gm = groupmin[grid[0][y-1]]
    temp = (gm) if grid[0][y] == grid[0][y-1] else (gm + 1)
    groupmin[grid[0][y]] = min(groupmin[grid[0][y]], temp); 

#do the rest of the blocks
for x in xrange(1, N):
    for y in xrange(1, N):
        gma = groupmin[grid[x-1][y]]
        gmb = groupmin[grid[x][y-1]]
        a = (gma) if grid[x][y] == grid[x-1][y] else (gma + 1)
        b = (gmb) if grid[x][y] == grid[x][y-1] else (gma + 1)
        temp = min(a, b)
        groupmin[grid[x][y]] = min(groupmin[grid[x][y]], temp); 

ans = groupmin[grid[N-1][N-1]]

This will run in O(N^2 * f(x)) where f(x) is the time the hash function takes which is normally O(1) time and this is one of the best functions you can hope for and it has a lot lower constant factor than Djikstra's.

You should easily be able to handle N's of up to a few thousand in a second.

回复收藏 0 原文

梦里寻她 2024-08-25 12:01:02

是否有办法确保除了广度优先搜索之外的任何方法都能满足最少的轮数启发式？

更快的方法，还是更简单的方法？ :)

您可以从两端交替进行广度优先搜索，直到两个区域在中间相遇。如果图表有很多扇出（例如城市地图），这会快得多，但最坏的情况是相同的。这实际上取决于图表。

回复收藏 0 原文

习惯成性 2024-08-25 12:01:02

这是我使用简单 BFS 的实现。 Dijkstra 也可以工作（替代按 stl::queue 成本降序排序的 stl::priority_queue），但会严重过度。

这里需要注意的是，我们实际上是在一个图上搜索，该图的节点与给定数组中的单元格并不完全对应。为了获得该图，我使用了一个简单的基于 DFS 的洪水填充（您也可以使用 BFS，但 DFS 对我来说稍微短一些）。其作用是找到所有连接的且相同的字符组件，并将它们分配给相同的颜色/节点。因此，在填充之后，我们可以通过查看 color[row][col] 的值来找出每个单元格属于底层图中的哪个节点。然后，我只需迭代单元格并找出相邻单元格颜色不同（即位于不同节点中）的所有单元格。因此，这些是我们图的边缘。当我迭代单元格以消除重复的边缘时，我维护一个 stl::set 边缘。之后，从边列表构建邻接列表是一个简单的事情，我们就为 bfs 做好了准备。

代码（C++）：

#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <set>
#include <cstring>

using namespace std;
#define SIZE 1001
vector<string> board;

int colour[SIZE][SIZE];
int dr[]={0,1,0,-1};
int dc[]={1,0,-1,0};

int min(int x,int y){ return (x<y)?x:y;}
int max(int x,int y){ return (x>y)?x:y;}

void dfs(int r, int c, int col, vector<string> &b){
    if (colour[r][c]<0){
        colour[r][c]=col;
        for(int i=0;i<4;i++){
            int nr=r+dr[i],nc=c+dc[i];
            if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && b[nr][nc]==b[r][c])
                dfs(nr,nc,col,b);
        }
    }
}

int flood_fill(vector<string> &b){
    memset(colour,-1,sizeof(colour));
    int current_node=0;
    for(int i=0;i<b.size();i++){
        for(int j=0;j<b[0].size();j++){
            if (colour[i][j]<0){
                dfs(i,j,current_node,b);
                current_node++;
            }
        }
    }
    return current_node;
}

vector<vector<int> > build_graph(vector<string> &b){
    int total_nodes=flood_fill(b);
    set<pair<int,int> > edge_list;
    for(int r=0;r<b.size();r++){
        for(int c=0;c<b[0].size();c++){
            for(int i=0;i<4;i++){
                int nr=r+dr[i],nc=c+dc[i];
                if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && colour[nr][nc]!=colour[r][c]){
                    int u=colour[r][c], v=colour[nr][nc];
                    if (u!=v) edge_list.insert(make_pair(min(u,v),max(u,v)));
                }
            }
        }
    }
    vector<vector<int> > graph(total_nodes);
    for(set<pair<int,int> >::iterator edge=edge_list.begin();edge!=edge_list.end();edge++){
        int u=edge->first,v=edge->second;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    return graph;
}

int bfs(vector<vector<int> > &G, int start, int end){
    vector<int> cost(G.size(),-1);
    queue<int> Q;
    Q.push(start);
    cost[start]=0;
    while (!Q.empty()){
        int node=Q.front();Q.pop();
        vector<int> &adj=G[node];
        for(int i=0;i<adj.size();i++){
            if (cost[adj[i]]==-1){
                cost[adj[i]]=cost[node]+1;
                Q.push(adj[i]);
            }
        }
    }
    return cost[end];
}

int main(){
    string line;
    int rows,cols;
    cin>>rows>>cols;
    for(int r=0;r<rows;r++){
        line="";
        char ch;
        for(int c=0;c<cols;c++){
            cin>>ch;
            line+=ch;
        }
        board.push_back(line);
    }
    vector<vector<int> > actual_graph=build_graph(board);
    cout<<bfs(actual_graph,colour[0][0],colour[rows-1][cols-1])<<"\n";
}

这只是一个快速破解，可以进行很多改进。但我认为它在运行时复杂性方面非常接近最佳，并且对于数千尺寸的板来说应该运行得足够快（不要忘记更改 SIZE< 的 #define /代码>）。另外，我只用你提供的一种情况进行了测试。因此，正如 Knuth 所说，“请注意上述代码中的错误；我只是证明了它的正确性，并未尝试过。” :)。

This is my implementation using a simple BFS. A Dijkstra would also work (substitute a stl::priority_queue that sorts by descending costs for the stl::queue) but would seriously be overkill.

The thing to notice here is that we are actually searching on a graph whose nodes do not exactly correspond to the cells in the given array. To get to that graph, I used a simple DFS-based floodfill (you could also use BFS, but DFS is slightly shorter for me). What that does is to find all connected and same character components and assign them to the same colour/node. Thus, after the floodfill we can find out what node each cell belongs to in the underlying graph by looking at the value of colour[row][col]. Then I just iterate over the cells and find out all the cells where adjacent cells do not have the same colour (i.e. are in different nodes). These therefore are the edges of our graph. I maintain a stl::set of edges as I iterate over the cells to eliminate duplicate edges. After that it is a simple matter of building an adjacency list from the list of edges and we are ready for a bfs.

Code (in C++):

#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <set>
#include <cstring>

using namespace std;
#define SIZE 1001
vector<string> board;

int colour[SIZE][SIZE];
int dr[]={0,1,0,-1};
int dc[]={1,0,-1,0};

int min(int x,int y){ return (x<y)?x:y;}
int max(int x,int y){ return (x>y)?x:y;}

void dfs(int r, int c, int col, vector<string> &b){
    if (colour[r][c]<0){
        colour[r][c]=col;
        for(int i=0;i<4;i++){
            int nr=r+dr[i],nc=c+dc[i];
            if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && b[nr][nc]==b[r][c])
                dfs(nr,nc,col,b);
        }
    }
}

int flood_fill(vector<string> &b){
    memset(colour,-1,sizeof(colour));
    int current_node=0;
    for(int i=0;i<b.size();i++){
        for(int j=0;j<b[0].size();j++){
            if (colour[i][j]<0){
                dfs(i,j,current_node,b);
                current_node++;
            }
        }
    }
    return current_node;
}

vector<vector<int> > build_graph(vector<string> &b){
    int total_nodes=flood_fill(b);
    set<pair<int,int> > edge_list;
    for(int r=0;r<b.size();r++){
        for(int c=0;c<b[0].size();c++){
            for(int i=0;i<4;i++){
                int nr=r+dr[i],nc=c+dc[i];
                if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && colour[nr][nc]!=colour[r][c]){
                    int u=colour[r][c], v=colour[nr][nc];
                    if (u!=v) edge_list.insert(make_pair(min(u,v),max(u,v)));
                }
            }
        }
    }
    vector<vector<int> > graph(total_nodes);
    for(set<pair<int,int> >::iterator edge=edge_list.begin();edge!=edge_list.end();edge++){
        int u=edge->first,v=edge->second;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    return graph;
}

int bfs(vector<vector<int> > &G, int start, int end){
    vector<int> cost(G.size(),-1);
    queue<int> Q;
    Q.push(start);
    cost[start]=0;
    while (!Q.empty()){
        int node=Q.front();Q.pop();
        vector<int> &adj=G[node];
        for(int i=0;i<adj.size();i++){
            if (cost[adj[i]]==-1){
                cost[adj[i]]=cost[node]+1;
                Q.push(adj[i]);
            }
        }
    }
    return cost[end];
}

int main(){
    string line;
    int rows,cols;
    cin>>rows>>cols;
    for(int r=0;r<rows;r++){
        line="";
        char ch;
        for(int c=0;c<cols;c++){
            cin>>ch;
            line+=ch;
        }
        board.push_back(line);
    }
    vector<vector<int> > actual_graph=build_graph(board);
    cout<<bfs(actual_graph,colour[0][0],colour[rows-1][cols-1])<<"\n";
}

This is just a quick hack, lots of improvements can be made. But I think it is pretty close to optimal in terms of runtime complexity, and should run fast enough for boards of size of several thousand (don't forget to change the #define of SIZE). Also, I only tested it with the one case you have provided. So, as Knuth said, "Beware of bugs in the above code; I have only proved it correct, not tried it." :).

回复收藏 0 原文

~没有更多了~