vlambda博客
学习文章列表

贪心算法与老鼠走迷宫

耿祥义

只要学过数组就可以看懂，即学过教材第2，3章即可（略微用到类和对象的最基本的知识,见第4章，当然我可以不用，把算法都写到主类的main方法里，但那样做我觉得代码不好看！）

教材介绍二维码：

单击阅读原文下载源代码：

链接:

https://pan.baidu.com/s/18EvAMu89mjxusQf_8LnPxA

提取码: 8ty6

1.贪心算法   

       

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。即不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

    

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解。贪心算法的特点是一步一步地进行，以当前情况为基础，根据某个算法作最优选择，而不考虑各种可能的整体情况，通过每一步贪心选择，可得到局部最优解。由于贪心算法每一步是局部最优解，因此，如果使用贪心算法，必须要判断是否得到了最优解。

      

例如，蒙眼爬山， 蒙眼爬山者 每次在周围选择一个 最陡峭的方向 前进一小步（最优选择），但是蒙眼爬山者最后爬山的山可能不是最高的山（多峰山），假设蒙眼爬山者携带了一个自动通报海拔高度的小仪器，每次都报告海拔高度，当蒙眼爬山者发现周围没有陡峭的方向可走了，报告海拔高度恰好是想要的高度，那就找到了最优解，否则就知道自己旋入了局部最优解，无法继续下去了。

     

贪心算法 仅仅是一种思想 而已，不像您熟悉的选择法排序，有明确的算法步骤。

2. 老鼠走迷宫

    

这里，我们将贪心算法用于老鼠走迷宫。

    

建立的模型如下：

    

让二维数组的单元代表迷宫的点。单元值取Integer的最大值Integer.MAX_VALUE代表 出口 ，单元值取Integer的最小值Integer.MIN_VALUE代表 墙 ，单元值在最大值和最小值之间代表 路点 （初值是0）。

    

老鼠每次 贪心的办法 如下（这里称二维数组单元为路点，其值为路值）：

  

（1）如果发现当前路点 不是出口（最大值 ），即不是最优解，就降低优先度，将当前路值减1，进行（2），否则进行（5）

  

（2）在当前路点的东西南北方向选出路值比当前路值大的最大的 新路点 ，如果找到进行（3）否则回到（1）。

  

（3）老鼠 达到 选出的新路点,进行（4）。

  

（4）回到（1）。

  

（5）结束。

     

如果路点的路值不会被减到等于墙的值(Integer.MIN_VALUE)，就一定能到达出口 ，否则某个路点或墙会被当成出口（因为 Integer.MIN_VALUE-1 等于 Integer.MAX_VALUE ,老鼠陷入局部最优解）。

   

下列运行效果中，显示老鼠找到出口（如果二维数组单元多，可以用Long类）。显示了老鼠在迷宫中走的过程。最后输出的二维数组，如果路值是-1表示老鼠走过此路点1次，-2老鼠走过此路点2次....。

3.代码( 单击阅读原文下载)

链接:

https://pan.baidu.com/s/18EvAMu89mjxusQf_8LnPxA

提取码: 8ty6

MainClass.java

public class MainClass {

   public static void main(String args[]){

      int Y= Integer.MAX_VALUE;//最优解

      int N = Integer.MIN_VALUE;//无解 

      int maze[][] =    {{0,N,0,0,0},

                         {0,0,0,0,N},

                         {N,0,N,0,0},

                         {0,0,0,N,Y}};

      Mouse jerry = new Mouse();

      jerry.walkMaze(maze,Y,N);

   }

}

Mouse.java

public class Mouse {

    int mousePI = 0; //老鼠初始位置

    int mousePJ = 0; //老鼠初始位置

    int rows;

    int columns;

    int maze[][];   //迷宫

    int Y ;//最优解

    int N ;//无解

    public void walkMaze(int maze[][],int yes,int no) {

      this.maze = maze;

      Y = yes;//最优解

      N = no;//无解

      rows = maze.length;

      columns = maze[0].length;

      System.out.println("迷宫初始状态:");

      showMaze();

      //贪心算法：当前位置周围的最大的整数之一是局部最优解之一，

      //即老鼠选择的下一个位置。

      while(maze[mousePI][mousePJ]!=Y){ //如果不是最优解

         System.out.printf("老鼠达到位置(%d,%d)\n",mousePI,mousePJ);

         maze[mousePI][mousePJ] = maze[mousePI][mousePJ]-1;//降低优先度

         int m =mousePI;

         int n =mousePJ;

         int max = maze[mousePI][mousePJ];

         if(mousePI<rows-1){ //以下算法:在当前位置的周围寻找最优解（最优位置）：

            if(maze[mousePI+1][mousePJ]>max){

               max = maze[mousePI+1][mousePJ];  

               m = mousePI+1;

               n = mousePJ;

            }

         }

         if(mousePI>=1){

            if(maze[mousePI-1][mousePJ]>max){

               max = maze[mousePI-1][mousePJ];  

               m =mousePI-1;

               n = mousePJ;

            }

         }

         if(mousePJ<columns-1){

            if(maze[mousePI][mousePJ+1]>max){

               max = maze[mousePI][mousePJ+1];  

               m = mousePI;

               n = mousePJ+1;

            }

         }

         if(mousePJ>=1){

            if(maze[mousePI][mousePJ-1]>max){

               max = maze[mousePI][mousePJ-1];  

               m = mousePI;

               n = mousePJ-1;

            }

         }

         mousePI = m;

         mousePJ = n; 

     }

     System.out.println("\n找到最优解："+maze[mousePI][mousePJ]);

     System.out.printf("老鼠位置(%d,%d)\n",mousePI,mousePJ);

     showMaze();

    }

    void showMaze(){ //输出二维数组

        for(int i=0;i<rows;i++) {

            for(int j=0;j<columns;j++){

               if(maze[i][j]==N)

                  System.out.printf("%6s","#");//代表墙

               else if(maze[i][j]==Y)

                  System.out.printf("%6s","*");//代表出口

               else

                  System.out.printf("%6s",""+maze[i][j]);

            } 

            System.out.println();

        }

    }

}