一份优质的报告，需要以总结性的语录、合理的格式，进行工作与学习内容的记录。想必你也正在为如何写好报告而发愁吧？以下是小编精心整理的《遗传算法java实验报告》相关资料，欢迎阅读！
第一篇：遗传算法java实验报告
遗传算法求解TSP问题实验报告
人工智能实验报告
实验六
遗传算法实验II
一、实验目的：
熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。
二、实验原理：
旅行商问题，即TSP问题(Traveling
Salesman
Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表(在计算机里用二进制码表示)，从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。
三、实验内容：
1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。
2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。
3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。
4、上交源代码。
四、实验报告要求：
1、画出遗传算法求解TSP问题的流程图。
2、分析遗传算法求解不同规模的TSP问题的算法性能。
规模越大，算法的性能越差，所用时间越长。
3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。
(1)
种群规模对算法结果的影响
x
0
1.1
3.5
3
7
8
4
4.5
9
2
y
1.1
3
2
4
5.1
8
4
4.5
9
2
实验次数：10
最大迭代步数:100
交叉概率：0.85
变异概率：0.15
种群规模
平均适应度值
最优路径
10
25.264
4-5-8-7-6-3-1-0-9-2
20
26.3428
2-9-1-0-3-6-7-5-8-4
30
25.1652
1-3-6-7-5-8-4-2-9-0
50
25.1652
0-1-3-6-7-5-8-4-2-9
80
25.1652
9-0-1-3-6-7-5-8-4-2
100
25.1652
1-0-9-2-4-8-5-7-6-3
150
25.1652
5-8-4-2-9-0-1-3-6-7
200
25.1652
1-3-6-7-5-8-4-2-9-0
250
25.1652
3-1-0-9-2-4-8-5-7-6
300
25.1652
5-8-4-2-9-0-1-3-6-7
如表所示，显然最短路径为25.1652m,最优路径为1-0-9-1-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为10，20时，并没有找到最优解。因此并不是种群规模越小越好。
(2)
交叉概率对算法结果的影响
x
9
1.1
3.5
3.5
7
8
4
4.5
3
2
y
1.1
3
1
4
5.1
3
1
8.5
9
1
实验次数：15
种群规模：25
最大迭代步数:100
变异概率：0.15
实验结果：
交叉概率
最好适应度
最差适应度
平均适应度
最优解
0.001
28.0447
36.6567
32.6002
9-2-6-0-5-4-8-7-3-1
0.01
27.0935
34.9943
32.1495
7-8-3-1-9-2-6-0-5-4
0.1
28.0447
35.3033
31.9372
7-3-1-9-2-6-0-5-4-8
0.15
28.0447
34.1175
31.2183
0-5-4-8-7-3-1-9-2-6
0.2
28.7108
33.9512
30.9035
3-1-9-2-6-5-0-4-7-8
0.25
28.0447
35.1623
30.7456
1-3-7-8-4-5-0-6-2-9
0.3
27.0935
31.9941
29.9428
8-3-1-9-2-6-0-5-4-7
0.35
27.0935
32.8085
30.9945
9-1-3-8-7-4-5-0-6-2
0.4
27.0935
32.5313
30.1534
1-3-8-7-4-5-0-6-2-9
0.45
27.0935
33.2014
30.1757
8-3-1-9-2-6-0-5-4-7
0.5
28.0934
33.6307
30.9026
5-0-2-6-9-1-3-8-7-4
0.55
27.0935
33.5233
29.1304
1-9-2-6-0-5-4-7-8-3
0.6
27.0935
33.2512
30.7836
3-1-9-2-6-0-5-4-7-8
0.65
28.0447
33.7003
30.9371
5-4-8-7-3-1-9-2-6-0
0.7
27.0935
32.0927
29.9502
9-1-3-8-7-4-5-0-6-2
0.75
28.0447
32.4488
30.3699
0-5-4-8-7-3-1-9-2-6
0.8
27.0935
32.1551
29.9382
7-4-5-0-6-2-9-1-3-8
0.85
27.0935
34.5399
30.3594
5-0-6-2-9-1-3-8-7-4
0.9
27.0935
32.6273
30.69
6-0-5-4-7-8-3-1-9-2
0.95
27.0935
32.4672
29.919
6-2-9-1-3-8-7-4-5-0
(注:红色表示非最优解)
在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。
(3)
变异概率对算法结果的影响
x
9
1.1
3.5
3.5
7
8
4
4.5
3
2
y
1.1
3
1
4
5.1
3
1
8.5
9
1
实验次数：10
种群规模：25
最大迭代步数:100
交叉概率：0.85
实验结果：
变异概率
最好适应度
最差适应度
平均适应度
最优解
0.001
29.4717
34.732
32.4911
0-6-2-1-9-3-8-7-4-5
0.01
29.0446
34.6591
32.3714
8-4-5-0-2-6-9-1-3-7
0.1
28.0934
34.011
30.9417
5-0-2-6-9-1-3-8-7-4
0.15
27.0935
32.093
30.2568
6-0-5-4-7-8-3-1-9-2
0.2
27.0935
32.2349
30.3144
8-7-4-5-0-6-2-9-1-3
0.25
27.0935
32.718
30.1572
4-5-0-6-2-9-1-3-8-7
0.3
27.0935
32.4488
30.2854
0-5-4-7-8-3-1-9-2-6
0.35
27.0935
33.3167
30.7748
1-3-8-7-4-5-0-6-2-9
0.4
29.0446
34.3705
31.3041
2-0-5-4-8-7-3-1-9-6
0.45
27.0935
31.374
29.6816
2-6-0-5-4-7-8-3-1-9
0.5
27.0935
32.3752
30.2211
2-9-1-3-8-7-4-5-0-6
0.55
27.0935
33.3819
30.6623
1-3-8-7-4-5-0-6-2-9
0.6
28.0934
33.2512
30.36
1-3-8-7-4-5-0-2-6-9
0.65
27.0935
32.7491
30.0201
3-1-9-2-6-0-5-4-7-8
0.7
28.7108
32.4238
30.785
1-3-8-7-4-0-5-6-2-9
0.75
27.0935
31.8928
30.2451
1-9-2-6-0-5-4-7-8-3
0.8
28.0934
31.6135
30.3471
9-1-3-8-7-4-5-0-2-6
0.85
29.662
33.2392
31.1585
2-9-1-3-7-8-4-0-5-6
0.9
28.0447
32.0387
30.4152
0-5-4-8-7-3-1-9-2-6
0.95
28.0447
31.3036
30.0067
9-1-3-7-8-4-5-0-6-2
从该表可知，当变异概率过大或过低都将导致无法得到最优解。
4、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。
不同变异策略和不同个体选择分配策略几乎不影响算法运行的时间，但会影响适应度。
五、实验心得与体会
通过本实验，更加深入体会了参数设置对算法结果的影响。同一个算法，参数值不同，获得的结果可能会完全不同。
同时通过本次实验，使自己对遗传算法有了更进一步的了解。遗传算法是一种智能优化算法，它能较好的近似求解TSP问题，在问题规模比较大的时候，遗传算法的优势就明显体现出来，当然不能完全保证能得到最优解。
第二篇：算法实验报告
《算法设计与分析》
实验报告
班级
姓名
学号
年
月
日
目录
实验一
二分查找程序实现…………………………………………………………………03页
实验二
棋盘覆盖问题(分治法).…………………………………………………………08页
实验三
0-1背包问题的动态规划算法设计……………………………………………….11页
实验四
背包问题的贪心算法………………………………………………………………14页
实验五
最小重量机器设计问题(回溯法)………………………………………………17页
实验六
最小重量机器设计问题(分支限界法)…………………………………………20页
1
指导教师对实验报告的评语
成绩：
指导教师签字：
年
月
日
2
实验一：二分查找程序实现
一、实验时间：2013年10月8日，星期二，第
一、二节地点：J13#328
二、实验目的及要求
目的：
建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。 要求：
1、用c/c++语言实现二分搜索算法。
2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。
三、实验环境
平台：Win7 32位操作系统 开发工具：Codeblocks10.05
四、实验内容
对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素x。
五、算法描述及实验步骤
算法描述：
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。 确定算法复杂度基本步骤：
1、首先设定问题规模n;
2、随即产生递增数列;
3、在n个有序数中随机取一个作为待查找量，搜索之;
4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次;
5、改变问题规模n重复上述步骤2~4，n取100、200……1000;
6、依实验数据作图，并与理论图作比较;
7、二分搜索算法平均查找次数： 问题规模为n时，平均查找次数为： A(n)=Int(logn) + 1/2 // Int() 函数为向下取整
3
即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。
实验步骤：
1.初始化生成递增随机数列： for ( int j=100; j <=1000; j+=100 ) {
array[0]=10+rand()%15;
for(int i=1; i
array[i]=array[i-1]+1+rand()%3+rand()%10;
} } 2. 定义二分查找算法：
int BinarySearch( const int b[], int searchKey, int low, int high ); 其中，返回值为int类型，数组b[]为待查递增序列，searchKey为所查数据，low为数组b[]左下标，hight为数组b[]右下标。 该算法实现过程为：
将数组b[]的n个元素分成个数大致相同的两半，取b[n/2]与searchKey作比较。如果searchKey=b[n/2]，则找到searchKey，算法终止;如果searchKeyb[n/2]，则只要在数组b的右半部继续搜索searchKey。
3.实现主函数并完成所有代码。 4.算法复杂性分析：
容易看出，没执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。
六、调试过程及实验结果
输出结果为：
4
Every array repeat search times: 10 Number of Elements
理论平均查找次数
实际平均查找次数
5
100
6.5
6.1
200
7.5
7.3
300
8.5
7.4
400
8.5
7.4
500
8.5
7.5
600
9.5
8.2
700
9.5
8.8
800
9 .5
8.7
900
9.5
8.8
1000
9.5
9.4
七、总结
二分查找在搜索有序表时，效率比较高。通过这次实验我对二分查找算法的认识又有了新的提高。本想写个图形界面，但由于种种原因，没有实现，下次做加密算法时，要写一个图形化界面。
6
指导教师对实验报告的评语
成绩：
指导教师签字：
年
月
日
7
实验二：分治法解决棋盘问题
一、实验时间：2013年10月22日，星期二，第
一、二节地点：J13#328
二、实验目的及要求
1、
用c/c++语言实现分治法解决棋盘问题算法。
2、
实现棋盘化以及棋盘覆盖
三、实验环境
Windows 2007 操作系统
以及code blocks软件
四、实验内容
在一个2^k*2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。
五、算法描述及实验步骤 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘(若不存在特殊方格)----则将该子棋盘右下角的那个方格假设为特殊方格 右上的子棋盘(若不存在特殊方格)----则将该子棋盘左下角的那个方格假设为特殊方格 左下的子棋盘(若不存在特殊方格)----则将该子棋盘右上角的那个方格假设为特殊方格 右下的子棋盘(若不存在特殊方格)----则将该子棋盘左上角的那个方格假设为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
六、调试过程及实验结果
8
七、总结
由于覆盖一个2k*2k棋盘所需的L型骨牌个数为(4k-1)/3，故此算法是一个在渐近意义下最优的算法。
9
指导教师对实验报告的评语
成绩：
指导教师签字：
年
月
日
10
实验三：0-1背包问题的动态规划算法设计
一、实验目的及要求
1.了解并掌握动态规划算法的设计思想。
2.利用动态规划算法的设计思想实现0-1背包问题的算法设计。
二、实验环境
使用C++语言;
在windows环境下使用CodeBlocks调试并运行。
三、实验内容
1.了解并掌握动态规划的设计思想。
2.利用动态规划算法的思想解决0-1背包问题。
四、算法描述及实验步骤
每种物品一件，可以选择放1或不放0。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略(放或不放)，那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v];如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
五、调试过程及实验结果
11
六、总结
0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。通过这次实验我对动态规划算法的认识又有了新的提高。
12
指导教师对实验报告的评语
成绩：
指导教师签字：
年
月
日
13
实验四：背包问题的贪心算法
一、 实验目的：
运用贪心算法思想，设计解决上述问题的算法，找出最大背包价值的装法。
二、实验要求
1. 用c++语言实现背包问题的贪心算法。
2.掌握贪心思想的应用。
三、实验原理
在贪心算法中采用逐步构造最优解的办法，在每个阶段，都做出一个看上去最优的决策(在一定的标准下 )，决策一旦做出就不可更改。
四、实验过程(步骤) 1. 定义背包结构体： struct stone { int name; int weight;//物品的剩余重量
int weight_t;//物品的重量
float benefit;//物品的价值
//float b; }; 2. 定义函数void sort(stone *data,int num) //计算物品的单位重量的价值，并进行排序 3. 定义主函数并完成贪心选择。 4.分析算法复杂性分析：
该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O(n*logn)。
与0-1背包问题类似，所不同的是在选择物品i装入背包时 ，可以选择物品i的一部分，可以选择物品i 可以选择物品 的一部分，而不一定要全部装入背包， 1≤i≤n。 这2类问题都具有最优子结构 ，最优子结构性质，极为相似，但 最优子结构 背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
五、运行结果
14
六、实验分析与讨论 贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题：
1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题;
3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程：
1.Begin 从问题的某一初始解出发; 2.while 能朝给定总目标前进一步 do 3.求出可行解的一个解元素;
4.由所有解元素组合成问题的一个可行解
七、实验心得
贪心算法通过一系列的选择来得知问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。通过背包问题的解决，进一步掌握了贪心算法的思想，并能在解问题时灵活运用。
15
指导教师对实验报告的评语
成绩：
指导教师签字：
年
月
日
16
实验五：最小重量机器设计问题(回溯法)
一、 实验目的
建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。
二、
实验要求
1、
用c++语言实现最小重量机器设计的回溯算法。
2、
分析算法的计算复杂性
三、
实验原理
首先，应该明确的确定问题的解空间。确定了解空间的组织结构后，发从开始节点(根节点)出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，向纵深方向搜索移至一个新的结点。这个新结点成为新的活结点，并成为新的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点成为死结点。此时，应往回移动(回溯)至最近的活结点，并使这个活结点成为当前的扩展结点。回溯以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。
四、 实验过程(步骤) 由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的sum小，如果小就赋给sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的sum即为最优解。
数据说明：
N：零件数量
m：不同的零件商
W[][]:是从供应商j处购得的部件i的重量
c[][]：相应的价值 算法设计：
a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。
b.用递归函数backtrack(i)来实现回溯法搜索排列树(形式参数i表示递归深度)。
① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。
② 若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。
③ 若i>n，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行;
④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m)。
c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。
五、 运行结果
17
六、实验心得
通过这次试验我明白了回溯法的思想，回溯法借助想象出来的树的结构，把问题简单化，使得解问题更方便。通过剪枝函数和约束函数对于求问题的解有很大的帮助，但要把一些限制条件把剪枝函数抽象化。
18
指导教师对实验报告的评语
成绩：
指导教师签字：
年
月
日
19
实验六：最小重量机器设计问题(分支限界法)
一、实验时间：2013年11月12日，星期二，第
一、二节地点：J13#328
二、实验目的及要求
1、了解分支限界法的基本思想。
2、运用分支限界法解决最小重量机器设计问题。
三、实验环境
平台：win7操作系统
开发工具：codeblocks10.05
四、实验内容
最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计
五、算法描述及实验步骤
算法描述：
解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer
实验步骤：
1.定义一个优先队列LinkQueue：
void InitQueue(LinkQueue &Q);//创建一个队列-----首尾结点 void DestroyQueue(LinkQueue &Q);//销毁一个队列 void ClearQueue(LinkQueue &Q);//清空队列
20
int QueueEmpty(LinkQueue &Q);//判断队列是否为空，空则返回TURE，否则返回FLASE int QueueLength(LinkQueue &Q);//求队列的长度
void EnQueue(LinkQueue &Q,QElemType &e);//拆入e为新的队尾元素 void DeQueue(LinkQueue &Q,QElemType &e);//用e返回队列的对头元素 bool IsEmpty(LinkQueue &Q)//判断队列是否为空 2. 定义类MinWeight，实现函数有：
void Add(int wt,int ct,int i);//往队列插入节点 int FindBest();//实现最小重量机器的查找 void setMW();//函数初始化 void printMW();//打印输出结果 3 实现主函数并完成所有代码。
六、调试过程及实验结果
七、总结
利用分支限界法解决最小重量机器问题，就是构造一个优先队列，按照规定的优先级按最大效益优先的方式查找解空间树，找出满足要求的最优解。通过利用分支限界法解决最小重量机器问题，熟练了对分支限界法的使用。
21
指导教师对实验报告的评语
成绩：
指导教师签字：
年
月
日
22
第三篇：PRIM算法实验报告
篇一：prim算法实验报告
算法实验报告
学院：xxx 班级：xxx 学号：xxx 姓名：xxx prim 篇二：prim最小生成树算法实验报告 算法分析与设计之prim 学院：软件学院 学号：201421031059 姓名：吕吕
一、问题描述 1. prim的定义
prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。 2. 实验目的
选择一门编程语言，根据prim算法实现最小生成树，并打印最小生成树权值。
二、 算法分析与设计
1.prim算法的实现过程 基本思想：假设g=(v，e)是连通的，te是g上最小生成树中边的集合。算法从u={u0}(u0∈v)、te={}开始。重复执行下列操作：
在所有u∈u，v∈v-u的边(u，v)∈e中找一条权值最小的边(u0,v0)并入集合te中，同时v0并入u，直到v=u为止。
此时，te中必有n-1条边，t=(v，te)为g的最小生成树。 prim算法的核心:始终保持te中的边集构成一棵生成树。 2.时间复杂度
prim算法适合稠密图，其时间复杂度为o(n^2)，其时间复杂度与边得数目无关，n为顶点数，而看ruskal算法的时间复杂度为o(eloge)跟边的数目有关，适合稀疏图。
三、数据结构的设计 图采用类存储，定义如下： class graph { private: int *verticeslist; int **edge; int numvertices; int numedges; int maxvertices; graph(); ~graph(); bool insertvertex(const int vertex); bool insertedge(int v1,int v2,int cost); int getvertexpos(int vertex); int getvalue(int i); int getweight(int v1,int v2); int numberofvertices(); 1 public: } void prim(); 其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。
四、 代码与运行结果 代码运行结果：
源码：
//普雷姆算法
#include using namespace std; const int maxweight=10000; const int defaultvertices=10000; const int maxedges=10000; const int maxint = 10000000; class graph{ private: int *verticeslist; 2 }; int numvertices; int numedges; int maxvertices; graph(); ~graph(); bool insertvertex(const int vertex); bool insertedge(int v1,int v2,int cost); int getvertexpos(int vertex); int getvalue(int i); int getweight(int v1,int v2); int numberofvertices(); int numberofedges(); void prim(); void lvlv(graph &g); public: istream& operator>>(istream& in,graph &g); ostream& operator<<(ostream& out,graph &g); //默认构造函数 graph::graph() { }; graph::~graph() { delete []verticeslist; delete []edge; 3 maxvertices=defaultvertices; numvertices=0; numedges=0; int i,j; verticeslist=new int [maxvertices]; edge=(int **)new int *[maxvertices]; for(i=0;i
int graph::getvalue(int i) { }; int graph::getweight(int v1,int v2) { }; int graph::numberofvertices() { }; int graph::numberofedges() { }; //插入结点 bool graph::insertvertex(const int vertex) { }; //插入边，v1和v2为结点在数组的下标
bool graph::insertedge(int v1,int v2,int cost) {
if(v1>-1&&v1-1&&v2=0&&i<=numvertices)?verticeslist[i]:null; return (v1!=-1&&v2!=-1)?edge[v1][v2]:0; return numvertices; return numedges; if(numvertices==maxvertices) return false; verticeslist[numvertices++]=vertex; return true; }; } return true; else return false; //输入图信息
istream& operator>>(istream &in ,graph &g) { }; //输出图对象
ostream& operator<<(ostream &out,graph &g) { int i,j,vertices,edges; int start,end,weight; vertices=g.numberofvertices(); edges=g.numberofedges(); out<
in>>vertices>>edges; for(i=1;i<=vertices;i++) { } i=0; while(i>start>>end>>weight; j=g.getvertexpos(start); k=g.getvertexpos(end); if(j==-1||k==-1) {} g.insertedge(j,k,weight); i++; cout<
黄冈师范学院 提高型实验报告
实验课题 最小生成树的prim算法
(实验类型：□综合性 ■设计性 □应用性)
实验课程 算法程序设计 实验时间2010年12月24日
学生姓名 周 媛鑫 专业班级 计科 0801 学 号 200826140110 一.实验目的和要求
(1)根据算法设计需要, 掌握连通网的灵活表示方法; (2)掌握最小生成树的prim算法; (3)熟练掌握贪心算法的设计方法; 二.实验条件
(1)硬件环境：实验室电脑一台 (2)软件环境：wintc 三.实验原理分析
(1)最小生成树的定义：
假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。
(2)构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为mst的性质：假设n=(v,{e})是一个连通网，u是顶点集v的一个非空子集。若(u,v)是一条具有最小权值(代价)的边，其中u∈u，v∈v-u，则必存在一棵包含边 (u.v)的最小生成树。 (3)普里姆(prim)算法即是利用mst性质构造最小生成树的算法。算法思想如下： 假设n=(v,{e})和是连通网，te是n上最小生成树中边的集合。算法从u={u0}( u0∈v)，te={}开始，重复执行下述操作：在所有u∈u，v∈v-u的边(u, v) ∈e中找一条代价最小的边(u0, v0)并入集合te，同时v0并入u，直到u=v为止。此时te中必有n-1条边，则t=(v,{te})为n的最小生成树。 四.实验步骤
(1)数据结构的设计 ：
采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #defineinfinityint_max //最大值
#define max_ertex_num20 //最大顶点数
typedef enum {dg,dn,udg,udn}graphkind;//{有向图,有向网，无向网，无向图} typedef struct arc cell{ vrtype adj ; // vrtype 是顶点关系的类型。对无权图用1和0表示相邻否; infotype * info; //该弧相关信息的指针
}arccell ，adjmatrix [ max_vertex_num][max_vertex_num]; typedef struct { vertextype vexs [ max_vertex_num] ;//顶点向量adjmatrixarcs ; // 邻接矩阵 intvexnum , arcnum ; //图的当前顶点数和弧数 graphkindkind ; // 图的种类标志 }mgraph ; (2)函数设计
函数名称 函数原型 功能描述
main() int main(void) 系统调用主函数 huiru() void huitu () 绘制无向图
graphicver() void graphicver(graph *g) 输出邻接矩阵 prim() void prim(graph *g) prim算法演示 (3)实验源代码
#include #include #include #include #include #define maxvertexnum 50 #define inf 32767 typedef struct graphic {char vexs[maxvertexnum]; int edges[maxvertexnum][maxvertexnum];int v,e; }graph; char tmp[10]; void huitu() /*无向图的图形生成*/ {char buffer[100]; int graphdriver = detect, graphmode; int i,xbefore,ybefore; int x1,y1; char c; /*registerbgidriver(egavga_driver); initgraph(&graphdriver, &graphmode, ); cleardevice(); printf(input pot (300v,&g->e); for(i=1;i<=g->v;i++) for(j=1;j<=g->v;j++) if(i==j) g->edges[i][j]=0; else{ g->edges[i][j]=inf;} for(k=1;k<=g->e;k++) {printf(input %dth edge :,k); scanf(%d,%d,%d,&v1,&v2,&weight); g->edges[v1][v2]=g->edges[v2][v1]=weight; } for(i=1;i<=g->v;i++) {printf( ); for(j=1;j<=g->v;j++) printf((g->edges[i][j]==inf)?∞ :%d ,g->edges[i][j]); } printf( );system(pause); } /***************prim 算法生成最小生成树***************/ void prim(graph *g) {int lowcost[maxvertexnum],closest[maxvertexnum]; int i,j,k,min; for(i=2;i<=g->v;i++) /*n个顶点，n-1条边 */ {lowcost[i]=g->edges[1][i];closest[i]=1; } lowcost[1]=0; /*标志顶点1加入u集合*/ for(i=2;i<=g->v;i++) /*形成n-1条边的生成树 */ {min=inf; k=0; for(j=2;j<=g->v;j++) if((lowcost[j]v;j++)/*修改由顶点k到其他顶点边的权值*/ if(g->edges[k][j]edges[k][j];closest[j]=k;}printf( );} } setviewport(150,140,630,310,1);cleardevice(); setcolor(green);rectangle(10,10,470,160); line(10,60,470,60); line(10,110,470,110); for(i=0;iv;i++) /*n个顶点，n-1条边 */ { lowcost[i]=g->edges[1][i]; /*初始化*/ closest[i]=1; } /*顶点未加入到最小生成树中 */ drawwapicture(lowcost,closest,g->v);lowcost[1]=0; drawwapicture(lowcost,closest,g->v); for(i=2;i<=g->v;i++) /*形成n-1条边的生成树 */ { min=inf; k=0; for(j=2;j<=g->v;j++) if((lowcost[j]v); cprintf((%d,%d)%2d ,closest[k],k,min); lowcost[k]=0;/*顶点k加入u*/ drawwapicture(lowcost,closest,g->v); for(j=2;j<=g->v;j++)/*修改由顶点k到其他顶点边的权值*/
第四篇：银行家算法实验报告
计算机操作系统实验报告
一、 实验名称：银行家算法
二、 实验目的：银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。
三、 问题分析与设计：
1、算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配;若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。
2、银行家算法步骤：(1)如果Requesti
(2)如果Request
(3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：
Available=Available-Request[i]; Allocation=Allocation+Request; Need=Need-Request; (4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
3、安全性算法步骤：
(1)设置两个向量
①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation; ②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。
(2)从进程集合中找到一个能满足下述条件的进程：
①Finish[i]=false ②Need
(3)当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work=Work+Allocation; Finish[i]=true; 转向步骤(2)。
(4)如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则，系统处于不安全状态。
4、流程图： 系统主要过程流程图
银行家算法流程图
安全性算法流程图
四、 实验代码：
//#define M 5 //#define N 3 #include //本实验中使用到的库函数 #include #include int max[5][1]; //开始定义银行家算法中需要用到的数据 int allocation[5][1]; int need[5][1]; int available[1]; int request[5][1]; char *finish[5]; int safe[5]; int n,i,m; int k=0; int j=0; int work[1]; int works[5][1];
void line() //美化程序，使程序运行时更加明朗美观 { printf("----------------- "); } void start() //表示银行家算法开始 { line(); printf(" 银行家算法开始 "); printf(" -- 死锁避免方法 line(); } void end() //表示银行家算法结束 { line(); printf(" 银行家算法结束，谢谢使用 "); line(); } void input() //输入银行家算法起始各项数据 {
for (n=0;n<5;n++)
{
printf("请输入进程P%d的相关信息： ",n);
printf("Max:");
for (m=0;m<1;m++)
scanf("%d",&max[n][m]);
printf("Allocation:");
for (m=0;m<1;m++)
scanf("%d",&allocation[n][m]);
");
}
for (m=0;m<1;m++)
need[n][m]=max[n][m]-allocation[n][m]; printf("请输入系统可利用资源数Available:"); for (m=0;m<1;m++)
} void output() //输出系统现有资源情况 { line(); printf("资源情况 Max Allocation Need Available "); printf("进程 A A A A "); line(); for(n=0;n<5;n++) { printf("P%d%3d%3d%3d",n,max[n][0],allocation[n][0],need[n][0]);
} line(); }
void change() //当Request[i,j]<=Available[j]时，系统把资源分配给进程P[i]，Available[j]和Need[i,j]发生改变
{ for (m=0;m<1;m++) { if (n==0) else
printf(" ");
printf("%3d%3d ",available[0]); scanf("%d",&available[m]);
} } available[m]-=request[i][m]; allocation[i][m]+=request[i][m]; need[i][m]-=request[i][m]; void outputsafe() //输出安全序列的资源分配表 { printf("该安全序列的资源分配图如下： "); line(); printf("资源情况 Work Need Allocation Work+Allocation Finish "); printf("进程 A A A A "); line(); for(n=0;n<5;n++)
printf("P%d%9d%3d%3d%5d%12s ",safe[n],works[safe[n]][0],need[safe[n]][0],allocation[safe[n]][0],works[safe[n]][0]+allocation[safe[n]][0],finish[n]); line(); } int check() //安全性算法 { printf("开始执行安全性算法…… "); for (m=0;m<1;m++) //数组work和finish初始化
work[m]=available[m]; for (n=0;n<5;n++) {
} finish[n]="false"; safe[n]=0; k=0; for (m=0;m<5;m++) for (n=0;n<5;n++)
if(strcmp(finish[n],"false")==0 && need[n][0]<=work[0] ) //查找可以分配资源但尚未分配到资源的进程
{
safe[k]=n; //以数组safe[k]记下各个进程得到
分配的资源的顺序
works[safe[k]][0]=work[0];
放出分配给它的资源
work[0]+=allocation[n][0]; //进程执行后释
finish[n]="ture"; //finish[n]变为1以示该进
程完成本次分
}
k++; for (m=0;m<5;m++) //判断是否所有进程分配资源完成
{
0
素都为ture } else
if (m==4) //此处m=4表示所有数组finish的所有元if (strcmp(finish[m],"false")==0) {
printf("找不到安全序列，系统处于不安全状态。 "); return 0; //找不到安全序列，结束check函数，返回 {
printf("找到安全序列P%d->P%d->P%d->P%d->P%d，系统是安全的 ",safe[0],safe[1],safe[2],safe[3],safe[4]);
} return 1; } void main() //主程序开始 { start(); for (;j==0;) //确认输入数据的正确性，若输入错误，重新输入
{
入：");
} printf("数据确认无误，算法继续。 "); if (check()==0) //若check函数返回值为0，表示输入的初始数据找不到安全序列，无法进行下一步，程序结束
{
} for(;j==1;) //当有多个进程请求资源时，循环开始
{
printf("请输入请求资源的进程i(0、
1、
2、
3、4)："); //输入发出请求向量的进程及请求向量 end(); exit(0); input(); printf("以下为进程资源情况，请确认其是否正确： "); output(); printf("数据是否无误： 正确：输入1 错误：输入0 请输
}
j=1;
outputsafe(); //输出安全序列的资源分配表
scanf("%d",&j);
scanf("%d",&i); printf("请输入进程P%d的请求向量Request%d：",i,i); for(n=0;n<1;n++)
scanf("%d",&request[i][n]);
for (;request[i][0]>need[i][0];) //若请求向量大于需求资源，则认为是输入错误，要求重新输入
{
printf("数据输入有误，请重试! 请输入进程P%d的请求向量Request%d：",i,i);
提供分配
",i);
} if(request[i][0]<=available[0]) //判断系统是否有足够资源
for(n=0;n<1;n++)
scanf("%d",&request[i][n]); {
} else
printf("系统没有足够的资源，进程P%d需要等待。printf("系统正在为进程P%d分配资源…… ",i); change(); //分配资源 j=0; if (j==0) //j=0表示系统有足够资源分配的情况 {
printf("当前系统资源情况如下： "); //输出分配资源后的系统资源分配情况
分配无效
output();
if(check()==0) //若找不到安全系列，则之前的资源 {
printf("本次资源分配作废，恢复原来的资源分配
状态。 ");
资源状态
输入：");
for (m=0;m<1;m++) //恢复分配资源前的系统
}
}
{
}
output(); //输出系统资源状态
available[m]+=request[i][m]; allocation[i][m]-=request[i][m]; need[i][m]+=request[i][m]; printf("是否还有进程请求资源? 是：输入1 否：输入0 请
scanf("%d",&j); //若还有进程请求资源，j=1，之前的for循环条件满足
} end(); }
五、 程序执行结果：
六、实验总结
多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。
第五篇：细胞遗传实验室报告
关于开设细胞遗传实验室的报告
对于复杂疾病，无法判断其为单基因遗传病或是复杂的形态或畸形，需首先考虑做细胞遗传学的分析，以分析是否存在染色体结构或者数目异常。细胞遗传学对遗传病的诊断和产前诊断具有重要意义。细胞遗传学实验室通过常规的核型分析(一般采用G显带和其他的显带技术)，以分析是否存在染色体结构或者数目异常。微小的染色体异常需要通过荧光原位杂交(FISH)，或不经培养的间期核的原位杂交(间期核FISH),或者通过是把正常人和病人基因组进行比较，分析病人是否存在某一个节段的重复缺失的技术，称为比较基因组杂交，又称CGH。这部分为细胞遗传学。
一、申请开展产前诊断技术的医疗保健机构应当向所在地省级卫生行政部门提交下列文件：
(一)医疗机构执业许可证副本;
(二)开展产前诊断技术的母婴保健技术服务执业许可申请文件;
(三)可行性报告;
(四)拟开展产前诊断技术的人员配备、设备和技术条件情况;
(五)开展产前诊断技术的规章制度;
(六)省级以上卫生行政部门规定提交的其他材料;
(七)符合《母婴保健专项技术服务基本条件》。
申请开展产前诊断技术的医疗保健机构，必须明确提出拟开展的产前诊断具体技术项目。
申请开展产前诊断技术的医疗保健机构，由所属省、自治区、直辖市人民政府卫生行政部门审查批准。省、自治区、直辖市人民政府卫生行政部门收到本办法规定的材料后，组织有关专家进行论证，并在收到专家论证报告后30个工作日内进行审核。经审核同意的，发给开展产前诊断技术的母婴保健技术服务执业许可证，注明开展产前诊断以及具体技术服务项目;经审核不同意的，书面通知申请单位。
卫生部根据全国产前诊断技术发展需要，在经审批合格的开展产前诊断技术服务的医疗保健机构中，指定国家级开展产前诊断技术的医疗保健机构。
开展产前诊断技术的《母婴保健技术服务执业许可证》每三年校验一次，校验由原审批机关办理。经校验合格的，可继续开展产前诊断技术;经校验不合格的，撤消其许可证书。
二、申请开展产前诊断技术的医疗保健机构应符合下列所有条件：
(一)设有妇产科诊疗科目;
(二)具有与所开展技术相适应的卫生专业技术人员;
(三)具有与所开展技术相适应的技术条件和设备;
(四)设有医学伦理委员会;
(五)符合《开展产前诊断技术医疗保健机构的基本条件》及相关技术规范。
三、实验室技术人员要求
1.产前诊断实验室技术人员，必须符合下列条件之一：
1)大转以上学历，从事实验室工作2年以上，接受过产前诊断相关实验室技术培训。 2)中级以上技术职称，接受过产前诊断相关实验室技术培训。
2.必须经过系统的产前诊断技术专业培训，通过省级卫生行政部门的考核获得从事产前诊断技术的《母婴保健技术考核合格证书》，方可从事产前诊断技术服务。从事辅助性产前诊断技术的人员，需在取得产前诊断类《母婴保健技术考核合格证书》的人员指导下开展工作。
3.实验室技术人员具备的相关基本知识和技能包括：
1)标本采集与保管的基本知识。 2)无菌消毒技术。
3)标记免疫检测技术的基本知识与操作技能。 4)风险率分析技术。
5)外周血及羊水胎儿细胞培养、制片、显带及染色体核型分析技术。
四、场所要求:
场所应包括标本接收室、接种培养室、标本制备室、阅片室、洗涤室。各工作室应具备恒温设施，标本接收室和接种培养室应具备空气消毒设施。
五、细胞遗传实验室设备：
普通双目显微镜
三筒研究显微镜附显微照相设备 超静工作台
二氧化碳培养箱
普通离心机
恒温干燥箱
自动纯水蒸馏器
恒温水浴箱
普通电冰箱
倒置显微镜附显微照相设备
荧光显微镜
分析天平
恒温培养箱
普通天平
六、开展特色项目
外周血及羊水胎儿细胞培养、制片、显带及染色体核型分析。
染色体核型分析是细胞遗传学研究的基本方法，是研究物种演化、分类以及染色体结构、形态与功能之间关系所不可缺少的重要手段。通过染色体核型分析，可以根据染色体结构和数目的变异情况来判断生物是否患有某种因染色体片段缺失、重复或倒置等引起的遗传病。如产前21三体综合征的诊断，通过核型分析可以在遗传基础上确定该疾病。此外，联合荧光原位杂交技术，还可以对基因进行定位。
应用范围: 1.35岁以上的高龄孕妇。 2.产前筛查后高危人群。
3.曾生育过染色体病患儿的孕妇。
4.产前检查怀疑胎儿患染色体病的孕妇。 5.夫妇一方为染色体异常携带者。
6.孕妇可能为某种X连锁遗传病基因携带者。
7.其他，如曾有不良孕产史者或特殊致畸因子接触史者。
临床应用: 1.代表一个个体的基本属性(如血型，多态性) 2.婚检 3.备孕优生
4.新生儿筛查(一生只做一次的检查) 5.不孕不育症 6.遗传病诊断
7.肿瘤辅助诊断(恶性胸/腹水的辅助诊断) 8.辐射评估
9.流产胚胎染色体(鉴别诊断流产原因) 10.产前诊断(绒毛/羊水/脐血) 11.植入前诊断----PGD 12.白血病诊断及治疗
微小的染色体异常需要通过荧光原位杂交(FISH)
人类染色体微缺失综合征(Microdeletion Syndrome)是一组由于染色体微小缺失造成的一系列疾病综合征的总称，在围产儿和新生儿中发病率较高。近年在全球和我国的主要出生缺陷发病率统计中，先天性心脏病排在首位，在遗传咨询诊断门诊中，排在前列的分别是智力低下、脑瘫和先天性耳聋，这些症状都有可能是某种微缺失综合征的临床表现。
微缺失综合征由于缺失片段较小，所以利用传统的G显带染色体核型分析技术很难被检测出来。FISH技术(荧光标记的原位杂交技术)发展迅速,目前已成为染色体微缺失检测的最重要的方法手段，并已成为某些微缺失综合征检测的金标准。目前FISH可以检测的微缺失综合征主要包括22q11微缺失综合征、X连锁鱼鳞病、猫叫综合征、Angelman综合征、Prader-Willi综合征和Williams综合征等。FISH技术的发展对于出生缺陷的诊断以及进行产前诊断避免出生缺陷儿的出生有非常大的意义。
(图为FISH检测22q11微缺失综合征图像)
其他项目:全自动精液分析、不孕不育抗体(需要设备条件简单)等检查。
【遗传算法java实验报告】相关文章：
遗传算法论文提纲11-15
遗传算法论文范文05-09
遗传算法产品设计论文04-18
基于遗传算法的优化设计论文04-28
遗传算法产品设计论文提纲11-15
遗传算法机械工程论文提纲11-15
遗传算法在面试问题方面的应用12-14
格雷码对遗传算法的改进研究09-10
应用遗传算法求解约束P-中值问题09-10