1.题目:给出 Hamiltonian 算法中 NextNode 的实现。
解答:NextNode(k)是求 X[1..k-1]给定时 X[k]的可能取值,返回时 X[k]=0 表
示已无结点可分配给 X[k]
NextNode(k)
X[k]←(X[k]+1) mod (n+1) // 取下一个 X[k]值
while X[k]!= 0
do if Graph[X[k-1][X[k]]]>0 // 有边相连?
then for j←1 to k-1 // 检查是否与前面的边重复
do if X[j]=X[k] then break
if j=k // 不重复
then if k<n or (k=n and Graph[X[n],1]) return
X[k]←(X[k]+1) mod (n+1)
说明:对于同一个 k,不同次的调用应该返回不同的 X[k],这样才能使
Hamiltonian 算法中的第 2~6 行不至于死循环,初始时设 X[k]为 0,对
于给定 k,第一次调用返回 1..k 中第一个可用的 X[k],以后再调用就
返回下一个可用的 X[k]
2.题目:就下述实例用带限界函数的回溯法求解背包问题:
c=110, P=(11, 21, 31, 33, 43, 53, 55, 65),
W=(1, 11, 21, 23, 33, 43, 45, 55)
解答:生成树如下页图所示,圈内的数字分别代表重量和效益,圈外的数字
代表效益的上界,没写的与父结点相同。总共生成了 35 个结点,
A,B,C,D 为答案结点,终止时,fp=159 和 X=(1,1,1,0,1,1,0,0)。
3.题目:写出分支限界法求解装载问题的算法
解答:要写 LC 分支限界的算法首先要找合适的限界函数作为结点的优先级,
这个优先级在 ppt68 页上面说的很清楚,有了限界函数之后参考 LCBB
的一般算法或者背包问题的一般算法就可以写出装载问题的 LCBB 算
法。
其实这个问题可以看成是背包问题的特例,即每个物品的价值和重量
相等。