寫了一個迷宮程式，繼續加強中目前是兩種產生迷宮方式，用同一種求解法兩種迷宮都是單解迷宮，如例圖 圖1圖2圖片大小有點大請各位自行點開閱覽(尺寸大但容量小)，均為150x100的迷宮。我是故意把出口往左上移一格的，實際上可以自行設定入口與出口 圖1，使用成長法：設定一個點，使道路由該點逐漸延伸擴展。很明顯的看得出解答路徑很單純，完全是左上->右下的趨勢。創造這個迷宮花費約3秒。圖2，使用隨機法：隨機打掉牆，再利用集合的方式判斷打掉隨機牆後是否會成為多解迷宮，稍有變化，但創造此迷宮花費了30秒...。12/20更改：圖2的寫法有所更改，原先使用.Net framework類別庫的Collections.Generic.HashSet作牆的集合，從集合中隨機拿出一面牆判斷是否能打穿直到拿完所有的牆或是打穿N-1面牆(N為道路格子的數量)，12/20改成以Knuth Shuffle作一等於牆數長度的隨機不重複數列，再由數列逐一取出牆，判斷牆是否能打穿。只是做了個小小的更改，花費時間由原本近30秒變成了近1秒，速度快了30倍! 由此可知：眾多Collections固然好用，亦要對演算法下功夫。圖1為什麼會趨近於直線呢？這是由於成長法的關係：我在寫這個建立迷宮的方法時，並沒有決定任何方向趨向的機率，純粹交由亂數決定。由於亂數理論均勻，這會使得迷宮道路呈現"圓形擴散"，而圓心就是一開始設定的起始成長點。換句話說，單解迷宮事實上我們可以視它為一棵樹，起始成長點即為根，由於均勻擴散，使得迷宮深度(或說樹的高度)呈現均勻分布，且迷宮內每一點到與成長點的路徑長與兩點距離呈現高度正相關。接近成長點的點具有高的道路通率。(某點P通率=迷宮兩點路徑中經過P點的路徑數 / C(n,2) )。更換成長點可以看出端倪，最早我是取起點為成長起點，後來是隨機取一點為成長點、也就是圖1。現在我強制設定成長起點為最左下角的點，產生的結果如圖3各位客倌看出端倪沒有？由左上角起點進入迷宮後，要先做一次尋根之旅，再由根前往右下角的出口。 相對的，圖2就比較均勻，均勻不等於複雜或蜿蜒，事實上，複雜或蜿蜒才是一種不均勻的表現。不知道有沒有人對這方面有興趣的？下篇接迷宮程式(2) .msgcontent .wsharing ul li { text-indent: 0; } 分享 Facebook Plurk YAHOO! .
