页数:7页文件大小:51.4 KB来源: 计算机算法设计与分析ppt课件
本课件讲解第八章回溯法的课后习题,包括修改回溯过程使其只求一个解、给出回溯与递归回溯两种算法的伪代码,以及重新定义PLACE过程返回合法列号以提高N皇后问题求解效率的改写方法。
第八章1、3、4
P215-1修改算法6.1和6.2,使它们只求出问题的一个解而不是问题的全部解
算法6.1 procedure BACKTRACK(n) integer k,n; local X(1: n)k ← 1 while k>0 doif还剩有没检验过的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 endifk ←k+1 else k ←k-1 endif repeat end BACKTRACK
算法6.2 procedure RBACKTRACK(k) global n, X(1:n),flagfor满足下式的每个X(k)X(k)∈T ( X(1), … ,X(k-1)) and Bk( X(1), … ,X(k))= truedo if ( X(1), … ,X(k))是一条抵达一答案结点的路径 then print ( X(1), … ,X(k))flag←1 return endif call RBACKTRACK(k+1) if flag then exit repeat end RBACKTRACK
P196-3重新定义过程PLACE(k),使它的返回值或者是第k个皇后可以放置于其上的合法列号,或者是一个非法值,这样可以提高一些NQUEENS的效率,按以上策略重写这两个过程。
procedure PLACE(k) global X(1:k) ; integer i, ki ← 1 while i<k do if X(i) = X(k) or ABS( X(i)−X(k)) = ABS(i-k) then X(k) ←X(k)+1 if X(k)>n then return (-1) elsei ← 1 else i ←i + 1 endif repeat return (X(k)) end PLACE
procedure NQUEENS(k) integer k,n,X(1:n)X(1) ← 0; k←1 while k>0 doX(k) ← X(k)+1j←PLACE(k) if j>0 then if k=n then print(X) else k ← k+1;X(k) ← 0 endif else k ← k-1 endif repeat end NQUEENS
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}