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

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

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

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

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

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

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

7、stacle是 struct SnakeAndLadder的向量，描述了蛇和梯子的傳送入I I和出I I:四、實(shí)驗(yàn)程序的功能模塊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ù)組 也就不再存在利用價(jià)值了(giidbakj=gridlj;coutgridbakj;)coutendl;Rr(J=Ojvn*n;j+)gridj=O;for(j=0jvn*n-lj+) 搜索所有的格子(最后一格不用搜索因?yàn)樵谶^程結(jié)束前它一 定為0)(if(gndbakj=O) /若在上一步無法到達(dá)此格則跳出continue;for(k=l ;kn*

9、n-l)break:for(l=0;lobNum;l-H-) 如果此格是一個(gè)傳送入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)的實(shí)驗(yàn)結(jié)果6 1335 253 235 1620 3300000000000000000000000000000000000 11011100000000000000001000000000000 11011111111100000000001111111000000結(jié)臬3七、思考題1、試針對該問題，用深度優(yōu)先的方式求解，并分析求解時(shí)存在的問題。當(dāng)遍歷到傳送入II,直接從傳送出II繼續(xù)遍歷知道遍歷結(jié)束，否則回溯到Wlnle(jn*n-1) 只要未搜索到最后就繼續(xù)搜索for(k= l;k n*n-1) /完成遍歷break:test=