首页计算机计算机基础计算机算法设计与分析 06 第8章 回溯.pptx

06 第8章 回溯.pptx

页数:47页文件大小:299.9 KB来源: 计算机算法设计与分析ppt课件

本课件讲解回溯法,从解空间的n-元组表示、显式与隐式约束出发,说明解空间树与状态空间树的术语和结点生成方式,给出BACKTRACK与RBACKTRACK的形式化描述、效率估计与蒙特卡罗方法,并以8-皇后问题完整演示限界函数与搜索过程。

第八章回溯法章节封面,标示本章主题为以深度优先方式搜索解空间的通用解题法
回溯法概念页,说明回溯是通用的解题法并以迷宫游戏类比深度优先搜索过程
解的形式说明页,给出n-元组表示与规范函数并说明硬性处理要构造全部元组逐一测试
查看本课件的文字版(共 47 页,供检索与复制)

第1页:第八章 回溯法章节封面

第八章回溯

第2页:什么是回溯法

入口8.1一般方法

  • 什么是回溯回溯
  • 迷宫游戏
  • 什么是回溯法
  • 回溯法是一种搜索算法
  • 通用的解题法
  • 回溯法是以深度优先的方式系统地搜索问题的解,它适用于解一些组合数较大的问题。
  • 寻求一组解,或求满足某些约束条件的最优解。回溯出口回溯回溯

第3页:解的形式与硬性处理

  • 解的形式n-元组(x1,…,xn),其中xi取自某个有穷集Si
  • 规范函数P(x1,…,xn)
  • 假设集合Si的大小是mi,满足规范函数P的可能的元组数为m=m1m2…mn
  • 硬性处理:构造m个n元组并依次测试是否满足P
  • 回溯法不断地用修改过的限界函数Pi(x1,…,xi)去测试正在构造的n元组的部分向量,看是否可能导致最优解,如果不能,就将可能要测试的mi+1… mn个向量略去。回溯法的基本概念

第4页:显式约束与隐式约束

  • 回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束
  • 显式约束条件:限定每个x只从一个给定的集合上取值,满足显式约束的所有元组确定一个可能的解空间例: xi≥0 , si={所有非负实数}
  • 隐式约束条件:描述了xi必须彼此相关的情况隐式约束条件指前面提到的规范函数
  • 解空间中满足隐式约束条件的元组称为可行解。回溯法的基本概念可能与问题实例有关,也可能无关。与问题实例有关

第5页:8-皇后问题描述

  • 在一个8*8棋盘上放8个皇后,使每两个皇后之间都不能互相“攻击”,即:使得每两个皇后都不能在同一行、同一列及同一条斜角线上。
  • 将皇后i放在行i上,8皇后问题可以表示为8-元组(x1,…x8),其中xi是皇后i被放置的列号。
  • 显式约束条件:Si={1, 2, 3, 4, 5, 6, 7,8}, 1≤i≤8
  • 隐式约束条件:没有两个xi可以相同,且没有两个皇后可以在同一条斜角线上。QQQQQQQQ解空间:88解空间:8!(4,6,8,2,7,1,3,5)例8.1(8-皇后问题)

第6页:子集和数问题实例

例8.2子集和数问题

  • 已知n+1个正数:wi, 1≤i≤n,和M。要求找出{wi}的所有子集使得子集中元素之和等于M。
  • 例如:n=4, (w1,w2,w3,w4)=(11,13,24,7),M=31。则满足要求的子集是(11,13,7)和(24,7)可表示为(1,2,4)和(3,4)

第7页:子集和数的k-元组表示

子集和数问题的描述

  • 解是k-元组(x1,…,xk),1≤k≤n
  • 显示约束条件xi∈{j|j是整数,wj的下标且1≤j≤n}
  • 隐式约束条件xi互不相同且相应的wk的和数是M,k=xi,xi<xi+1
  • (1, 2, 4)和(3, 4)

第8页:子集和数的另一种表示

子集和数问题的描述--另一种表示

  • 解是大小固定的n-元组(x1,…,xn),其中xi∈{0,1},1≤i≤n,若xi=0,解集合不包含wi;若xi=1,解集合包含wi;则例中的解可以表示为(1,1,0,1)和(0,0,1,1)

