2009-2010.2《算法》-10回溯法学案.ppt

克服困难性;克服困难性;基于有哪些信誉好的足球投注网站剪枝技术;基于精确的概率概念;基于近似的解;回溯法;学习要点 理解回溯法的深度优先有哪些信誉好的足球投注网站策略。 思路：状态空间--- 穷举设计 求解过程--- 深度优先有哪些信誉好的足球投注网站+剪枝 通过应用范例学习回溯法的设计策略。 （1）图的3着色问题 （2）8皇后问题；;图的m着色问题;3着色问题：;3着色问题：;输入：无向图G=(V,E) 输出：G的顶点的3着色，其中每个c[j]为1，2，3 1. for k=1 to n 2. c[k]=0 3. end for 4. flag= flase 5. k=1 6. while k=1 7. while c[k]=2 8. c[k]=c[k]+1 9. if c 为合法着色 then set flag =true 且退出 10. else if c 是部分解 then k=k+1 {前进} 11. end while 12. c[k]=0 13. k=k-1 {回溯,就是剪枝} 14. end while 15. if flag then output c 16. else output “no solution”;解向量：(x1, x2, … , xn)表示顶点i所着颜色x[i] ，a[k][j]为图矩阵。可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。;8皇后问题;4皇后举例;8后问题;解向量：(x1, x2, … , xn) 显约束：xi=1,2, … ,n 隐约束： 1)不同列：xi?xj 2)不处于同一正、反对角线：|i-j|?|xi-xj|;有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是有哪些信誉好的足球投注网站，或是一种组织得井井有条的，能避免不必要有哪些信誉好的足球投注网站的穷举式有哪些信誉好的足球投注网站法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树。算法有哪些信誉好的足球投注网站至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的有哪些信誉好的足球投注网站，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略有哪些信誉好的足球投注网站。;问题的解空间;生成问题状态的基本方法;回溯法的基本思想;递归回溯;递归回溯;;输入：集合X1,X2,…Xn的清楚的或隐含的描述 输出：解向量v=(x1,x2,…,xi),0=i=n 1. v={} 2. flag= flase 3. k=1 4. while k=1 5. while Xk 没有被穷举 6. xk中的下一个元素；将xk 加入v 7. if v 为合法着色 then set flag =true 且退出 8. else if v 是部分解 then k=k+1 {前进} 9. end while 10. 重置Xk ，使得下一个元素排在第一位 11. k=k-1 {回溯,就是剪枝} 12. end while 13. if flag then output v 14. else output “no solution”