用回溯法求解一般哈密爾頓回路問題(已修改)
2025-01-21 18:57 本頁面
【正文】 1 用回溯法求解一般哈密爾頓回路問題 目 錄 引言 ........................................................ 1 1 需求分析 .................................................. 2 問題的提出 ........................................... 2 問題的描述 ........................................... 2 算法的描述 ........................................... 3 2 概要設(shè)計 ................................................. 4 系統(tǒng)運行環(huán)境 ......................................... 4 算法的實現(xiàn) ........................................... 4 接口設(shè)計 ............................................ 12 出錯處理設(shè)計 ........................................ 12 維護設(shè)計 ............................................ 13 3 詳細設(shè)計 ................................................. 14 算法的分析 .......................................... 14 程序的思路 .......................................... 15 程序的實現(xiàn) .......................................... 15 設(shè)計環(huán)境 ............................................ 19 4 調(diào)試分析 ................................................. 20 有哈密爾頓回路連通圖 ................................ 20 無哈密爾頓回路連通圖 ................................ 22 5 總結(jié) ..................................................... 23 參考文獻 ................................................... 25 附錄 ....................................................... 26 2 摘 要 回溯法是一種按照深度優(yōu)先的策略從根結(jié)點開始搜索解空間樹的算法，該算法 既帶有系統(tǒng)性又帶有跳躍性， 它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根節(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一節(jié)點時，總是先判定該節(jié)點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該節(jié)點為跟的子樹的系統(tǒng)搜索，逐層向其祖先節(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行探索。 這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法。 回溯法 可以用來求出問題的全部解，也可以在求出問題的一個解之后停止對問題 的求解，即只求該問題是否有解。 它適用于解一些組合數(shù)較大的問題。哈密爾頓回路 路就是判斷圖中是否存在一條通過所有頂點一次且僅一次的路徑。本文主要講的就是用回溯法來求解一個任意的圖中是否存在一條哈密頓通路的問題 ， 并用具體的算法來實現(xiàn)它。 關(guān)鍵詞 ： 回溯法 哈密爾頓回路 空間樹 1 用回溯法求解一般哈密爾頓回路問題 引言 回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹 [1]。算法搜索至解空間樹的任一 結(jié)點時， 總是先判斷該結(jié)點是否肯定不包含問題的解。 如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束 [2]。而 回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。 這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。 2 用回溯法求解一般哈密爾頓回路問題 1 需求分析 問題的提出 在求解一些問題（如走迷宮、地圖著色等問題）時，題目的要求可能是求出原問題的一種或所有可能的解決方案。這類 問題的解往往是由一個一個的步驟或狀態(tài)所構(gòu)成的，每一步驟又有若干種可能的決策方案；由于沒有固定、明確的數(shù)學(xué)解析方法，往往要采用搜索的做法，即從某一個初始狀態(tài)出發(fā)，不斷地向前（即下一個狀態(tài)）搜索，以期最終達到目標狀態(tài)，從而得到原問題的一個解或所有的解。在搜索的過程中，由于問題本身及所采取的搜索方法的特點（如在缺乏全局及足夠的前瞻信息的情況下進行搜索等） [3]，會導(dǎo)致走到某一狀態(tài)就走不下去的情況，這時，就必須回頭（即回到上一步，而不是回到最初的狀態(tài)），再嘗試其 他的可能性，換一個方向或方法再試試。這樣，不斷地向前 探索、回溯，再向前、再回溯，直至最終得出問題的解，或者一路回溯到出發(fā)點（出現(xiàn)這種情況即表示原問題無解）[4] 。注意，這種搜索過程并不是嘗試搜索問題解空間中所有的可能狀態(tài)和路徑，而是采用深度優(yōu)先的方式，沿著一條路徑，盡可能深入地向前探索。 問題的描述 1．設(shè)計內(nèi)容： 給出 內(nèi)存 分類法的多種應(yīng)用，給出這些應(yīng)用對應(yīng)的算法并編程實現(xiàn)。 2．設(shè)計要求： (1)給出各種分類法的求解算法 。 (2)編程實現(xiàn)各種分類法的算法 。 (3)對所寫的每個算法給出時空復(fù)雜性分析。 3 用回溯法求解一般哈密爾頓回路問題 算法的描述 該算法講的就是用回溯法求解 一個無向圖中是否存在哈密
試題試卷相關(guān)推薦
鄂ICP備17016276號-1