數據結構與算法：Python語言描述 棧和隊列

迷宮問題 迷宮問題的特點： 存在一集可能位置，一些位置相互連通，一步可達 一個位置可能連通若干位置，出現向前探查的多種可能(有分支) 目標是找到一條路徑(而不是找所有的能行路徑) 為了找到路徑，可能需要逐一探查不同的可能分支 工作中需要緩存信息：如果當前位置存在多個可能探查方向，由于下步只能探查一個，需要把不能立刻處理的方向記下來，后面可能使用 向前搜索也有一些不同方式，可以比較冒進，也可以穩扎穩打 如果搜索還沒找到出口，有一些可能做法。例如： 直到無路可走時才考慮其他選擇，換一條沒走過的路繼續 每步都從最早記錄的有選擇位置向前，檢查并保存另一個可達位置 無論如何，路徑搜索中必須記錄(緩存)有關信息，以供后面使用 迷宮問題 實現不同的路徑搜索過程，需要用不同緩存結構保存分支點信息 用棧保存和提供信息，實現的是回到之前最后選擇點繼續的過程 用隊列保存信息，就是總從最早遇到的選擇點繼續搜索 用棧保存信息，實際上是盡可能利用已經走過的路(改變最少) 下面先考慮實現這一過程的算法。算法里用一個棧保存分支點信息 用隊列方式記錄信息的可能性后面考慮 解決這個問題需要設計一種問題表示形式和一種確定可行方向的方式 注意：還要防止出現兜圈子的情況，為此需要記錄到過的位置 如果不記錄試探過的位置，在搜索通路的過程中就有可能重復探查某些局部路徑，即使出口是可達的，也永遠找不到 記錄了探查過的位置，在搜索中檢查，保證不重復探查任一位置 兩種記錄方式：1, 專門保存信息；2, 或直接記在“地圖” (迷宮圖) 上 迷宮問題 問題求解中的一項關鍵工作是選擇合適的問題表示。這里采用： 一個整數“矩陣”(兩層的 list)表示迷宮 入口和出口都用一對表下標表示(位置) 初始時，通路上的點用元素值為 0 表示，非通路點用 1 為避免無窮循環，搜索中把檢查過的點標記為2(記錄方法 2) 這樣，尚未考慮過的通行位置的值是 0，否則都是不需要進一步考慮的(或者根本不是通路，或者是已經探查過的位置) 每個位置有四個相鄰位置。為正確(且方便)地處理可能前進方向，要確定一種系統的檢查方法。我們把一個位置的四鄰看作“東南西北”四方位置，按這個順序逐方向處理 對單元 (i, j)，其相鄰的四個位置的數組元素下標如右圖所示 N (i-1,j) w (i,j-1) ? (i, j) E (i,j+1) S (i+1,j) 迷宮問題 用一個序對的 list 表示從任一 (i, j) 得到其四鄰位置應該加的數對： dirs = [(0,1), (1,0), (0,-1), (-1,0)] 對于當前位置 (i, j)，順序加 dirs[0], dirs[1], dirs[2], dirs[3]，就可以得到其東西南北的四個相鄰位置 這一設計使檢查當前位置四鄰的工作可以通過一個循環完成 先定義兩個簡單的輔助函數(設 pos 是形式為 (i, j) 的序對)： def mark(maze, pos): # 給迷宮 maze 的位置 pos 標 2 表示“到過” maze[pos[0]][pos[1]] = 2 def passable(maze, pos): # 檢查迷宮 maze 的位置 pos 是否可行 return maze[pos[0]][pos[1]] == 0 先考慮用遞歸方式寫出的算法，它比較簡單，不需要輔助數據結構 如前所述，為支持遞歸執行，語言系統內部實際上有一個運行棧。采用遞歸的方式描述迷宮搜索，也就是利用這個運行棧 迷宮的遞歸求解 前面提出了對迷宮求解問題的遞歸觀點，改寫如下： 每個時候總有一個當前位置，開始時這個位置是迷宮入口 如果當前位置就是出口，問題已解決 如果從當前位置已無路可走，當前的探查失敗 取一個與當前位置相鄰的可行位置用同樣方式探查，如果從那里有路徑通往出口，也就找到了從當前位置到出口的路徑 遞歸的迷宮求解算法是上述描述的實現，開始時把入口作為當前位置 mark 當前位置 檢查它是否出口，如果是則成功結束 逐個檢查當前位置的四鄰是否可以通到出口(遞歸) 成功時，整個求解也成功 失敗時放棄這個可能性 迷宮問題 遞歸實現的主函數如下： def find_path(maze, start, end): mark(maze, start); if start == end: # 已到達出口 print(start, end=" ") # 輸出這個位置 return True # 成功結束 for i in range(4): # 否則按四個方向順序探查 nextp = start[0]+dirs[i][0],

總結

以上是生活随笔為你收集整理的python中栈的描述是_数据结构与算法：Python语言描述 栈和队列.ppt的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。