算法设计与分析回溯法提纲提纲骑士巡游问题青蛙换位问题骑士骑士巡游问题骑士巡游问题青蛙换位问题让左右两边的青蛙交换位置。通常IQ不低于50（即轻度智障者）的人，三分钟内可以完成。^_^提纲知识点知识点问题的解空间知识点回溯法的基本思想实例分析解空间为：{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}AAAAAAAAAAAAA如何避免回溯法的无效搜索回溯法的主要步骤知识点递归回溯知识点迭代回溯知识点两种类型的解空间树子集树搜索子集树的一般算法排列树搜索排列树的一般算法提纲实例分析旅行商问题旅行商问题（TSP问题）利用回溯法求解ＴＳＰ问题通过实例分析问题可能的周游路线回溯法的求解过程回溯法的求解过程剪枝函数的引入举例说明算法流程和复杂性分析常用的TSP问题求解方案符号三角形问题符号三角形问题算法设计算法实现&算法复杂性分析N皇后问题Ｎ皇后问题算法设计算法流程＊８皇后问题８皇后问题的１２个不同解其中一个可行解的图示最大团问题最大团问题实例说明算法设计图的ｍ着色问题问题描述可平面图4色猜想说明算法设计解空间的定义与组织X[1]=1递归回溯算法实现算法复杂性分析圆排列问题问题描述举例说明最优排列解空间的定义与组织算法设计算法实现算法实现算法复杂性分析电路板问题问题描述举例说明设x表示n块电路板的排列，即在机箱的第i个插槽插入电路板x[i].x所确定的电路板排列密度density(x)定义为跨越相邻电路板插槽的最大连线数算法中的参数说明算法设计算法实现&算法复杂性连续邮资问题问题描述分析如何确定最大连续邮资区间算法设计骑士巡游问题骑士巡游问题提纲回溯法的效率分析重排原理存在的困难用概率方法估计将产生的接点数publicintestimate(intn){intm=1,r=1,k=1;while(k<=n){T=x[k]的满足约束条件的可取值集合；if(T.size==0)returnm;r*=T.size;m+=r;x[k]=T.choose();k++;}returnm;}存在的问题提纲本章小结本章作业下一章内容