内容发布更新时间 : 2024/11/9 4:36:29星期一 下面是文章的全部内容请认真阅读。

/*更新经过的顶点*/

for(int j=1; j<=n; j++) next.visp[j]=tmp.visp[j]; next.visp[i]=1;

/*求目标函数*/ next.lb=get_lb(next);

/*如果大于上界就不加入队列*/ if(next.lb>up) continue; q.push(next); } } }

return ret; }

int main(){ }

in();

cout<

四、运行输出结果：

（1）蛮力法：

16

（2）动态规划法：

（3）回溯法：

（4）分支限界法：

五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： 1、首先是部分函数以及头文件的使用，在编写程序过程中经常会遇到需要使用自带或额外编写函数，经常需要查询相关资料。

2、代码运行时需要对oj上题目所要求的输入输出进行对应修改，否则会得到wrong answer。

3、由于算法的不同需要使用不同的数据结构进行存储，在数据结构的切换时会出现各种各样的问题，查询资料并逐步调试可以解决。

六、算法与代码的对应与解释（抽讲）

17

（1）蛮力法：

借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点到自身节点的距离为无穷大。在第一行找到最小项a[1][j]，从而跳转到第j行，再找到最小值a[j][k]，再到第k行进行查找……然后构造各行允许数组row[n]={1,1…1}，各列允许数组colable[n]={0,1,1….1}，其中1表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已经被访问。如果改行或该列不允许访问，跳过该点访问下一节点。程序再发问最后一个节点前，所访问的行中至少有1个允许访问的节点，依次访问这些节点找到最小的即可；在访问最后一个节点后，再次访问，会返回k=0，即实现访问源节点，得出一条简单回路。

（2）动态规划法：

假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。

推导：(分情况来讨论)

① 当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的 城市3->城市0(0为起点城市)。此时d(i, V’)=Cis(就是 城市i 到 城市s 的距离)、

②如果V’不为空，那么就是对子问题的最优求解。你必须在V’这个城市集合中，尝试每一个，并求出最优解。

d(i, V’)=min{Cik + d(k, V’-{k})}

注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。 （3）回溯法：

确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点即成为新的活结点，并为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

18

（4）分支限界法：

算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。

19