填空題用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h（n），則回溯法所需的計(jì)算空間通常為（）

您可能感興趣的試卷

你可能感興趣的試題

5.單項(xiàng)選擇題記號(hào)Ω的定義正確的是（）。

A.O（g（n））={f（n）∣存在正常數(shù)c和n0使得對(duì)所有n≧n0有：0≦f（n）≦cg（n）}
B.O（g（n））={f（n）∣存在正常數(shù)c和n0使得對(duì)所有n≧0有：0≦g（n）≦（n）}
C.O（g（n））={f（n）∣對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有n≧n0有：0≦f（n）<cg（n）}
D.O（g（n））={f（n）∣對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有n≧n0有：0≦cg（n）<f（n）}

最新試題

寫出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟。

題型：問答題

若n=4，在機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為ai和bi，且（a1，a2，a3，a4）=（4，5，12，10），（b1，b2，b3，b4）=（8，2，15，9）求4個(gè)作業(yè)的最優(yōu)調(diào)度方案，并計(jì)算最優(yōu)值。

題型：問答題

二分搜索算法是利用（）實(shí)現(xiàn)的算法。

題型：填空題

用分支限界法解裝載問題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。

題型：問答題

動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是（）和（）。

題型：填空題

已知非齊次遞歸方程：其中，b、c是常數(shù)，g（n）是n的某一個(gè)函數(shù)。則f（n）的非遞歸表達(dá)式為：現(xiàn)有Hanoi塔問題的遞歸方程為：，求h（n）的非遞歸表達(dá)式。

題型：問答題

何謂P、NP、NPC問題？

題型：問答題

設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： ①每個(gè)選手必須與其他n-1名選手比賽各一次； ②每個(gè)選手一天至多只能賽一次； ③循環(huán)賽要在最短時(shí)間內(nèi)完成。 （1）如果n=2k，循環(huán)賽最少需要進(jìn)行幾天； （2）當(dāng)n=23=8時(shí)，請(qǐng)畫出循環(huán)賽日程表。

題型：問答題

在進(jìn)行問題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問題所用的計(jì)算模型。3個(gè)基本計(jì)算模型是（）、（）、（）。

題型：填空題

算法就是一組有窮的（），它們規(guī)定了解決某一特定類型問題的（）。

題型：填空題