計算機(jī)算法設(shè)計及分析習(xí)題和答案解析(編輯修改稿)
2025-07-20 17:33 本頁面
【文章內(nèi)容簡介】 tn) output(x)。 else for (int i=t。i=n。i++) { swap(x[t], x[i])。 if (legal(t)) backtrack(t+1)。 swap(x[t], x[i])。 }} A.void backtrack (int t){ if (tn) output(x)。 else for (int i=0。i=1。i++) { x[t]=i。 if (legal(t)) backtrack(t+1)。 }} B. C.void backtrack (int t){ if (tn) output(x)。 else for (int i=0。i=1。i++) { x[t]=i。 if (legal(t)) backtrack(t1)。 }}void backtrack (int t){ if (tn) output(x)。 else for (int i=t。i=n。i++) { swap(x[t], x[i])。 if (legal(t)) backtrack(t+1)。 }} D.51. 常見的兩種分支限界法為（D）A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊列式（FIFO）分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法；二、填空題 時間 復(fù)雜性和 空間 復(fù)雜性之分。程序是 算法用某種程序設(shè)計語言的具體實現(xiàn)。算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。4. 矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。算法是指解決問題的 一種方法 或 一個過程 。從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是 遞歸算法 。問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 回溯法 。計算一個算法時間復(fù)雜度通?？梢杂嬎?循環(huán)次數(shù) 、 基本操作的頻率 或計算步。解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 動態(tài)規(guī)劃 ，需要排序的是 回溯法 ，分支限界法 。1使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時一般有兩個標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是 0/1背包問題 ，只使用約束條件進(jìn)行裁剪的是 N皇后問題 。1 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。1矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。 貪心選擇 性質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。15. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。，且要滿足輸入、 輸出 、確定性和 有限性 四條性質(zhì)。1大整數(shù)乘積算法是用 分治法 來設(shè)計的。1以廣度優(yōu)先或以最小耗費(fèi)方式搜索問題解的算法稱為 分支限界法 。1 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 分治策略 的一種排序算法。. 最優(yōu)子結(jié)構(gòu) 性質(zhì)和 重疊子問題 性質(zhì) 。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 隊列式（FIFO） 分支限界法和 優(yōu)先隊列式 分支限界法。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 。 規(guī)模 有關(guān)。 劃分的對稱性 。 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到 。 問題的最優(yōu)解包含了其子問題的最優(yōu)解 。 具有限界函數(shù)的深度優(yōu)先生成法 。在任何時刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為 O(h(n)) ）。 子集樹 算法框架與 排列樹 算法框架。，該問題的解空間結(jié)構(gòu)為 子集樹 結(jié)構(gòu)。，該問題的解空間結(jié)構(gòu)為 排列
語文相關(guān)推薦
鄂ICP備17016276號-1