最短路径问题设计论文(编辑修改稿)

最短路径问题设计论文(编辑修改稿)内容摘要：

新 到 M y M a r k [ m * j + k ] 中j + +i + +结 束更 新 M y M a r k [ m * j + k ] 为 完 成 状 态M y M a r k [ m * j + k ] = 1更 新 M y M a r k [ m * j + k ] 为不 可 达 状 态M y M a r k [ m * j + k ] = 1YNYNNYYN 图 穷举法流程图 （最短距离） 穷举法分析 针对本最短路径问题， 穷举法 实现比较简单，但是时间复杂度和空间复杂度比较大， 空间复杂度为 O(n!) ，时间复杂度为 2O(n)。 在这里可以对算法进行如下改进： 设定一个变量 MinPrice=MAXSIZE 存储当前代价最小值， 首先判断 iv 到 jv 是否可以直接到达，可以则将其距离更新为最小代价值 MinPrice，在以后的遍历中，路径的代价如果大于 MinPrice 则设置其状态为不可到达；若路径已经完成，且代价小于 MinPrice，则 MinPrice 用现有完成路径代价替换。 回溯法 回溯法描述 回溯法（ Back Tracking Algorithm）是一种优选搜索法，按优选条件向前搜索，以达到目标。 为了实现回溯， 首先 需要为问题定义一个解空间， 这个解空间必须至少包含问题的一个解（可能是最优的）。 然后将所有的解组织在一起形成解空间，一般的解空间的组织方法是图或树。 最后在这个解空间的组织方法下可按照深度优先的方法从开始结点进行搜索。 在搜索过程中，探索到某一步时发现原先的选择并不是最优或者达不到目标，就会退一步重新选择，而在回溯法中，利用限界函数可以避免移动到不可能产生解的子空间以提高算法效率。 利用回溯法实现深度优先搜索。 深度优先搜索属于图算法的一种，英文缩写为 DFS即 Depth First 是对每一个可能的分支路径深入到不能再深入为止，而且每个 节点 只能访问一次。 回溯法 设计 针对 2 个顶点之间的最短路径 问题 使用回溯的方法解决，借用 深 度优先遍历的思想解决该问题 ， 设置标记变量 flag，如果标记变量为真 ， 则 打印结果，否 则此 2个顶点之间不可以到达。 其算法流程如图 所示，其算法步骤可以描述为如下： （ 1） 从文件中读取图的节点数目、读取节点数目 Npoint、起始点 Start、结束点 End、邻接矩阵 **WeightArry。 （ 2） 初 始化结果存储变量 result_old， = MAXSIZE， 设置标记 flag=0。 （ 3） 初始化临时存储变量 result_new， [*] = Start， 路径数目 = 1。 （ 4） 判断 = 1。 不满足，则执行（ 5）。 1） 获取满足相关条件的下一个下标 iPathEnd。 2） 判断 iPathEnd。 =Startamp。 amp。 约束条件。 不满足则转向 1），否则继续。 3） 判断 iPathEnd==End。 ， 是则更新 result_old = result_new； 将原来结果中的代价加上当前代价 ；将原来结果中的节点数加 1， falg=1；转向（ 4），否则执行下一步 4）。 4） 判断 iPathEnd != Start。 ， 满足则将当前路径信息添加到result_new中 ， ++， result_new的代价加上当前代价 ，转向（ 4）； 否则 继续 转向 5）。 5） 重置路径信息，回溯。 ， result_new的代价减去后 2个点之间的代价，返回（ 4）。 （ 5） 判断 flag==1。 ，不满足则转向（ 7）。 （ 6） 打印结果信息。 （ 7） 结束。 其中说明如下： （ 1） 步骤（ 4）的 2）中约束条件包括 ； 节点是否已经存在； 最小代价。 （ 2） result_new、 result_old均为 mark类型的结构体。 result_new存放满足条件的路径信息； result_old存放最终的结果。 （ 3） 在遍历的时候，首先将每一个节点初始化为 Start,依次循环增加，如果增加到 Start，则表示已经循环了一轮。 开 始读 取 节 点 数 目 N p o i n t 、起 始 点 S t a r t 、 结 束 点 E n d 、邻 接 矩 阵 * * W e i g h t A r r y初 始 化 结 果 存 储 变 量 r e s u l t _ o l dR e s u l t _ o l d . p r i c e = M A X S I Z E。 设 置 标 记 f l a g = 0初 始 化 临 时 存 储 变 量 r e s u l t _ n e wr e s u l t _ n e w . p a t h [ * ] = S t a r t路 径 数 目 R e s u l t _ n e w . n = 1r e s u l t _ n e w . n = 1。 获 取 第 r e s u l t _ n e w . n 条 路 径 的 下 标i P a t h E n di P a t h E n d。 = S t a r t amp。 amp。 约 束 条 件。 i P a t h E n d = = E n d。 r e s u l t _ o l d = r e s u l t _ n e w ；将 原 来 结 果 中 的 代 价 加 上 当 前 代 价 ；将 原 来 结 果 中 的 节 点 数 目 加 1F l a g = 1i P a t h E n d ! = S t a r t。 将 当 前 路 径 信 息 添 加 到 r e s u l t _ n e w 中 ，r e s u l t _ n e w . n + +。 r e s u l t _ n e w 的 代 价 加 上 当 前 代 价重 置 新 路 径 信 息 ， 并 回 溯r e s u l t _ n e w . n。 r e s u l t _ n e w 的 代 价 减 去 后 2 个 点 之 间 的代 价F l a g = = 1。 打 印 结 果结 束YNYNNYYN 图 回溯法流程图（最短距离） 回溯法分析 （ 1）解空间和状态空间数 假设输入的节点数为 4，起点为 2，终点为 1，则状态空间数如图 所示 ，其解空间为 {(2,3,0,1)， (2,3,1)， (2,1)，（ 2,0,1）， (2,0,3,1)}，有 5 种可能的解。 当输入规模为 n 时，有不超过 ( 1)!n 种可能的解。 23 1 00 11 03 00 31 33 1 图 n=4 时候的状态空间数 （ 2）搜索过程 从 上述解空间树的根结点开始。 开始时，根结点是唯一的活结点，也是当前扩展结点。 根据深度优先，逐层向下进行，直到该解向量为不可行解，然后回溯到该结点的父结点，再次进行搜索。 依此方法，可搜索整个解空间树。 搜索结束后，找到最短距离问题的最优解。 （ 3）搜索函数 Price(i)表示搜索到第 i层时的总代价， Path(i)表示搜索到第 i层时的节点编号。 Price(i)大于或等于当前存储的最小代价时停止搜索，转向右子数搜索；当 Path(i)等于无穷时，转向右子数搜索；当 Path(i)等于终点， Price(i)小于存储的最 小代价时，将现有路径信息更为最小路径信息，现有代价更新为最小代价，转向右子数搜索。 如果该节点只是一个中间节点，则将该节点与上一节点之间的代价加到 Price(i)中，将路径更新至 Path(i)中，继续向下搜索。 （ 4）复杂度分析 针对本最短路径问题，时间复杂度和空间复杂度 均比穷举法小 ，空间复杂度 为 O()n ，时间复杂度为 2O(n)。 贪心 法 贪心法描述 贪心法（ Greedy Algorithm）也称为贪 婪算法，是一种不要求最优解，只希望得到较为满意解的方法。 贪心方法常以当前情况为基础作最优选择，而不是考虑各种可能的整体情况，所以贪心方法不要回溯。 贪心法一般可以快速得到满意的解，但是由。