Algorithm学习笔记 --- 迷宫问题
關于搜索我做了一個整理這里用到的是深度搜索還有回溯算法。
意思是按著一個方向找如果沒有依次返回。
http://www.cnblogs.com/hustcat/archive/2008/04/09/1144645.html
這里有位大師的講解不錯！
計算機解迷宮時，通常用的是"試探和回溯"的方法，即從入口出發，順某一方向向前探索，若能走通，則繼續往前走；否則沿原路退回，換一個方向再繼續探索，直至所有可能的通路都探索到為止,如果所有可能的通路都試探過，還是不能走到終點，那就說明該迷宮不存在從起點到終點的通道。
1．從入口進入迷宮之后，不管在迷宮的哪一個位置上，都是先往東走，如果走得通就繼續往東走，如果在某個位置上往東走不通的話，就依次試探往南、往西和往北方向，從一個走得通的方向繼續往前直到出口為止；
2．如果在某個位置上四個方向都走不通的話，就退回到前一個位置，換一個方向再試，如果這個位置已經沒有方向可試了就再退一步，如果所有已經走過的位置的四個方向都試探過了，一直退到起始點都沒有走通，那就說明這個迷宮根本不通；
??
? 3．所謂"走不通"不單是指遇到"墻擋路"，還有"已經走過的路不能重復走第二次"，它包括"曾經走過而沒有走通的路"。顯然為了保證在任何位置上都能沿原路退回，需要用一個"后進先出"的結構即棧來保存從入口到當前位置的路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。
由此，求迷宮中一條路徑的算法的基本思想是：
若當前位置"可通"，則納入"當前路徑"，并繼續朝"下一位置"探索；若當前位置"不可通"，則應順著"來的方向"退回到"前一通道塊"，然后朝著除"來向"之外的其他方向繼續探索；若該通道塊的四周四個方塊均"不可通"，則應從"當前路徑"上刪除該通道塊。
設定當前位置的初值為入口位置；?
do{
若當前位置可通，?
則{
將當前位置插入棧頂； // 納入路徑?
若該位置是出口位置，則算法結束；?
// 此時棧中存放的是一條從入口位置到出口位置的路徑
否則切換當前位置的東鄰方塊為新的當前位置；?
}
否則
{
若棧不空且棧頂位置尚有其他方向未被探索，?
則設定新的當前位置為: 沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；
若棧不空但棧頂位置的四周均不可通，?
則{ 刪去棧頂位置； // 從路徑中刪去該通道塊
若棧不空，則重新測試新的棧頂位置，?
直至找到一個可通的相鄰塊或出棧至棧空；?
}?
}?
} while (棧不空)；
#include?<cstdio>
#include <iostream>
#define?WALL???0??//墻
#define?CORRIDOR?1?//通道
#define?PATH??9?//為路徑上的一塊
#define?TRIED?2?//
#define?ROW_NUM????7?//迷宮數組行數
#define?COL_NUM???13?//列數
#define?TRUE?1
#define?FALSE?0
#define?MAXSIZE?50
typedef?struct?
{
????int?row;
????int?col;
}PosType;
typedef?struct?
{
????int?ord;??????//通道塊在路徑上的"序號"
????PosType?seat;?//通道塊在迷宮中的坐標
????int?di;???????//當前通道塊的方向
}SElemType;
typedef?struct?
{
????SElemType?S[MAXSIZE];
????int?top;
}MazeType;
//迷宮
int?grid[ROW_NUM][COL_NUM]={{1,?1,?1,?0,?1,?1,?1,?0,?0,?1,?1,?1,?1},
????????????????????????????{1,?0,?1,?1,?1,?0,?1,?1,?1,?1,?1,?0,?1},
????????????????????????????{1,?0,?0,?0,?0,?0,?1,?0,?1,?0,?1,?0,?1},
????????????????????????????{1,?0,?0,?0,?1,?1,?1,?0,?1,?0,?1,?1,?1},
????????????????????????????{1,?1,?1,?1,?1,?0,?0,?0,?0,?1,?0,?0,?0},
????????????????????????????{0,?0,?0,?0,?1,?0,?0,?0,?0,?0,?0,?0,?0},
????????????????????????????{0,?0,?0,?0,?1,?1,?1,?1,?1,?1,?1,?1,?1}};
//當前位置是否可以通過
bool?Valid(PosType?pos)
{
????if(pos.row>=0&&pos.row<=ROW_NUM&&pos.col>=0&&pos.col<=COL_NUM&&grid[pos.row][pos.col]==CORRIDOR)
????????return?TRUE;
????else
????????return?FALSE;
}
void?FootPrint(PosType?pos)//留下足跡
{
????grid[pos.row][pos.col]=PATH;
}
void?Undo(PosType?pos)?//留下不能通過的標識
{
????grid[pos.row][pos.col]=TRIED;
}
//當前位置的下一個位置
PosType?NextPos(PosType?cur,int?di)
{
????PosType?next;
????switch(di)
????{
????case?0:?//東
????????next.row=cur.row;
????????next.col=cur.col+1;
????????break;
????case?1:?//南
????????next.row=cur.row+1;
????????next.col=cur.col;
????????break;
????case?2:??//西
????????next.row=cur.row;
????????next.col=cur.col-1;
????????break;
????case?3:??//北
????????next.row=cur.row-1;
????????next.col=cur.col;
????????break;
????}
????return?next;
}
//是否到達終點
bool?Done(PosType?cur,PosType?end)
{
????if(cur.row==end.row&&cur.col==end.col)
????????return?TRUE;
????else
????????return?FALSE;
}
//尋找迷宮路徑
bool?MazePath(MazeType?&path,PosType?start,PosType?end)
{
????SElemType?e;
????path.top=-1;
????int?step=1;
????PosType?curpos=start;
????do
????{
????????if(Valid(curpos))
????????{
????????????FootPrint(curpos);
????????????e.ord=step;
????????????e.di=0;
????????????e.seat=curpos;
????????????path.S[++path.top]=e;
????????????if(Done(curpos,end))
????????????????return?TRUE;
????????????curpos=NextPos(curpos,0);
????????????step++;
????????}
????????else
????????{
????????????if(path.top>-1)//棧不空
????????????{
????????????????e=path.S[path.top--];
????????????????while(e.di==3&&path.top>-1)
????????????????{
????????????????????Undo(e.seat);
????????????????????e=path.S[path.top--];
????????????????}
????????????????if(e.di<3)
????????????????{
????????????????????e.di++;
????????????????????path.S[++path.top]=e;
????????????????????curpos=NextPos(e.seat,e.di);
????????????????}
????????????}//if
????????}//else
????}while(path.top>-1);
????return?FALSE;
}
//輸出路徑
void?PrintPath(MazeType?path)
{
????int?i=0;
????while(i<=path.top)
????{
????????printf("第%d步:(%d,%d)\n",path.S[i].ord,path.S[i].seat.row,path.S[i].seat.col);
????????i++;
????}
}
//輸出路徑
void?PrintPath2()
{
????for(int?i=0;i<ROW_NUM;i++)
????????for(int?j=0;j<COL_NUM;j++)
????????if(grid[i][j]==PATH)
????????????printf("(%d,%d)\n",i,j);
}
int?main()
{
????MazeType?path;
????PosType?start={0,0},end={6,12};
????if(MazePath(path,start,end))
????????PrintPath(path);
????else
????????printf("not?reachable!\n");
????PrintPath2();
}
總結
以上是生活随笔為你收集整理的Algorithm学习笔记 --- 迷宫问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java Apple_GitHub -
- 下一篇： C#中利用Linq.Dynamic实现简