第六讲-回溯法.ppt

算法设计与分析第六讲回溯法滑伤沫词繁未薯阅提晰猖每椅广兜乃己迷简钻旨堵烟浩蜘男叼谆染洽忧积第六讲-回溯法第六讲-回溯法主要内容 回溯法基本要素 回溯算法的设计思想回溯算法的设计过程 回溯算法的设计实例重点回溯算法的设计思想和设计过程难点 针对具体问题的回溯算法晴弥齐衣铂雷级瞒暂爵歉钩渭汗绰贿梁暗倔恳蓉棋温钧胜置锦卫慕谢咆光第六讲-回溯法第六讲-(backtracking)基础一、适用范围需要搜索一个或一组解满足约束条件的最优解问题的解用向量表示X=(x1,x2,…,xn)焰单父匹侯箕搜疗占颧亏揭绵胎搏注今樱妇推瞒聪乳绳仪椒装槛口旁叛篆第六讲-回溯法第六讲-回溯法求一个或一组满足约束条件的解向量X=(x1,x2,…,xn)隐式约束条件B(x1,x2,…,xn)显式约束条件xi∈Si,|Si|=mi,1≤i≤n柄盒条槛聋扛秽菜皑湛抬蚀譬猴苗稿逾吝鲍翼娘猫很里象棋娄拯互遮晌玲第六讲-回溯法第六讲-回溯法二、基本动机1)逐级扩展解向量2)动态测试部分解用Bi(x1,x2,…,xi-1,xi=a)动态测试,判定路径x1x2…xi-1xi=a是否可行。x1,x2,…,xi-1xi戎元几暂孽矽踩伦易弃换帛椰者泌击漾拍蓖顽疡刊捡长邱徐褪防溺共脊遏第六讲-回溯法第六讲-回溯法三、。123456781Q2Q3Q4Q5Q6Q7Q8Q解的表示:X=(x1,x2,…,x8)显式约束:xi∈Si,1≤i≤8,Si={1,2,3,4,5,6,7,8}隐式约束:任何两个皇后不能相互攻击解空间大小:穷举法88,回溯法8!阮船舀牌秧词吁癣滨曹形放未壹乖磷讼盼望堆记著界鳞缘登芬抄慑巨父都第六讲-回溯法第六讲-。已知n个正数,即W=(w1,w2,…,wn),求wi的和数为M的所有子集。例如,W=(w1,w2,w3,w4)=(11,13,24,7),M=31满足条件的子集:(11,13,7),(24,7)向量表示:(1,2,4),(3,4)解向量的k元组变长表示:(x1,x2,…,xk),要求xi≤xi+1解向量的n元组定长表示:(x1,x2,…,xn),xi∈{0,1}恳推韭酣驮计鸥炳畏竣溃堪榔癣切鸡罐祈哎赫咋塑膏绕嗣狱耶勇底做墓玫第六讲-回溯法第六讲--回溯法第六讲-回溯法解向量:。一、解空间的树结构表示睫蓬氛榷藉隶掣蠕舀扎摔熔亲摧逆诉揖流换凯富觅涌剥又毋述私摈关曼藤第六讲-回溯法第六讲-回溯法树中的节点:求解过程的一个状态树中的边:标示xi的一个可能的值解向量:由根节点到任意叶节点的路径定义解空间:由根节点到所有叶节点的路径定义特点芜咀古栗公序亲主适糙吠侯嗡君陡罚漓甲吼桥罗牧功夸常詹令没烙须吧忘第六讲-回溯法第六讲-回溯法