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