貪心算法與老鼠走迷宮
耿祥義
只要學過數組就可以看懂，即學過教材第2，3章即可（略微用到類和對象的最基本的知識,見第4章，當然我可以不用，把算法都寫到主類的main方法裡，但那樣做我覺得代碼不好看！）
教材介紹二維碼：
單擊閱讀原文下載原始碼：
連結:
https://pan.baidu.com/s/18EvAMu89mjxusQf_8LnPxA
提取碼: 8ty6
1.貪心算法
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。即不從整體最優上加以考慮，算法得到的是在某種意義上的局部最優解 。 貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇。也就是說，不從整體最優上加以考慮，做出的只是在某種意義上的局部最優解。貪心算法的特點是一步一步地進行，以當前情況為基礎，根據某個算法作最優選擇，而不考慮各種可能的整體情況，通過每一步貪心選擇，可得到局部最優解。由於貪心算法每一步是局部最優解，因此，如果使用貪心算法，必須要判斷是否得到了最優解。 例如，蒙眼爬山，蒙眼爬山者每次在周圍選擇一個最陡峭的方向前進一小步（最優選擇），但是蒙眼爬山者最後爬山的山可能不是最高的山（多峰山），假設蒙眼爬山者攜帶了一個自動通報海拔高度的小儀器，每次都報告海拔高度，當蒙眼爬山者發現周圍沒有陡峭的方向可走了，報告海拔高度恰好是想要的高度，那就找到了最優解，否則就知道自己旋入了局部最優解，無法繼續下去了。 貪心算法僅僅是一種思想而已，不像您熟悉的選擇法排序，有明確的算法步驟。 讓二維數組的單元代表迷宮的點。單元值取Integer的最大值Integer.MAX_VALUE代表出口，單元值取Integer的最小值Integer.MIN_VALUE代表牆，單元值在最大值和最小值之間代表路點（初值是0）。 老鼠每次貪心的辦法如下（這裡稱二維數組單元為路點，其值為路值）： （1）如果發現當前路點不是出口（最大值），即不是最優解，就降低優先度，將當前路值減1，進行（2），否則進行（5） （2）在當前路點的東西南北方向選出路值比當前路值大的最大的新路點，如果找到進行（3）否則回到（1）。 如果路點的路值不會被減到等於牆的值(Integer.MIN_VALUE)，就一定能到達出口，否則某個路點或牆會被當成出口（因為Integer.MIN_VALUE-1等於Integer.MAX_VALUE,老鼠陷入局部最優解）。 下列運行效果中，顯示老鼠找到出口（如果二維數組單元多，可以用Long類）。顯示了老鼠在迷宮中走的過程。最後輸出的二維數組，如果路值是-1表示老鼠走過此路點1次，-2老鼠走過此路點2次....。連結:
https://pan.baidu.com/s/18EvAMu89mjxusQf_8LnPxA
提取碼: 8ty6
public static void main(String args[]){ int Y= Integer.MAX_VALUE;//最優解 int N = Integer.MIN_VALUE;//無解 int maze[][] = {{0,N,0,0,0}, Mouse jerry = new Mouse(); jerry.walkMaze(maze,Y,N); int mousePI = 0; //老鼠初始位置 int mousePJ = 0; //老鼠初始位置 public void walkMaze(int maze[][],int yes,int no) { columns = maze[0].length; System.out.println("迷宮初始狀態:"); //貪心算法：當前位置周圍的最大的整數之一是局部最優解之一， while(maze[mousePI][mousePJ]!=Y){ //如果不是最優解 System.out.printf("老鼠達到位置(%d,%d)\n",mousePI,mousePJ); maze[mousePI][mousePJ] = maze[mousePI][mousePJ]-1;//降低優先度 int max = maze[mousePI][mousePJ]; if(mousePI<rows-1){ //以下算法:在當前位置的周圍尋找最優解（最優位置）： if(maze[mousePI+1][mousePJ]>max){ max = maze[mousePI+1][mousePJ]; if(maze[mousePI-1][mousePJ]>max){ max = maze[mousePI-1][mousePJ]; if(maze[mousePI][mousePJ+1]>max){ max = maze[mousePI][mousePJ+1]; if(maze[mousePI][mousePJ-1]>max){ max = maze[mousePI][mousePJ-1]; System.out.println("\n找到最優解："+maze[mousePI][mousePJ]); System.out.printf("老鼠位置(%d,%d)\n",mousePI,mousePJ); void showMaze(){ //輸出二維數組 for(int i=0;i<rows;i++) { for(int j=0;j<columns;j++){ System.out.printf("%6s","#");//代表牆 System.out.printf("%6s","*");//代表出口 System.out.printf("%6s",""+maze[i][j]);