實驗7 蛇和梯子問題的算法設(shè)計與實現(xiàn)

1、實驗7蛇和梯子問題的算法設(shè)計與實現(xiàn)一、實驗?zāi)康?、掌握深度優(yōu)先和廣度優(yōu)先搜索算法的基本思想和設(shè)計方法；2、理解貪心算法的局限性；3、提高分析與解決問題的能力。二、實驗內(nèi)容【實驗題】“蛇和梯子”是一個在NXN （0N=20）的方格棋盤上進(jìn)行的游戲。（見下圖）方格從1到N的平方編號。除了第1號和最后編號的方格，其它的格子都有可能有蛇或梯子 存在（蛇和梯子的數(shù)量及具體位置由輸入確定，它們的數(shù)量都在100之內(nèi)并且蛇和梯子不能 臨近放置,也就是在任何了放置兩者首尾的方格之間至少還有一個未放置任何東西的格子）。 開始的時候玩家把他們的標(biāo)志物放在1號格子中。玩家輪流以扔骰子的方式移動他們的指示 物。如果一個

2、指示物到達(dá)了一條蛇的嘴部，則把它移回蛇的尾部。如果一個指示物到達(dá)了一 個梯子的底部則將它移動到梯子的頂部。如果你是一個可以自由控制骰子的高手，現(xiàn)在請求 出你至少需要扔幾次骰子才能到這標(biāo)為22的格子。（比如在上圖所示例一中，你的方案應(yīng) 該是走4步到達(dá)5并由梯子上升到16,再走4步到達(dá)20并由梯子上升到33,然后走3步。 這樣，你一共需要扔3次骰子。而在例二中，你的方案應(yīng)該是連扔4個6。）三、算法的原理方法從上面的實驗題中很容易看出，這個問題是不能用貪心算法解決的，因為你不能保證 在這步到達(dá)一個數(shù)碼比較大的格子就意味著最好的效率（即使是通過梯子到這了一個這步所 能到這的最大號碼的格子），也就是說，

3、號碼的大小并不能代表從這個格子到達(dá)終點(diǎn)所需要 的步數(shù)上的多少，這就帶給我們一個啟發(fā)：蛇和梯子真的需要看成是兩個東西來分別處理 么？實際上確實是不需要的，蛇和梯子的本質(zhì)就是我們經(jīng)常在游戲中說的“單向傳送點(diǎn)”， 只不過梯子的底部是入I I而頂部是出I I,蛇的嘴部是入I I而尾部是出I I罷了，對于他們的描 述完全可以選擇相同的結(jié)構(gòu)： struct SnakeAndLadderint from, to;；接下來要考慮的是解決問題的方法。貪心算法被否定之后，我們的選擇可能會是搜索， 對于本題所采用的搜索顯然應(yīng)該以廣度優(yōu)先的方式進(jìn)行，但是稍加分析我們就會發(fā)現(xiàn)如果單 純地采用廣度優(yōu)先搜索會產(chǎn)生許多重復(fù)的

4、結(jié)點(diǎn)，現(xiàn)在我們將指示物處于某格的結(jié)點(diǎn)簡稱為結(jié) 點(diǎn)X,那么比如在例1中，第1步過后，隊列中存放的結(jié)點(diǎn)是2, 23, 4, 16, 6, 7,在第二 步時，當(dāng)結(jié)點(diǎn)2成為擴(kuò)展結(jié)點(diǎn)時將生成結(jié)點(diǎn)23、4、16、6、7、8,其中只有8不存在于當(dāng) 前活結(jié)點(diǎn)隊列中，即使加以判斷，不把重復(fù)的結(jié)點(diǎn)再次加入隊列中，那至少也需要對活結(jié)點(diǎn) 隊列進(jìn)行搜索。實際上我們完全有更好的方法。應(yīng)該意識到，采用樹狀結(jié)構(gòu)和搜索的方法處理問題其重要的一點(diǎn)是利用祖先結(jié)點(diǎn)的差異 性來對兒子結(jié)點(diǎn)做不同的處理。然而在本實驗中，兒子結(jié)點(diǎn)的生成只依賴于父結(jié)點(diǎn)的信息而 與其它祖先結(jié)點(diǎn)無關(guān)，所以采用樹來描述這個過程其實是多余的。在走了若干步之后，對于