第9页:解空间的树结构

解空间的树结构

  • 搜索算法通过系统的检索给定问题的解空间来确定问题的解。解空间可以用树结构加以描述。
  • 对于一个给定的解空间,可能有多种树结构。

第10页:n-皇后问题

例8.3n-皇后问题

  • n-皇后问题是8-皇后问题的推广。n个皇后将被放置在n×n的棋盘上且使得没有两个皇后可以互相攻击。这是8-皇后问题的推广,其解空间由n-元组(1,2,…,n)的n!个排列所组成。
  • n=4时的树结构--排列树。树的边由xi的可能的取值标记。由i级到i+1级节点的边给出xi的值。解空间由从根节点到叶节点的所有路径定义。

第11页:4-皇后问题的解空间树

  • 145674334101112942421415161732322021222343432526272841143031323331133813341924291342183450342………
  • 4-皇后问题的解空间树x1=1x2=2

第12页:子集和数问题的解空间树

  • 12345678910111213141516x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4x4=4子集和数问题的解空间树1
  • 解空间树中的路径对应一个向量
  • 根结点到自身的空路径对应一个空向量( )
  • 树中红色的路径分别对应向量:(1, 2, 4)(2, 3, 4)(4)

第13页:子集和数的另一种解空间树

  • 17123456789101112131415161820232425192122262728293031x1=1x1=0x2=1x3=1101010x2=0x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=01010101010
  • 子集和数问题的解空间树2注:结点按D-检索方式编号从根结点到叶结点的一条路径确定解空间中的一个元组树中红色路径表示元组(1,1,0,1)

第14页:回溯法的搜索策略

回溯法在求问题的所有解时,要遍历树才能结束。

  • 回溯法在求问题的任一解时,只要搜索到问题的一个解就可以结束。
  • 回溯法在包含问题所有解的解空间树中,按深度优先的策略,从根结点出发搜索解空间树。
  • 回溯法搜索至解空间树的任一结点时,先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过以该结点为根的子树,逐层向其祖先结点回溯。否则就进入该子树,继续按深度优先的策略进行搜索。回溯法的基本概念

第15页:状态空间树的术语

解空间树(状态空间树)的术语

  • 问题状态(problem state):树中的每一个结点确定所求解问题的一个问题状态.
  • 状态空间(state space):由根结点到其他结点的所有路径确定了这个问题的状态空间.
  • 解状态(solution states):是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这个解空间中的一个元组.
  • 答案状态(answer states):是这样的一些解状态S,对于这些解状态而言,由根到S的这条路径确定了这问题的一个解.答案状态⊆解状态⊆问题状态(解空间树中的节点)

第16页:静态树与动态树

  • 静态树(static trees):树结构与所要解决问题的实例无关.
  • 动态树(dynamic trees):树结构是与实例相关的,且树结构是动态确定的.
  • 活结点:自己已经生成而其所有的儿子结点还没有全部生成的结点.
  • E-结点(正在扩展的结点):当前正在生成其儿子结点的活结点.
  • 死结点:不再进一步扩展或者其儿子结点已全部生成的生成结点.解空间树(状态空间树)的术语

第17页:问题状态的生成方法

问题状态的生成

  • 第一种状态生成方法:当前的E-结点R一旦生成一个新的儿子结点C,这个C结点就变成一个新的E-结点,当检测完了子树C后, R结点就再次成为E-结点,生成下一个儿子结点。(该方法也称为深度优先结点生成法)
  • 第二种状态生成方法:一个E-结点一直保持到变成死结点为止。它又分为两种方法:宽度优先生成方法(队列方法)和D-检索方法(栈方法)
  • 回溯法:加限界的深度优先生成方法称为回溯法
  • 第二种状态生成方法对应分枝-限界法

