【正文】 ,5,3,5操作步驟：點擊“使用已有數(shù)組排序”顯示每一個的解答同預(yù)期N皇后詳細演示進入N皇后界面界面中測試數(shù)據(jù)：13操作步驟：點擊查看下一個具體解顯示每一步的解答同預(yù)期結(jié) 論 本次畢業(yè)設(shè)計的主要任務(wù)是基于Java語言開發(fā)的減治、動態(tài)規(guī)劃和回溯算法實驗演示程序設(shè)計與實現(xiàn)。測試用例知識學(xué)習(xí)功能的測試。知識學(xué)習(xí)的測試用例。測試項目用例編號輸入條件操作步驟與測試數(shù)據(jù)預(yù)期結(jié)果實際結(jié)果插入排序算法演示進入插入排序算法界面中測試數(shù)據(jù)：1,2,3，4,2,5,3,4,5,3,5操作步驟：點擊“使用已有數(shù)組排序”1 2 2 3 3 3 4 4 5 5 5同預(yù)期圖的深度優(yōu)先搜索算法演示進入圖的遍歷界面中測試數(shù)據(jù)頂點集合：v1,v2,v3,v4,v5,v6,v7,v8 邊集合： v1v2,v1v3,v2v4,v4v8,v8v5,v3v6,v6v7開始頂點：v1操作步驟：點擊“深度優(yōu)先”v1 v2 v4 v8 v5 v3 v6 v7 同預(yù)期圖的廣度優(yōu)先搜索算法演示進入圖的遍歷界面中測試數(shù)據(jù):頂點集合：v1,v2,v3,v4,v5,v6,v7,v8邊集合： v1v2,v1v3,v2v4,v4v8,v2v5,v3v6,v3v7 開始頂點：v1操作步驟：點擊“廣度優(yōu)先”v1v2v3 v4 v5v6 v7v8 同預(yù)期01背包算法演示進入01背包界面中測試數(shù)據(jù)物品：蘋果52400，三星33210，背包負重：20步驟：點擊“開始計算”三星3 蘋果5同預(yù)期二項式算法演示進入二項式界面中測試數(shù)據(jù)：N：8 k：5操作步驟：點擊“開始”56同預(yù)期N皇后算法演示進入N皇后界面界面中測試數(shù)據(jù)：13操作步驟：點擊計算總數(shù)73712同預(yù)期迷宮算法演示進入迷宮界面中測試數(shù)據(jù)：寬：14長：15操作步驟：點擊“生成迷宮”彈出迷宮圖解界面同預(yù)期(知識學(xué)習(xí))詳細說明環(huán)境要求硬件：PC機：一臺最低配置：可以穩(wěn)定運行Windows7(中文)操作系統(tǒng)硬盤可用存儲空間至少50MB軟件：操作系統(tǒng)：Windows7(中文)，屏幕分辨率在1024*768（含）以上預(yù)置條件測試環(huán)境已搭建、軟件可測試。測試用例算法演示功能的測試。 背景a. 系統(tǒng)名稱；減治、動態(tài)規(guī)劃和回溯算法實驗演示程序設(shè)計與實現(xiàn)b. 本項目提出者：邱建雄c. 開發(fā)者：陳鵬d. 用戶：算法初學(xué)者與算法愛好者e. 本軟件產(chǎn)品與其他有關(guān)軟件產(chǎn)品的關(guān)系：在myeclipse集成環(huán)境上進行開發(fā)和調(diào)試 定義測試用例：為某個特殊目標(biāo)而編制的一組測試輸入、執(zhí)行條件以及預(yù)期結(jié)果，以便測試某個程序路徑或核實是否滿足某個特定需求。預(yù)期輸入輸出的詳細說明有助于與開發(fā)人員的溝通，提高編寫符合要求的代碼。本文檔覆蓋了各個功能流程和預(yù)期的輸入輸出。完成編碼工作之后便可以按照本文檔進行測試。內(nèi)部接口：此模塊采用數(shù)據(jù)耦合方式，通過參數(shù)表傳送數(shù)據(jù)、交換信息。 接口用戶接口：本系統(tǒng)采用圖形接口。 功能 算法知識學(xué)習(xí)理解 輸入項在算法操作界面點擊“知識學(xué)習(xí)”按鈕 輸出項彈出一個新的窗口顯示該算法的學(xué)習(xí)知識內(nèi)容算法知識學(xué)習(xí)功能 知識學(xué)習(xí)時序圖7 模塊三（算法詳細演示模塊設(shè)計說明） 模塊描述此模塊提供了直接方便的圖形化界面作為用戶接口，通過此模塊用戶可以對減治算法演示、動態(tài)規(guī)劃演示、回溯算法演示進行操作，此模塊主要用于算法演示。 column[j] = rup[i+j] = lup[ij+n] = 1。 column[j] = rup[i+j] = lup[ij+n] = 0。amp。amp。 j = n。當(dāng)?shù)趎個皇后放置成功后，即得到一個可行解，此時再回到上一個皇后重新放置尋找下一個可行解...如此后，即可找出一個n皇后問題的所有可行解。如果不能，則跳到下一列...直到最后一列，如果最后一列也不能放置，則說明此時放置方法出錯，則回到上一個皇后向之前放置的下一列重新放置。 //當(dāng)前位置是否是出口 } if(當(dāng)前方塊的鄰接是否有路) findPath（鄰接方塊） else ()。amp。 //當(dāng)前方塊壓入棧 board[row][col].visit()。否則，找下一個可走的相鄰方塊，若不存在這樣的方塊，則退棧。 } }}二項式系數(shù)計算基本思想1）怎么描述問題，要把問題描述為交疊的子問題 2）交疊子問題的初始條件（邊界條件） 3）動態(tài)規(guī)劃在形式上往往表現(xiàn)為填矩陣的形式（在后面會看到，有的可以優(yōu)化空間復(fù)雜度，開一個數(shù)組即可，優(yōu)化也是根據(jù)遞推式的依賴形式的，后面有篇文章詳細說明） 4）填矩陣的方式（或者說順序）表明了什么？它表明了這個動態(tài)規(guī)劃從小到大產(chǎn)生的過程，專業(yè)點的說就是遞推式的依賴形式?jīng)Q定了填矩陣的順序。 } //若當(dāng)前物品數(shù)量小于可以放進去的數(shù)量，則將所有的該物品全部放進去 else if(num=當(dāng)前物品有的庫存) { (當(dāng)前物品，物品數(shù)量)。 //若當(dāng)前物品的數(shù)量大于可以放進去的數(shù)量則放入num個 else if(num當(dāng)前物品有的庫存) { (當(dāng)前物品，物品數(shù)量)。i) { //計算當(dāng)前物品可以放多少個 num = (int)(背包重量/當(dāng)前物品重量)。01背包問題輸入：物品名,物品數(shù)量，物品重量，物品價值,物品名,物品數(shù)量，物品重量，物品價值,...輸出：物品名物品數(shù)量，物品名物品數(shù)量，物品名物品數(shù)量，...偽代碼public void putBag(Goods[] goods){ for(int i=len1。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i1件物品的問題。用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。 j。amp。 j=i1。i。w = nextAdjVex(G,u,w)) if(!visited[w]) EnQueue(Q,w) } } }插入排序基本思想將n個元素的數(shù)列分為已有序和無序兩個部分，如下所示{{a1}，{a2，a3，a4，…，an}}，{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}…{{a1(n1），a2(n1) ，…},{an(n1)}}每次處理就是將無序數(shù)列的第一個元素與有序數(shù)列的元素從后往前逐個進行比較，找出插入位置，將該元素插入到有序數(shù)列的合適位置中。 for(w = firstadvex(G,v)。 visited[u] = true。v++) if(!visited[v]){ EnQueue(Q,v)。 for(v=0。v++) visited[v] = flase。輸出：將輸入的圖按照深度優(yōu)先遍歷的結(jié)果顯示偽代碼 void WFS(Graph G,Status(*Visit)(int v)){ //按廣度優(yōu)先非遞歸遍歷圖G for(v=0。即從v0開始，由近至遠，按層次依次訪問與v0有路徑相通且路徑長度分別為1，2，…的頂點，直至連通圖中所有頂點都被訪問一次。對于無向連通圖，廣度優(yōu)先搜索是從圖的某個頂點v0出發(fā)，在訪問v0之后，依次搜索訪問v0的各個未被訪問過的鄰接點w1，w2，…。 if(!visited[w]) DFS(g,W)。 w=0。 VisitFunc(v)。++v) if(!visited[v]) DFS(G,v)。 //訪問標(biāo)志數(shù)組初始化 for(v=0。v。 void DFSTraverse(Graph G,Status(* VisitFunc)(int v)){ //對圖G作深度優(yōu)先遍歷 VisitFunc = visit。輸出：將輸入的圖按照深度優(yōu)先遍歷的結(jié)果顯示偽代碼 Boolean visited[max]。假定給定圖G的初態(tài)是所有頂點均未被訪問過，在G中任選一個頂點i作為遍歷的初始點，則深度優(yōu)先搜索遞歸調(diào)用包含以下操作：（1）訪問搜索到的未被訪問的鄰接點；（2）將此頂點的visited數(shù)組元素值置1；（3）搜索該頂點的未被訪問的鄰接點，若該鄰接點存在，則從此鄰接點開始進行同樣的訪問和搜索。4. 如果軟件在運行中頻繁出錯，可通過升級本系統(tǒng)的版本來解決。2. 內(nèi)存不足導(dǎo)致系統(tǒng)崩潰無法運行時，應(yīng)適當(dāng)?shù)丶哟笙到y(tǒng)的使用內(nèi)存。 出錯信息表出錯或故障輸出信息形式含義處理方法無法響應(yīng)鼠標(biāo)無法點擊界面處理器對所讀數(shù)據(jù)未解讀關(guān)閉，重啟算法無法運行提示錯誤輸入數(shù)據(jù)不符合要求輸入合法信息無法計算結(jié)果提示內(nèi)存不夠輸入數(shù)據(jù)不符合要求輸入合法信息 補救措施說明故障出現(xiàn)后可能采取的變通措施。部分信息還可以指導(dǎo)用戶對出錯故障的情況進行有效地處理，例如當(dāng)用戶輸入的數(shù)據(jù)不符合要求時，提示用戶數(shù)據(jù)不符合要求。當(dāng)出現(xiàn)出錯或故障情況時，系統(tǒng)會輸出信息。圖形用戶接口元素包括窗口、圖標(biāo)、菜單和對話框，圖形用戶接口元素的基本操作包括菜單操作、窗口操作和對話框操作等。圖形用戶接口采用了圖形化的操作界面。N皇后詳細演示插入排序詳細演示N皇后知識學(xué)習(xí)迷宮知識學(xué)習(xí)二項式知識學(xué)習(xí)01背包知識學(xué)習(xí)插入排序知識學(xué)習(xí)減治算法演示動態(tài)規(guī)劃演示回溯算法演示圖的遍歷知識學(xué)習(xí)算法演示詳細演示知識學(xué)習(xí)算法演示與設(shè)計 總體結(jié)構(gòu)框架圖 功能需求與程序的關(guān)系本條用一張矩陣圖說明各項功能需求的實現(xiàn)同各模塊的分配關(guān)系。知識學(xué)習(xí)分為圖的遍歷知識學(xué)習(xí)、插入排序知識學(xué)習(xí)、二項式系數(shù)知識學(xué)習(xí)、01背包知識學(xué)習(xí)、迷宮知識學(xué)習(xí)、N皇后知識學(xué)習(xí)。詳細演示模塊在用戶對算法的運行結(jié)果存在不清楚，不明白是怎么得來的時候可以選擇查看單步詳細結(jié)果，這樣就可以幫助使用者更好的理解算法的過程 運行環(huán)境硬件環(huán)境：CPU：P4—1GHZ或更高內(nèi)存：128M或更多顯示器分辨率: 1200x800或更高軟件環(huán)境:操作系統(tǒng)：windows 7操作系統(tǒng) Java環(huán)境：JDK 分辨率：最佳效果1364*768像素運行工具：myeclipse 根據(jù)子系統(tǒng)劃分設(shè)計的原則，將系統(tǒng)劃分為算法演示、知識學(xué)習(xí)、詳細演示。算法演示模塊用戶可以對每個算法進行演示運行操作，幫助用戶對每一個算法進行深層次的理解與認識。Swing是JAVA基礎(chǔ)類的一部分。本文檔面向的主要讀者對象為程序的開發(fā)組，設(shè)計者，以及測試人員。對整個系統(tǒng)的細節(jié)進行進一步地細化工作，以求給與程序的開發(fā)者一個更加清晰的開發(fā)脈絡(luò)。該文檔是設(shè)計結(jié)果的詳細描述，也是程序員編寫程序功能的依據(jù)。4 運行環(huán)境規(guī)定 設(shè)備a. 處理器型號：b. 內(nèi)存容量：2G或以上c. 外存容量：10G以上d. 輸入設(shè)備：鍵盤、鼠標(biāo)e. 輸出設(shè)備：顯示器f. 運行軟件：myeclipse 支持軟件1) 操作系統(tǒng)：winwin8； 2) 開發(fā)軟件：myeclipse10；3) Java環(huán)境：JDK 減治、動態(tài)規(guī)劃和回溯算法實驗演示程序設(shè)計和實現(xiàn)軟件設(shè)計說明書編 制 陳鵬 審 核 邱建雄 批 準(zhǔn) 邱建雄 長沙學(xué)院二零一四年四月二十二日軟件設(shè)計說明書1 引言 編寫目的軟件設(shè)計的任務(wù)是從軟件需求規(guī)格說明書出發(fā)，根據(jù)需求分析階段確定的功能設(shè)計軟件系統(tǒng)的整體結(jié)構(gòu)、劃分功能模塊、確定每個模塊的實現(xiàn)算法以及編寫具體的代碼，形成軟件的具體設(shè)計方案。本系統(tǒng)相關(guān)文檔以及代碼注釋需詳細編寫，使后續(xù)維護和開發(fā)人員能快速理解軟件的結(jié)構(gòu)、接口、功能和內(nèi)部過程，是維護可行性增強。輸入錯誤數(shù)據(jù)時，系統(tǒng)不崩潰、不異常退出也不丟失數(shù)據(jù)。要求本系統(tǒng)能夠處理對系統(tǒng)失效的數(shù)據(jù)。系統(tǒng)使用相同術(shù)語、特性命名一致。一旦軟件崩潰、電腦死機等異常情況，要求文件數(shù)據(jù)不會丟失。如果在使用軟件過程中出錯而又未給出錯誤提示時，重新啟動本系統(tǒng)可解決程序出錯引起的故障。輸出要求：簡單、直觀，符合用戶的習(xí)慣，便于用戶閱讀、理解與使用，輸出操作方便。本系統(tǒng)應(yīng)盡量保持輸入輸出操作的方便，減少數(shù)據(jù)輸入輸出的內(nèi)容和工作量。本系統(tǒng)輸入輸出格式應(yīng)滿足可能使用人員的要求。采用可維護度高java面向?qū)ο笳Z言編碼，由于Java語言是跨平臺編程語言，所以適應(yīng)性較強。b) 處理時間：低于5秒。前置條件：用戶選擇算法操作界面后置條件：系統(tǒng)返回該算法的相關(guān)知識內(nèi)容活動步驟： 1. 用戶在菜單欄選擇自己想要操作的算法2. 系統(tǒng)返回該算法的