PTT數位生活區 / Python

[問題]使用遞迴解迷宮卻遇到stack overflow

看板Python作者 (property)時間7年前 (2018/04/28 10:40), 7年前編輯推噓7(7推 0噓 8→)
留言15則, 6人參與, 7年前最新討論串1/1
各位大大好 某份作業需要解迷宮 我參考了網路上的遞迴算法 但是卻總是遇到stack overflow 想給各位抓藥一下 其中 0 是可以走的路徑 如果確定是正確路徑我就標記 1 起點為矩陣ret[1][0] 終點為ret[99][100] https://imgur.com/LxVeeUY.jpg
terminal執行結果 https://imgur.com/inKi4aR.jpg
會stackoverflow我想是因為無法走到終止條件(?) 但是實在不知問題出在哪邊QAQ 第一次寫遞迴程式麻煩各位學長姐鞭小力一點嗚嗚 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.225.142.235 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1524883201.A.A7E.html
→
04/28 12:04, 7年前 , 1F
你先把走的路徑印出來看跟你想的一不一樣
04/28 12:04, 1F
→
04/28 12:05, 7年前 , 2F
然後先從小一點的試試看
04/28 12:05, 2F
推
04/28 16:01, 7年前 , 3F
你i,j都沒終止條件阿walk(ret,i,j+1) j會加到無限大
04/28 16:01, 3F
推
04/29 13:52, 7年前 , 4F
沒設邊界條件。
04/29 13:52, 4F
→
04/29 13:52, 7年前 , 5F
如果設了還是爆掉，就用dp或單源最短路徑試試。
04/29 13:52, 5F
推
04/29 19:27, 7年前 , 6F
最後一招就是改sys.setrecursionlimit()
04/29 19:27, 6F
感謝各位 我加入了邊界條件之後還是爆掉 我加入 if i<0 or i>100 or j<0 or j>100: return False 目前是想到還能用DFS 但也是需要用到遞迴 ※ 編輯: ar0n77777 (140.112.25.47), 04/30/2018 14:16:31
推
04/30 16:14, 7年前 , 7F
你把size先改成30以內看是否有結果
04/30 16:14, 7F
→
04/30 16:15, 7年前 , 8F
DFS可以用迴圈寫的 和BFS差別在容器是stack而非queue
04/30 16:15, 8F
推
04/30 16:20, 7年前 , 9F
文章中的寫法 一個點會被重複拜訪阿 2x2也會overflow
04/30 16:20, 9F
推
04/30 16:24, 7年前 , 10F
漏看line 7, 那麼就是改小size先確定這會動 再優化吧
04/30 16:24, 10F
推
05/04 17:43, 7年前 , 11F
因為你遞迴寫的方式會把整個MATRIX走滿 也就是100*10
05/04 17:43, 11F
→
05/04 17:45, 7年前 , 12F
0 在建立boundary情形下 先往j + 1走到底 j == 100
05/04 17:45, 12F
→
05/04 17:46, 7年前 , 13F
時又往下 i + 1下走 總而言之八成會繞完整個matrix
05/04 17:46, 13F
→
05/04 17:54, 7年前 , 14F
然後你not只用在一個條件下 估計走一走都是True
05/04 17:54, 14F
→
05/04 17:57, 7年前 , 15F
應該八成原本標記的1都會又會變成0
05/04 17:57, 15F
‣ 更多 ar0n77777 的文章
文章代碼(AID): #1Quzy1f- (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ar0n77777 的文章
文章代碼(AID): #1Quzy1f- (Python)