第18页:4-皇后回溯过程一

  • 结点2变成E-结点,它再生成结点3,路径变为(1, 2),即皇后1在第1列上,皇后2在第2列上,所以结点3被杀死,此时应回溯13x2= 22x1=1
  • 开始把根结点作为唯一的活结点,根结点就成为E-结点而且路径为( );接着生成儿子结点,假定按自然数递增的次序来生成儿子,那么结点2被生成,这条路径为(1),即把皇后1放在第1列上kill112例: 4-皇后问题

第19页:4-皇后回溯过程二

8x2= 3

  • 回溯到结点2生成结点8,路径变为(1, 3),则结点8成为E-结点,它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致答案的棋盘格局),所以结点8也被杀死,应回溯13x2= 22x1=1kill11x3=49x3=2112123killkill例: 4-皇后问题123

第20页:4-皇后回溯过程三

13x2= 415x4=3

  • 回溯到结点2生成结点13,路径变为(1, 4),结点13成为E-结点,由于它的儿子表示的是一些不可能导致答案结点的棋盘格局,因此结点13也被杀死,应回溯8x2= 313x2= 22x1=1kill11x3=49x3=2killkill14x3=2kill112123412316x3=3kill例: 4-皇后问题

第21页:4-皇后回溯过程四

  • 18x1= 213x2= 415x4=313x2= 22x1=1kill11x3=49x3=2killkill8x2= 314x3=2kill16x3=3kill
  • 结点2的所有儿子表示的都是不可能导致答案的棋盘格局,因此结点2也被杀死;再回溯到结点1生成结点18,路径变为(2)19x2= 124x2= 3killkill
  • 结点18的儿子结点19、结点24被杀死,应回溯例: 4-皇后问题11212

第22页:4-皇后回溯过程五

131x4=3

  • 结点18生成结点29,结点29成为E-结点,路径变为(2,4);18x1= 213x2= 415x4=313x2= 22x1=1kill11x3=49x3=2killkill8x2= 314x3=2kill16x3=3kill19x2= 124x2= 3killkill121231234
  • 结点29生成结点30,路径变为(2,4,1)
  • 结点30生成结点31,路径变为(2,4,1,3),找到一个4-皇后问题的可行解29x2= 430x3=1可行解

第23页:回溯算法的三个步骤

  • 1、针对所给问题定义问题的解空间,解空间应至少包含问题的一个最优解2、确定易于搜索的解空间结构3、以深度优先方式搜索解空间,并在搜索过程中使用限界函数避免无效搜索
  • 回溯算法的三个步骤

第24页:深度优先搜索的执行过程

从根结点出发,以深度优先方式搜索整个解空间。

  • 首先根结点成为一个活结点,同时也成为当前的扩展结点。在当前扩展结点处,搜索向纵深方向移至一个新结点,该新结点成为一个新的活结点,并成为当前扩展结点。
  • 如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时应回溯至最近的一个活结点处,并使该活结点成为当前的扩展结点。
  • 回溯法以这种方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。回溯法搜索过程

第25页:回溯算法的形式化描述

回溯算法的形式化描述

  • 假设回溯法要找出所有的答案结点
  • 设(x1,x2,…,xi-1)是状态空间树中由根到一个结点的路径,而T(x1,…xi-1)是下述所有结点xi的集合,它使得对于每一个xi,(x1,x2,…,xi)是一条由根到结点xi的路径;
  • 假定存在一些限界函数Bi,如果路径(x1,x2,…,xi)不可能延伸到一个答案结点,则Bi(x1,x2,…,xi)取假值,否则取真值。
  • 解向量X(1:n)中的第i个分量,就是那些选自集合T(x1,x2,…,xi-1)且使Bi为真的xi

第26页:BACKTRACK过程

回溯算法的形式化描述 procedure BACKTRACK(n)int k, n; local X(1: n);k←1; while (k>0) doif(还剩有没检验的X(k)使得X(k)∈T(X(1)…X(k-1)) andB(X(1)…X(k))=TRUE ) then if (X(1) …X(k))是一条抵达答案结点的路径) then print ( X(1)…X(k) ); endifk←k+1; else k←k-1; endif repeat end BACKTRACK//回溯//打印数组X//考虑下一个集合在X(1)…X(k-1)已经被确定的情况下,T(X(1)…X(k-1))给出X(k)的所有可能的取值,限界函数B(X(1)…X(k))判断哪些X(k)满足隐式约束条件

