3、边，再选第二条边，在不破坏旅游情况下选择最短的，一直到最后一条边。选择一些边，形成旅游，最后要形成圈才行。先选(c4,c5)，下一步选(c1,c2),(c2,c3),(c5,c6)三条边长相同，下一步选(c1,c3)不允许。只能选(c3,c4)，最后只能选(c1,c6)。得到货郎旅游为：C1,C2,C3,C4,C5,C6,C1§2.3动态规划技术(DYNAMICprogramming)动态规划技术应用广泛，有许多问题也设计动态规划算法，一定能寻找到最优解。遍历解空间中的所有解，从而找到所需要的或最优的。难理解把所有解一点一点构造出来，构造所有可能的解，其中包含最优解。是一种找到最优解的
4、方法，通过规划方法把所有可能解规划遍历出来。实际上要把问题实例的解一点一点组装起来，先组装规模小的实例的解，在逐渐增大实例规模，得到其解。例2.2A,B两组进行比赛，对于确定的n，哪组先胜n局则哪组获胜。A,B能力相当，一局取胜概率都为1/2。P(i,j):A组需要取胜i局才能获胜，B组需要取胜j局才能获胜，在这种情况下,最终导致A取胜的概率。如：n=4，A已经胜2局，B已经胜1局，则i=2,j=3，此时A取胜的概率为P(2,3)P(i,j)怎么计算？P(0,j>0)=1,P(i>0,0)=0。P(i-1,j)：A取胜一局后最终取胜的概率，P(i,j-1)：B取胜一局而A最终取胜的概率
5、。概率计算公式：P(i,j)=计算任意的P(i,j)，对任意的i和j时间复杂度是多少？列出递推关系,编递归程序实现的话可能比较危险，时间复杂度用下面方法分析。下面的递归算法容易给出：P(i,j)Ifi=0andj>0return1Ifi>0andj=0return0Ifi>0andj>0returni+j=n,求T(n)时间复杂度。T(1)=CT(n)=2T(n-1)+d,i+j=n可以得到T(n)=O(2n)，但是可以设计另一个算法.下面的表就是一个算法。99/12857/6431/321566/12842/6426/3215/161429/12822/6416/3211/167/8
6、137/646/325/161/23/4121/321/161/81/41/211000000543210iji+j=n，T(n)Cn2,T(n)=O(n2)动态规划的含义在哪里，后面的计算要用到前面的计算结果。必须存储中间结果，用到中间结果。一点一点算，从右下角往左上角依次计算。问题：货郎问题怎样设计动态规划算法？§2.4回溯技术：Backtracking一棵树从根开始，走遍所有节点，怎么走，要用到回溯技术，树搜索在智能系统中非常有用。每个问题都是树搜索。数据库删除记录就要用到回溯算法，研究生到现在为止尚未实现该程序。例子，两人x和o下棋的例子，分别以次往方格里面加入棋子，谁先
7、站满一行一列或一斜行(列)则取胜。目标是为了讲搜索和回溯。为了决定下一步怎么走，必须搜索以后的多种可能性，所以搜索每一种下法。为了让计算机知道什么叫好什么叫坏，给每个搜索节点设置一个估价函数。原则是对一方有利则数值越大，另一方有利则数值越小。通过一个例子讲回溯，搜索的好坏用得分表示。搜遍所有可能情况才知道哪个好哪个坏。(1)得分，-1(胜0负),0(平),1(0胜负)(2)最大最小，选择对自己最有利的策略(3)深度优先搜索，xxx000xx
