算法作业、八章114s第七章

1.在下图中考虑哈密顿环问题。将问题的解空间表示成树，并分别利用深度优先搜索和广度优先搜索判定该图是否存在哈密顿环。1235467(1)深度优先搜中列出的树为深度搜索路径当深度优先所搜索搜索到目标节点时，证明图中存在哈密顿环，否则不存在。(2)广度优先搜索165434736274253543536374627271图中列出的树枝为广度搜索路径2.考虑8-魔方问题。分别用深度优先方法，广度优先方法，爬山法，最佳优先方法判定上图所示的初始格局能够通过一系列操作转换成目标格局，将搜索过程的主要步骤书写清楚。2184567321845673起始格局目标格局(1)广度优先搜索2184567321845673218456732184567321845673218456732184567321845673218456732184567321845673218456732184567321845673..................逐层搜索，直到目标格局出现为止(2)深度度优先搜索21845673218456732184567321845673...以某一条分枝为路径，深度优先搜索，如果该分支没有目标节点，则回溯到该分支的父亲节点继续沿该父亲节点的其他儿子节点深度优先搜索，直到搜索到目标格局为止。218456732184567321845673218456732184567321845673...(3)爬山法76564爬山策略使用贪心方法确定搜索的方向,使用启发式测度来排序节点扩展的顺序。依次搜索直到遇到目标格局。f(n)为当前位置错误数(4)最佳优先方法21845673218456732184567321845673218457321845673.........67564结合深度优先和广度优先的优点根据一个评价函数,在目前产生的所有节点中选择具有最小评价函数值的节点进行扩展.具有全局优化观念,而爬山策略仅具有局部优化观念,这里使用堆数据结构对数据进行存储，以便选择全局的最优解。3.分别用分支限界法和A*算法求出下图中从v0到T的最短路径，写出算法执行的主要过程。分支界限策略的原理:产生分支的机制,产生一个界限进行分支界限搜索,剪除不可能产生优化解的分支.256149774v0v12v11v23v21v22v21v23v22=14>13v1334v23v21v13167v33v31T3=13=135v34=17>13............产生分支的机制,产生一个界限进行分支界限搜索,剪除不可能产生优化解的分支,直到搜索完全部分支。A*算法代价函数对于任意节点ng(n)＝从树根到n的代价h*(n)＝从n到目标节点的优化路径的代价f*(n)＝g(n)+h*(n)是节点n的代价 h*(n)为n所有子节点中最小代价的值(1).使用Best-first策略搜索树;(2).节点n的代价函数为f(n)=g(n)+h(n),g(n)是从根到n的路径代价,h(n)是从n到某个目标节点的优化路径代价;(3).对于所有n,h(n)h*(n);(4).当选择到的节点是目标节点时,算法停止,返回一个优化解.A*算法的规则2561474v0v12v11v22v21v23v22v1334v23v21v13167v33v31A*算法执行过程31241067v23v219101312T151614v33v32v34511661115当选择到的节点是目标节点时,算法停止,返回一个优化解13114.在下面邻接矩阵给出的有向图上，用分支限界法求出代价最小的哈密顿环计算解的代价的下界把代价矩阵某行(列)的各元素减去同一个数,不影响优化解的求解.代价矩阵的每行(列)减去同一个数(该行或列的最小数),使得每行和每列至少有一个零,其余各元素非负.每行(列)减去的数的和即为解的下界.-5-7-8-10-6解代价下界=5+7+8+6+10=3602132430369165433286366136假设初始点为0412233636分支被剪掉分支被剪掉分支被剪掉分支被剪掉分支被剪掉分支界限搜索算法1.

建立根节点,其权值为解代价下界;2.使用爬山法,类似于拓朴排序序列树生成算法求解问题,每产生一个节点,其权值为加工后的代价矩阵对应元素加其父节点权值;3.一旦发现一个可能解,将其代价作为界限,循环地进行分支界限搜索:剪掉不能导致优化解的子解,使用爬山法继续扩展新增节点,直至发现优化解.

(1)深度优先法使用深度优先搜索整棵树，如果遇到某节点，使从根节点到该节点的和等于K输入，否则继续搜索。06764820820420813201127013134157136..............................最后得到S’为{4,6,8}(2)分支限界法使用分支界限法时，我们可以设定分支界限的界限为K，使用深度优先搜索树时，如果你当前节点的值大于K，则可以舍弃该分支，并继续搜索，如果遇到某节点，使从根节点到该节点的和等于K输入。06764820820420813201127013134157136.....................最后得到S’为{4,6,8}分支被剪掉分支被剪掉分支被剪掉6.精确描述求解8-魔方问题的A*算法，在习题2给出了起始格局和目标格局上给出A*算法操作的主要步骤2184567321845673起始格局目标格局对于任意格局ng(n)＝从树根到n的代价，即为当前格局下错误的格子数量h*(n)＝从n到目标格局的优化路径的代价f*(n)＝g(n)+h*(n)是格局n的代价h*(n)为n所有子格局中最小代价的值，即所有子格局最小错误的格子数量主要操作步骤:(1).使用最佳优先策略搜索树;(2).格局n的代价函数为f(n)=g(n)+h(n),g(n)是从根到n的路径代价,h(n)是从n到某个目标格局的优化路径代价;(3).对于所有n,h(n)h*(n);(4).当选择到的格局是目标格局时,算法停止,返回一个优化解.这里我们使用当前格局下错误的格子数量作为代价函数，即f(n)为当前格局下错误的格子数量，使用堆最为我们存储结构。A*算法执行过程218456732184567321845673218456732184567321845673...11149122