第27页:迭代回溯的执行示意

131513211981416 procedure BACKTRACK(n)int k, n local X(1: n)k←1 while (k>0) doif(还剩有没检验的X(k)使得X(k)∈T(X(1)…X(k-1))and B(X(1)…X(k))=TRUE) then if (X(1) …X(k))是一条抵达答案结点的路径) then print ( X(1)…X(k)) endifk←k+1 else k←k-1 endif repeat end BACKTRACKk=2k=3k=4若只需要一个解,怎样修改算法?

第28页:RBACKTRACK过程

procedure RBACKTRACK(k) global X(1:n);int k, n;for(满足下式的每个X(k),X(k)∈T(X(1)…X(k-1))and B(X(1),…B(k))=true)do{ if(X(1),…,X(k))是一条抵达答案结点的路径 then print (X(1)…X(k)); call RBACKTRACK(k+1);} end RBACKTRACK 回溯算法的递归描述进入算法时,解向量X中的前k-1个分量X(1) …X(k-1)已经被赋值对于所有可以由根结点到达,并可能使限界函数B为真的结点X(k),判断(X(1)…X(k))是否是一条能抵达答案结点的路径

第29页:回溯法的效率估计

效率估计

  • 回溯法的效率主要取决于四种因素:
  • 生成下一个X(k)的时间
  • 满足显示约束条件的X(k)的数目
  • 限界函数Bi的计算时间
  • 满足Bi的X(k)的数目
  • 限界函数:减少结点数,本身的计算时间生成节点的时间子节点的数量检验节点的时间通过检验的节点数量在计算时间和减少节点数量上进行折中

第30页:最坏情况时间复杂度

  • 一旦选定了一种状态空间树结构,前三种因素对于所要解决的实例没有多大的关系,只有第四种因素,对于问题的不同实例,生成的结点数是不相同的。
  • 易知,回溯算法最坏情况下的时间复杂度为O(p(n)2n)或O(q(n)n!),其中p(n)和q(n)为n的多项式。
  • 由于回溯法对同一问题不同实例在计算时间上出现巨大差异,在n很大时,对某些实例仍然十分有效。
  • 用回溯算法处理一棵树所要生成的节点数,可以用蒙特卡罗方法估算出来。效率估计

第31页:蒙特卡罗方法

效率估计---估计满足Bi的X(k)的数目

  • 蒙特卡罗方法
  • 在状态空间树中生成一条随机路径。
  • 设X是这条路径上第i级的一个结点。
  • 在结点X处用限界函数确定没受限界的儿子结点数目mi,在这mi个儿子结点中随机选择一个结点作为这条路径上的下一个结点。
  • 这条路径在以下结点处结束:或者它是一个叶子结点,或者该结点的所有儿子结点都已被限界。
  • 用这些mi可以估算出这棵状态空间树中不受限界结点的总数m。

第32页:蒙特卡罗方法的优缺点

效率估计---估计满足Bi的X(k)的数目

  • 蒙特卡罗方法
  • 优点:找到所有答案结点的情况非常有用,限界函数固定不变,计算方便,对状态空间树中同一级结点都适用。
  • 缺点:只求一个解时,生成的结点数远小于m,随着检索的进行,限界函数应该更强,使得m的值更小。

第33页:ESTIMATE过程

效率估计Procedure ESTIMATE//程序沿着状态空间树中一条随机路径产生这棵树中不受限界结点的估计数//m←1; r←1; k←1 loopTk←{X(k):X(k)∈T(X(1), …,X(k-1)) andBk(X(1), …,X(k-1))}ifSIZE(Tk)=0 then exit endifr←r×SIZE(Tk)m←m+rX(k)←CHOOSE(Tk)k←k+1 repeat return(m) end ESTIMATE//第k级的结点数//从Tk中随机地挑选一个元素//前第k级的结点总数返回集合Tk的大小

第34页:回溯法求解问题的基本步骤

