工业实验提交.pdfVIP

实验二有哪些信誉好的足球投注网站算法

⼀、实验⽬的

（1）掌握有哪些信誉好的足球投注网站算法的基本设计思想与方法，

（2）掌握分支界限有哪些信誉好的足球投注网站策略的设计思想与方法，

（3）熟练使用高级编程语言实现有哪些信誉好的足球投注网站算法，

（4）利用实验测试给出的有哪些信誉好的足球投注网站算法的性能。

二、实验内容

1.实验问题

（1）哈密顿环问题：输入是一个无向连通图G=(V,E)；如果G中存在哈密

顿环则输出该环，否则输出“否”。

（2）最小哈密顿环问题：输入是一个无向连通图G=(V,E)，每个节点都没

有到自身的边，每对节点间都有一条非负边；输出一个权值代价和最小的哈

密顿环。注意：事实上输入图是一个完全图，因此哈密顿环是一定存在的。

2.实验要求

2.1实现哈密顿环有哪些信誉好的足球投注网站算法

（1）哈密顿环问题：(a)实现基于树的基本有哪些信誉好的足球投注网站算法(BFS,DFS)(b)利用爬山

法的思想，考虑在有哪些信誉好的足球投注网站过程中如何选择节点进行展开有哪些信誉好的足球投注网站，设计并实现有哪些信誉好的足球投注网站的“个

性化”优化策略。

（2）最小哈密顿环问题：(a)实现求解最小哈密顿环问题的分支界限算法。

2.2测试算法性能

注意：在记录算法运行时间时，要去掉预处理以及后处理的时间，只记录对

-1-

比算法运行的时间。

（1）哈密顿环问题：随机生成大小分别为（8，10，12，14，16，18，20）

的输入图，记录算法运行时间并绘制性能曲线。注意：可以通过为每一对顶点抛

硬币的方法实现随机输入并控制边的比率。

（2）最小哈密顿环问题：随机生成大小分别为（8，10，12，14，16，18，

20）的输入图，记录算法运行时间并绘制性能曲线。注意：输入图是完全图，这

里的随机指的是边上权值的随机。

三、实验过程及结果

1．整体设计

1.1问题分析

（1）求解给出的无向图中是否存在哈密顿环

实验要求，需要随机生成大小分别为（8，10，12，14，16，18，20）的输

入图，因此，问题的一个输入数据即为无向图的顶点大小。输入顶点大小后，需

要根据边的比率设置边，在此我们设定另一输入数据：最大边数。实验过程中，

我们首先根据顶点数，随机生成n个顶点；再利用随机数，分别生成两个0~n-1

的数字，作为边的起点和终点，若起点和终点不相等（顶点到自身顶点不存在边），

则加入该边。生成无向图以后，再根据深度优先有哪些信誉好的足球投注网站策略，即可得出是否存在哈

密顿环。为了表达清楚是否存在，以及展示结果的合理性，需要给出无向图的绘

制，若存在哈密顿环，还需绘制出所求哈密顿环以供检验。

（2）求解完全无向图中的最小哈密顿环

由于完全无向图的边数由顶点数唯一确定，因此，无向图的规模由顶点数唯

一确定，只需要输入顶点数，即可计算出图形的边数，并利用随机算法生成图，

同时，需要利用随机算法给出每条边的权值，我们需要设置输入参数：最大权值，

令完全图中的每条边的权值在1~最大权值之间。将完全图绘制出来以后，利用

分支限界法计算出最短路径，并进行展示。

1.2数据结构

-2-