頁:
[1]
類似老鼠走迷宮:求 "最長" 路徑
本帖最後由 zxc456999 於 2017-4-9 07:57 PM 編輯請問有甚麼演算法可以使用嗎?還是有甚麼特殊解法呢?
因為迷宮小點還可以算得出來, 但大迷宮就無法了...
求大神解惑Orz
求從左上角到右下角的最長路徑
地圖可能長這樣
3X3
. . .
. . #
. . .
其中只有3個限制:
1.#不能走
2.不允許角落接觸
3.不允許邊緣接觸
<div></div> 本帖最後由 CoNsTaRwU 於 2017-4-8 05:00 PM 編輯
如果沒有規定曾經走過的地方能不能再被經過的話就無解了吧...
不過看你問這問題問得不清不楚的，自己都沒先想過，大概也沒什麼人想幫你
如果有限制同一個地方能經過幾遍的話，不就和找最短路徑一樣用 dfs 就解決了嗎... 本帖最後由 zxc456999 於 2017-4-8 09:07 PM 編輯
CoNsTaRwU 發表於 2017-4-8 04:45 PM static/image/common/back.gif
如果沒有規定曾經走過的地方能不能再被經過的話就無解了吧...
不過看你問這問題問得不清不楚的，自己都沒先 ...
抱歉, 資訊給太少了
但我想過了哦, 也寫出來了, 只是效率不盡理想
沒有限制同一個地方能經過幾遍, 單純的求從左上角到右下角的最長路徑
地圖可能長這樣
3X3
. . .
. . #
. . .
其中只有3個限制:
1.#不能走
2.不允許角落接觸
3.不允許邊緣接觸
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> zxc456999 發表於 2017-4-8 09:05 PM static/image/common/back.gif
抱歉, 資訊給太少了
但我想過了哦, 也寫出來了, 只是效率不盡理想
沒有限制同一個地方能經過幾遍, 單純的 ...
哦！！抱歉錯怪你了 qq
要是沒有規定同一個地方能經過幾遍的話，答案會是無限吧…
不過要是先假設只能走一遍的話，那標準的做法是用DFS(depth-first search, 深度優先搜索)來做
關於DFS可以參考這裡：http://www.csie.ntnu.edu.tw/~u91029/Graph.html
可以先看 graph traversal 那邊，然後再回去學 graph
有問題可以再來問喔...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> CoNsTaRwU 發表於 2017-4-9 05:17 PM static/image/common/back.gif
哦！！抱歉錯怪你了 qq
要是沒有規定同一個地方能經過幾遍的話，答案會是無限吧…
謝謝大大的回覆 :D
應該是找到解決辦法了~~<br><br><br><br><br><div></div>
頁:
[1]