回溯法求解问题的基本步骤

  • 为所求问题定义解空间,使其包含所有解;
  • 确定适于搜索的解空间结构;
  • 用深度优先方法搜索该解空间,在搜索过程中利用限界函数避免无效搜索。

第35页:8-皇后问题描述

8.2 8-皇后问题

  • 问题描述:在一个8*8棋盘上放置8个皇后,使得每两个皇后之间都不能互相“攻击”,即每两个皇后都不能在同一行、同一列及同一条斜角线上Q1Q2Q3Q4Q5Q6Q7Q8
  • 8皇后问题可以表示为8-元组(x1, …, x8) ,其中xi是放置皇后i所在的列号
  • 图中的可行解表示为一个8-元组即(4, 6, 8, 2, 7, 1, 3, 5)

第36页:棋盘的行列编号

a18a17a16a15a14a13a12a11a28a27a26a25a24a23a22a21a38a37a36a35a34a33a32a31a48a47a46a45a44a43a42a41a58a57a56a55a54a53a52a51a68a67a66a65a64a63A62a61a78a77a76a75a74a73a72a71a88a87a86a85a84a83a82a81用二维数组A(1:8,1:8)的下标来标记每个皇后的位置,那么可以看到:对于在由左到右的同一条斜角线上的每个元素具有相同的“行-列”值;

对于在由右到左的同一条斜角线上的每个元素则具有相同的“行+列”值设有两个皇后被放置在(i, j)和(k, l)位置上,那么当且仅当i-j = k-l或i+j = k+l时,它们才在同一条斜角线上。

将这两个等式分别变换成:j-l = i-k或j-l = k-i因此当且仅当|j-l| = |i-k|时(即两个皇后所在位置的行差距等于列差距时),两个皇后在同一条斜角线上

第37页:限界函数PLACE(k)

限界函数

  • PLACE(k)
  • 令X(k)与X(i)逐个比较,i=1..k-1。
  • 若存在X(k)=X(i)或者|X(i)-X(k)|=|i-k|
  • 则返回false;
  • 否则返回true。对X(k)的限定

第38页:PLACE过程

procedure PLACE(k)int i , k;i←1; while ( i<k ) doif(X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k)) then return (false); endifi←i+1; repeat return (true); end PLACE若一个皇后能放在第k行第X(k)列,则返回true,否则返回falseX是全程数组,进入此过程时已置入了k个值, ABS是绝对值函数能否放置一个新皇后的算法描述:注:两个皇后被放置在(i, j)和(k, l)位置上所以j=X(i),l=X(k),|j-l| = |i-k|即为ABS(X(i)-X(k))=ABS(i-k)//若两个皇后在同一列上,或在同一对角线上,则说明该位置不能放皇后,应返回false值

第39页:NQUEENS过程

求n-皇后问题的回溯算法描述 procedure NQUEENS(n)int k, n, X(1:n);X(1)←0 ; k←1; while (k>0) doX(k)←X(k)+1; while (X(k)≤nandNot PLACE(k)) doX(k)←X(k)+1; repeat if (X(k)≤n) then if (k=n) then print (X); else { k←k+1; X(k)←0; } endif elsek←k-1; endif repeat end NQUEENS//若是一个完整的解则打印数组X//k是当前行; X(k)是当前列//对所有的行执行循环语句//移到下一列当该位置不能放皇后时转到下一列//找到一个位置//否则转到下一行//没有合适的位置,回溯

第40页:NQUEENS执行过程一

43210X01Q1PLACE(1)i=1; while ( i<k ) do1<1 ,循环不执行 return (true);X(1)=0 ; k=1; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not true ,循环不执行 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=2; X(2)=0; }} end whilek=2; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not false ,X(k)=X(k)+1=2;2≤n and Not false ,X(k)=X(k)+1=3;3≤n and Not true ,循环不执行123 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=3; X(3)=0; }0} end whileQ2PLACE(2)i=1; while ( i<k ) doif(X(i)=X(k)) then return (false);PLACE(2)i=1; while ( i<k ) doif(|X(i)-X(k)|=|i-k|) then return (false);PLACE(2)i=1; while ( i<k ) do{ if(X(i)≠X(k) or|X(i)-X(k)|≠|i-k|) then不执行i=i+1=2;结束循环} return (true);

