华中科技大学《算法设计与分析》复习参考题

integer k,n; local X(1: n) k ← 1

while k>0 do

if还剩有没检验过的X(k)使得

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true then if ( X(1), ? ,X(k) ) 是一条抵达一答案节点的路径 then print ( X(1), ? ,X(k))

return endif

k ←k ＋ 1

else k ←k － 1 endif repeat

end BACKTRACK

算法6.2

procedure RBACKTRACK(k) global n, X(1:n)

for 满足下式的每个X(k)

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true do if ( X(1), ? ,X(k))是一条抵达一答案结点的路径 then print ( X(1), ? ,X(k))

return endif

call RBACKTRACK(k+1) repeat

end RBACKTRACK

50．在关于解空间树结构的术语中，什么是活结点？什么是E-结点？什么叫答案状态？什么是死结点？

51．什么是状态空间树？回溯法求解问题的过程中，状态空间树所有结点没有完全遍历到，但为什么能够得到所有的解？