技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 广度优先搜索解决“营救公主”问题

广度优先搜索解决“营救公主”问题

浏览:2579次  出处信息

   在之前的一片文章(迷宫营救公主算法)中提供了一个半成品的解决方案,之所以说他是半成品,是因为首先选择的算法就不对,采用的是深度优先搜索,其次也没有真正的用对深度优先算法,走过的点应该标记为已经走过,而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。

   文章链接:【图论】广度优先搜索和深度优先搜索

   就营救公主的问题而言,这里不再重复描述问题了,请点击这里查看题目分析:链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码:

   这里每个节点有三种状态:

   *)该状态表示墙,如果访问到该类型节点,则不用继续遍历。应退回至上层节点。

   .)该状态表示该节点通行,访问到该节点应该将节点压入队列。并将该节点标记为已经访问。为区别图中已经有的几种元素,这里定义一个新的标记’#’来表示已经访问过的节点。同时可以使用一个二维数组记录从起始节点到该节点的访问距离step[i][j],该值应该是由其上一个节点的值加1之后得到。这样起始节点的值为1,依次每一个节点的距离都可以得到。

   P)该状态表示已经搜索到了公主的位置,搜索结束。这时给出P点的距离,如果该距离值在给定的范围内,则可以营救出公主,否则失败。

   解决问题的关键在于用一个step数组记录每个节点的距离起始点的距离,另外用一个’#’字符标记该节点已经被访问过,避免走“回头路”。

BFS(G, s)    

       init V[G]   // 由测试用例实现。

       status[s] = S    // s王子的位置,通过一次遍历可以获取其坐标。

       

       int count = -1;

       queue q

       q.add(s) // 将王子的位置入队。

       while !q.isEmpty()

           t = q.poll()

           for each vertex v in Adj[t] // 与t邻接的点

               if status[v] = 'P'    // 只对未访问的操作

                   count = step[v] = step[t] + 1

                   q.clear()

                   break

               elseif status[v] = '.'    

                   status[v] = '#'    // 标记为已经走过该节点

                   q.add(v)

                   step[v] = step[t] + 1 // 累加得到当前节点的步长

               elseif status[v] = '*'

                   step[v] = -1   // 遇到墙,则将该节点的距离置为-1,在遍历完整个图时,

                                  // 如果遇到最后一个节点的值为-1,则表明没有找到。

               else

                   error

               

       if count != -1

           if count < L

               return true

       return false

   

   

有了上面的伪代码,翻译成代码也就非常简单了。
package com;

   import java.util.LinkedList;

   import java.util.List;

   import java.util.Queue;

   /**

    * 公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。

    * 为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只

    * 能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步。地图由'S','P','.','*'

    * 四种符号构成,'.'表示王子可以通过,'*'表示墙,王子不能通过;'S'表示王子的位置;'P'表示公主

    * 的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:

    */

   public class SavePrincess

   {

       private int m;

       private int n;

       private char[][] visited;

       private Position s = null;

       private Position p = null;

       public static void main(String[] args)

       {

           char maze[][] = {

           /* 0 1 2 3 4 5 6 7 8 9 */

           /* 0 */{ '.', '*', '.', '.', '.', '*', '.', '.', '.', '.' },

           /* 1 */{ '*', 'S', '*', '.', '.', '.', '.', '.', '.', '.' },

           /* 2 */{ '.', '*', '*', '.', '.', '.', '.', '.', '.', '.' },

           /* 3 */{ '.', '.', '*', '*', '*', '.', '.', '.', '.', '.' },

           /* 4 */{ '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },

           /* 5 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },

           /* 6 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },

           /* 7 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },

           /* 8 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },

           /* 9 */{ '.', 'P', '.', '.', '*', '.', '.', '.', '.', '.' } };

           new SavePrincess().saved(maze, 10, 8, 11);

       }

       /**

        * @param vis

        *            M行N列迷宫

        * @param m

        *            M

        * @param n

        *            N

        * @param t

        *            T

        *

        * @return boolean true表示营救成功,反之表示失败。

        */

       public boolean saved(char[][] vis, int m, int n, int t)

       {

           if (t < 0)

           {

               return false;

           }

           this.m = m;

           this.n = n;

           this.visited = vis;

           int step[][] = new int[m][n];

           init(m, n, step);

           if (s == null || p == null)

           {

               System.out.println("input visited error!");

               return false;

           }

           Queue<Position> queue = new LinkedList<Position>();

           queue.add(s);

           int l = -1;

           while (!queue.isEmpty())

           {

               Position e = queue.poll();

               l = dealOneNode(step, queue, l, e);

           }

           if (l != -1 && l <= t)

           {

               System.out.println("Saved the princess in " + l + " seconds!");

               return true;

           }

           System.out.println("failed saved the princess! " + l + " > " + "t");

           return false;

       }

       private void init(int m, int n, int[][] step)

       {

           for (int i = 0; i != m; i++)

           {

               for (int j = 0; j != n; j++)

               {

                   System.out.print(visited[i][j]);

                   System.out.print(' ');

                   step[i][j] = 0;

                   switch (visited[i][j])

                   {

                   case '*':

                       break;

                   case 'S':

                       this.s = new Position(i, j, 'S');

                       break;

                   case '.':

                       break;

                   case 'P':

                       this.p = new Position(i, j, 'P');

                       break;

                   default:

                       System.out.println("input visited error!");

                       System.exit(-1);

                   }

               }

               System.out.println("");

           }

       }

       private int dealOneNode(int[][] step, Queue<Position> queue, int l, Position e)

       {

           /**

            * 在求相邻节点时做了一点优化,遇到墙的节点则不放到相邻节点中。

            * 从设计思想和可读性上看不是太好,从运行效率考虑,可以。

            */

           for (Position c : getNextPostions(e))

           {

               switch (c.getV())

               {

               case 'P':

                   queue.clear();

                   l = step[e.getI()][e.getJ()] + 1;

                   break;

               case '.':

                   visited[c.getI()][c.getJ()] = '#';

                   queue.add(c);

                   step[c.getI()][c.getJ()] = step[e.getI()][e.getJ()] + 1;

                   break;

               default:

                   // 不可能进入该分支。

                   System.err.println("some error!");

                   break;

               }

           }

           return l;

       }

       /**

        * 取有效节点。

        * 遇到墙则不加入相邻节点中。

        *

        * @param e

        * @return

        */

       private List<Position> getNextPostions(Position e)

       {

           int i = e.getI();

           int j = e.getJ();

           List<Position> lst1 = new LinkedList<Position>();

           addOneNode(i + 1, j, lst1);

           addOneNode(i, j + 1, lst1);

           addOneNode(i - 1, j, lst1);

           addOneNode(i, j - 1, lst1);

           return lst1;

       }

       private void addOneNode(int i, int j, List<Position> lst)

       {

           if (i >= m || i < 0 || j >= n || j < 0)

           {

               return;

           }

           char v = visited[i][j];

           switch (v)

           {

           case '.':

           case 'P':

               lst.add(new Position(i, j, v));

               break;

           default:

               break;

           }

       }

       private class Position

       {

           private int i;

           private int j;

           private char v;

           public Position(int i, int j, char value)

           {

               this.i = i;

               this.j = j;

               this.v = value;

           }

           public char getV()

           {

               return v;

           }

           public int getI()

           {

               return i;

           }

           public int getJ()

           {

               return j;

           }

           public String toString()

           {

               return "(" + i + ", " + j + ")";

           }

       }

   }

   

建议继续学习:

  1. C++11的Lambda使用一例:华容道求解    (阅读:2443)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1