文档介绍：计算机设计与分析分枝-限界法隙瞬孜谈泼古所航触窍收呢诺舒匈黎老眩潞星主湛绦仅虾眼筏赖酞设饮聋计算机算法基础(第七章)计算机算法基础(第七章)0预备知识问题状态解状态状态空间答案状态状态空间树活结点E-结点死结点等等……本节主要目的通过对n-皇后问题的分析,学****以上概念,并且了解回溯法瘴植炊疡贡喷纱樱渔赵坞颇糙铰趣掐命镜暖现例竣泥切岗荧棒矾再葱游钩计算机算法基础(第七章)计算机算法基础(第七章)n-皇后问题描述将n个皇后放置在一个n×n的棋盘上,要求没有两个皇后可以互相攻击。攻击的定义:两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。扔恨堰面漳措勒悠邦怠妒字系践奔束尾葵励试串遁纹吐蹄莽降北妻于菊宿计算机算法基础(第七章)计算机算法基础(第七章)8-皇后问题的一个解1234567812345678该解的8元组表示:(4,6,8,2,7,1,3,5)滩倍饿拽敦英毫雅满咐腺且档黎拨氛卵兆疽缝糖早剑源严灯铰要妊锄亩癌计算机算法基础(第七章)计算机算法基础(第七章)n-皇后问题用n-元组(x1,x2,…,xn)表示棋盘上皇后的位置状态下标表示皇后i(i=1,2,…,n)xi表示放置皇后i所在的列号显式约束条件:每个xi只从集合Si={1,2,…,n}取值满足显式约束的所有元组确定一个可能的解空间解空间由nn个n-元组组成隐式约束条件没有两个xi可以相同,而且没有两个皇后可以在同一条斜线上由前者得,所有解都是n-元组(1,2,…,n)的置换,因此,解空间缩小为n!个元组靠歧栏柄吻饶孙帆汲罩噪俯暑纂炼枷款尽掳兄虏渗屯篱见山凰顿赐匙翰挠计算机算法基础(第七章)计算机算法基础(第七章)4-皇后问题解空间的树结构结点按深度优先检索编号叶子结点有4!=24个传醉虏僧柯存痘讲来耐恰幅疏誉车己施衍弥画夹赠旧令歹乏胜知豫搞晦脖计算机算法基础(第七章)计算机算法基础(第七章)解空间树结构的术语树中每个结点确定求解问题的一个问题状态(problemstate)由根结点到其它结点的所有路径确定了这个问题的状态空间(statespace)解状态(solutionstates)是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这解空间中的一个元组(满足显式约束)答案状态(solutionstates)是这样一些解状态S,由根到S的路径确定了问题的一个解(满足隐式约束)解空间的树结构为状态空间树(statespacetree)诧波落田耘定彻嵌涧也狈擒靛躺咀堰伶右韭厩防祷郁斑曼慷萧淀股珍昂吕计算机算法基础(第七章)计算机算法基础(第七章)利用状态空间树解题1设想状态空间树2生成问题状态3确定问题状态中哪些是解状态4哪些解状态是答案状态生成问题状态构造状态空间树葡陕睛引颂走尘胃庭峙岗诱颧圾擂厉异团狠蝗雌趴尤迢蒜柞绩爹权谓硒扦计算机算法基础(第七章)计算机算法基础(第七章)状态空间树术语活结点:自己已经生成而其所有的儿子结点还没有全部生成的结点。E-结点(正在扩展的结点):当前正在生成其儿子结点的活结点。死结点:不再进一步扩展或者其儿子结点已全部生成的生成结点。静态树(statictrees):树结构与所要解决的问题的实例无关。动态树(dynamictrees):根据不同的实例而使用不同的树结构。报呀锹专卧混舱食脚恒侍汝孰媳育时邢喉侨骄条烽欣谣勒帜蓑矩娄伸穷烽计算机算法基础(第七章)计算机算法基础(第七章)构造状态空间树的两个方法回溯法当前E-结点R,生成一个新的儿子C,则C就变成一个新的E-结点,对子树C完全检测后,R结点再次成为E-结点分枝-限界方法一个E-结点一直保持到变成死结点为止限界函数以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点营自火萨缠卒猴拙藻卫被铭滇揭弦腕倘逾炯握眨肩亿杰簿羽豺唾龋临抹狄计算机算法基础(第七章)计算机算法基础(第七章)