5、一個特定的格子實際上只有兩種狀態(tài)的區(qū)分：1、在走了這些步數(shù)之后存在一種方案使指示物位于此格中；2、不存在這樣的一種方案。所以我們可以用一個NXN大小的數(shù)組來描述若干步之后可以到達(dá)的格子的集合，其中 每一個元素描述一個格子的狀態(tài)，0表示不存在一種方案到達(dá)，1表示存在至少一種方案到 達(dá)。這樣，我們從表示第n步狀態(tài)的數(shù)組，完全可以推出表示第n+1步狀態(tài)的數(shù)組，而旦在 第n+1步狀態(tài)的數(shù)組得到之后，表示第n步狀態(tài)的數(shù)組也就不再存在利用價值了。一旦數(shù)組 中表示最后一個格子的元素成為1,就表示可以通過這個步數(shù)完成任務(wù)了。比如在例1中，描述棋盤狀態(tài)的數(shù)組其變化過程應(yīng)該為:描述狀態(tài)數(shù)組元素的內(nèi)容（從表示第1個

6、格的元素排列到表示最后一個格的元素）起始狀態(tài)100000000000000000000000000000000000第1步之后010101100000000100000010000000000000第2步之后000101111111100111101111111110001000第3步之后000001111111111111101111111111111101到第3步之后，數(shù)組的最后一個元素己經(jīng)變?yōu)榱?1,這即表明存在一種方案，使得我們?nèi)?次骰子就可以完成任務(wù)。以下是實現(xiàn)此算法的主要部分代碼，數(shù)組下.標(biāo)0一 size*size-l的元素分別表示了從第1格到最后一格的狀態(tài)，step記錄步數(shù)，ob

7、stacle是 struct SnakeAndLadder的向量，描述了蛇和梯子的傳送入I I和出I I:四、實驗程序的功能模塊typedef stmct snakeladder; /蛇與梯子的結(jié)構(gòu)void Slove();廣度優(yōu)先遍歷搜索最少步數(shù)五、詳細(xì)代碼#iiicludeusing namespace std;typedef stmct snakeladderint from;int to; snakeladder; /定義蛇與梯子的類型hit n,step,obNum;int grid1001;snakeladder obstacle1001;void Slove()int l,j,k

8、,test;int giidbak1001;for(j=2jn*nj-H-)gridj=O;gnd0=l;step=O;while(grid n*n-l =0)for(j=ljvn*n;j+)/而且在第n+1步狀態(tài)的數(shù)組得到之后，表示第n步狀態(tài)的數(shù)組 也就不再存在利用價值了(giidbakj=gridlj;coutgridbakj;)coutendl;Rr(J=Ojvn*n;j+)gridj=O;for(j=0jvn*n-lj+) 搜索所有的格子(最后一格不用搜索因為在過程結(jié)束前它一 定為0)(if(gndbakj=O) /若在上一步無法到達(dá)此格則跳出continue;for(k=l ;kn*

9、n-l)break:for(l=0;lobNum;l-H-) 如果此格是一個傳送入I I,將傳送出I I的格子可達(dá) if(o bstacle 1. fiom=j +k)gridobstaclel.to=l;test=l;break:1Jif(test=O & gridj+k=O) gndj+k=l;)step+; / 步數(shù)加一coutstependl;hitint snakeJadderJoca,value;mtij;while(cmn) 棋盤邊界obNum=0;cinsnakeladder; 蛇數(shù)，梯子數(shù)fbr(i=O;isnake;i+)(ciiilocavalue;/輸入蛇數(shù)據(jù)obsta

10、cleloca.fiom=loca;obstacle loca.to=value;obNum+;)fbr(j=0 j ladder;j+)(ciiilocavalue;/輸入梯子數(shù)據(jù)obstacleloca.fiom=loca;obstacle loca.to=value;obNum+;)Slove();return 0;六、提供測試數(shù)據(jù)和相應(yīng)的實驗結(jié)果6 1335 253 235 1620 3300000000000000000000000000000000000 11011100000000000000001000000000000 11011111111100000000001111111000000結(jié)臬3七、思考題1、試針對該問題，用深度優(yōu)先的方式求解，并分析求解時存在的問題。當(dāng)遍歷到傳送入II,直接從傳送出II繼續(xù)遍歷知道遍歷結(jié)束，否則回溯到Wlnle(jn*n-1) 只要未搜索到最后就繼續(xù)搜索for(k= l;k n*n-1) /完成遍歷break:test=