問答題

【簡答題】請畫出用回溯法解釋皇后問題的解空間樹和搜索空間樹。

答案：

解空間樹：

用回溯法的搜索空間樹：

你可能感興趣的試題

【簡答題】
考慮使用動態(tài)規(guī)劃方法求解下列問題：
01背包數(shù)據(jù)如下表，求：能夠放入背包的最有價值的物品集合。

如設(shè)：V（i，j）——前i個物品中能夠裝入承重量j的背包中的最大總價值。請將如下遞推式填寫完整：

自底向上：按行或列填寫下表。

答案：

【計算題】考慮在序列A[1..n]中找最大最小元素的問題。一個分治算法描述如下：如果n≤2就直接求解。否則，將序列等分成兩個子序列A[1..n/2]和A[n/2+1..n]，分別找出這兩子序列的最大最小元素x1，y1和x2，y2；然后據(jù)此求出A[1..n]的最大元素x=max{x1，x2}及最小元素y=min{y1，y2}。請給出該算法計算時間T（n）滿足的遞歸方程，并解方程來確定算法的時間復(fù)雜度。假定n=2^k（k為正整數(shù)）。

答案：

算法時間復(fù)雜度滿足如下遞歸方程：