第41页:NQUEENS执行过程二

4321031XQ1Q2k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do if (X(k)≮n) then不执行 elsek=k-1=2;//回溯} end whilek=2; while (k>0) do{ X(k)=X(k)+1=3+1=4; while (X(k)≤n and Not PLACE(k)) do1≤n and Not false ,X(k)=X(k)+1=2;2≤n and Not false ,X(k)=X(k)+1=3;4≤n and Not true ,循环不执行 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=3; X(3)=0; }} end whileQ213≤n and Not false ,X(k)=X(k)+1=4;4≤n and Not false ,X(k)=X(k)+1=5;2345405≮n ,循环不执行

第42页:NQUEENS执行过程三

4321041XQ1Q2k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do if (X(k)<n) then if (k≠n) then不执行 else { k=k+1=4; X(4)=0;} end whilek=4; while (k>0) do{ X(k)=X(k)+1=1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not false ,X(k)=X(k)+1=2;2≤n and Not true ,循环不执行;} end whileQ2120Q31≤n and Not false ,X(k)=X(k)+1=2;1232≤n and Not true ,X(k)=X(k)+1=3;43≤n and Not true ,X(k)=X(k)+1=4;54≤n and Not true ,X(k)=X(k)+1=5;5≮n ,循环不执行 if (X(k)≮n) then不执行 elsek=k-1=3;//回溯

第43页:NQUEENS执行过程四

4321241XQ1k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do if (X(k)≮n) then不执行 elsek=k-1=2;//回溯} end whilek=2; while (k>0) do{ X(k)=X(k)+1=4+1=5; while (X(k)≤n and Not PLACE(k)) do} end whileQ23≤n and Not false ,X(k)=X(k)+1=4;4≤n and Not false ,X(k)=X(k)+1=5;3455≮n ,循环不执行55≮n ,循环不执行 if (X(k)≮n) then不执行 elsek=k-1=1;//回溯

第44页:NQUEENS执行过程五

43211XQ2k=1; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do} end whilek=2; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do2≤n and Not true ,循环不执行;1≤n and Not false ,X(k)=X(k)+1; if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=3; X(3)=0; }} end while if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=2; X(2)=0; }2≤n and Not false ,X(k)=X(k)+1;3≤n and Not false ,X(k)=X(k)+1;4≤n and Not true ,循环不执行;20Q1Q21234

第45页:NQUEENS执行过程六

4321042XQ1Q2k=3; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do} end whilek=4; while (k>0) do{ X(k)=X(k)+1; while (X(k)≤n and Not PLACE(k)) do1≤n and Not true ,循环不执行;3≤n and Not true ,循环不执行 if (X(k)≤n) then if (k=n) then print(2,4,1,3)} end whileQ21 if (X(k)≤n) then if (k≠n) then不执行 else { k=k+1=4; X(4)=0; }1≤n and Not false ,X(k)=X(k)+1;2≤n and Not false ,X(k)=X(k)+1;Q3Q43≤n and Not true ,循环不执行03

第46页:NQUEENS生成结点数的估算

估算NQUEENS所生成结点数

  • 硬性处理法:C(64,8)=4.4×109
  • NQUEENS(不考虑PlACK时)8!=40320
  • 估算节点数(蒙特卡罗方法)
  • 假设使用固定的限界函数且在检索进行时函数不改变。
  • 在状态空间树的同一级的所有节点都有相同的度。静态的状态空间树节点个数为:1+8+8*7+8*7*6+…+8*7*6*5*4*3*2*1=1+∑8*..*(8-j)=1+ ∑∏(8-i)=69281j=07j=07i=0j

第47页:蒙特卡罗估计结果

12345854321+8+8*5+8*5*4+8*5*4*3+8*5*4*3*2=164912345678642111=1401这5次试验的平均值是1625不受限节点的估计数大约是8-皇后状态空间树的节点总数的1625/69281=2.34%8-皇后问题的不受限节点的估计值

顶部目录