算法设计及分析实验指导书(2011)

实验(设计)报告参考格式

多段图问题的动态规划算法与实现

一、 设计目的

1. 掌握有向网的成本邻接矩阵表示法; 2. 掌握多段图问题的动态规划递推算法;

3. 进一步掌握动态规划法的基本思想和算法设计方法; ……

二、 设计内容

1. 任务描述

1)多段图问题简介 ……

2)设计任务简介

设计求解多段图问题的动态规划算法,即设计和实现多段图问题的表示方案、动态规划递推算法,设计对算法或程序的测试方案并完成测试。

2. 多段图问题的表示方案

本设计采用成本邻接矩阵表示多段图,针对多段图(可插入图例)描述成本邻接矩阵的规模与元素意义……

3. 递推过程的抽象描述

本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对多段图问题的求解(抽象地)描述递推过程……

4. 主要数据类型与变量

typedef NodeNumber int; /* 节点编号 */ typedef CostType int; /* 成本值类型 */

CostType cost[n][n]={…}; /* 成本邻接矩阵, n为顶点数 */ NodeNumber path[k]; /* k段图最短路径上的节点编号数组 */ NodeNumber cur= -1; /* 当前邻接节点 */

(必要时,可对数据类型和变量进一步解释或说明,增加可读性)

5. 算法或程序模块

int FindForward(CostType *cost[n], NodeNumber i, NodeNumber cur)

功能: 根据邻接矩阵查找节点i的下一个前向邻接节点, 成功时返回节点编号, 否则返

回-1; cur为当前的前向邻接节点, 第一次调用时其值为-1. int FindBackward(CostType *cost[n], NodeNumber i, NodeNumber cur)

功能: 根据邻接矩阵查找节点i的下一个后向邻接节点, 成功时返回节点编号, 否则返

回-1; cur为当前的后向邻接节点, 第一次调用时其值为-1.

(必要时,可对算法或程序模块进一步解释或说明,增加可读性)

三、 测试

1. 方案

描述测试方案、测试模块、测试数据实例(文字数据、图或表等形式)……

2. 结果

结合测试数据实例描述测试过程和测试结果,最好给出表示测试过程和结果的抓图,对测试结果进行分析并得出结论。

四、 总结与讨论

可针对本设计谈体会、谈改进、谈设想等,展示你的概括、归纳和创新思维能力,看重的不是你的对与错,而是鼓励你的想象和创新思维。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4