填空題

用回溯法解0/1背包問(wèn)題時(shí)，該問(wèn)題的解空間結(jié)構(gòu)為（）結(jié)構(gòu)。

答案：子集樹(shù)

你可能感興趣的試題

回溯法的算法框架按照問(wèn)題的解空間一般分為（）算法框架與（）算法框架。

答案：子集樹(shù)；排列樹(shù)

用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。在任何時(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))