贪心算法Tsp实习报告1
- 格式：pdf
- 大小：319.26 KB
- 文档页数：9
下载文档原格式
合集下载
实验三-贪心算法
StringBuffer buf=newStringBuffer();
for(inti=0;i<s.length();i++){
buf.append(getEachCode(s.substring(i,i+1)));
}
returnbuf.toString();
}
publicString getEachCode(String name){
for(inti=0;i<buffer.length();i++){
if(name.equals(codes[i].name)){
returnhuffstring[i];
}
}
return"";
}
publicvoidgetCode(intn,String[] thecodes,String thebuffer){
importjava.util.Scanner;
classHuffmanCode{
Stringname;
doubleweight;
intlc,rc,pa;
publicHuffmanCode(){
name="";
weight=0;
lc=-1;rc=-1;pa=-1;
}
}
publicclassHuffman1 {
dist[j]=newdist;prev[j]=u;}}}}
(3)运行结果
3、题目三
(1)问题分析
设G=（V，E）是连通带权图，V={1，2，…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S{1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。过程中所取到的边恰好构成G的一棵最小生成树。
for(inti=0;i<s.length();i++){
buf.append(getEachCode(s.substring(i,i+1)));
}
returnbuf.toString();
}
publicString getEachCode(String name){
for(inti=0;i<buffer.length();i++){
if(name.equals(codes[i].name)){
returnhuffstring[i];
}
}
return"";
}
publicvoidgetCode(intn,String[] thecodes,String thebuffer){
importjava.util.Scanner;
classHuffmanCode{
Stringname;
doubleweight;
intlc,rc,pa;
publicHuffmanCode(){
name="";
weight=0;
lc=-1;rc=-1;pa=-1;
}
}
publicclassHuffman1 {
dist[j]=newdist;prev[j]=u;}}}}
(3)运行结果
3、题目三
(1)问题分析
设G=（V，E）是连通带权图，V={1，2，…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S{1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。过程中所取到的边恰好构成G的一棵最小生成树。
贪心算法实验报告算法实验贪心法实验报告
贪心算法实验报告算法实验贪心法实验报告西安邮电大学（计算机学院）课内实验报告实验名称：贪心算法专业名称：班级：学生姓名：学号（8指导教师：实验日期：一. 实验目的及实验环境1.练习掌握最有分解问题的规划设计与实现；2.熟练掌握递归算法的设计及应用，怎样才能使算法的空间复杂度和时间复杂度最低；基于Linux系统下的ubuntu或其他的编辑器二. 实验内容1. 设n是一个正整数，现在要求将n分解为若干互不相同的自然数的和，且使这些自然数的乘积最大三．方案设计1.先将这个数分解成以2开始的连续的若干因子，它们的和加起来是n，将此数在后项优先的方式下均匀地分给前面各项。
保证正整数所分解出的因子之差的绝对值最小，即| a – b |最小，可以保证分解乘积越大。
四．测试数据及运行结果1．正常测试数据（3组）及运行结果；A.2.非正常测试数据（2组）及运行结果A.B.五．总结1．实验过程中遇到的问题及解决办法；在实验过程中错误不断地出现，我认真地查阅书籍，研究课本上例题，并且在同学的帮助下纠正了自己的错误，得出了正确的结果。
2．对设计及调试过程的心得体会。
在程序的运行与调试过程中出现了很多错误，但是通过自己复习课本知识、查询资料等，修改后得出了正确的结果。
而且我觉得自己一定要敢于尝试，即使没有结果但是勇于实践就会有意想不到的收获。
所以在以后的学习中我觉得我们一定要集中精力、端正自己态度，提高自己的成绩。
当然我也认识到了自己的薄弱之处，因此我一定争取做的能让自己满意，做的更好。
六．附录：源代码（电子版）#include#includevoid open_file(int n){FILE *fp;if((fp=fopen(“input.txt”,”wt”))==NULL) {printf(“the file write failed.\n”);exit(1);}fprintf(fp,”%2d\n”,n);fclose(fp);}void save_file(int sum){FILE *fp;if((f p=fopen(“output.txt”,”wt”))==NULL) {printf(“ the file save failed!.\n”);exit(1);}fprintf(fp,”%2d\n”,sum);fclose(fp);if((fp=fopen(“output.txt”,”r”))==NULL) {printf(“save file failed!\n”);exit(1);}fscanf(fp,”%2d”,&sum);printf(“\n鏈€澶х?d\n”,sum);fclose(fp);}int MAX(int n){int i=2,j=0,data[n],sum=0,max=1; int lenth; while(sum+i{sum+=i;data[j]=i;i++;j++;}lenth=j;i=n-sum;while(i>0){if(j{data[j+i]+=1;i--;j--;}else{data[j-1]+=1;i--;j--;}}for(i=0;imax*=data[i];return max;}int main(){int n,max;srand((unsigned)time(NULL)); n=rand()%100; open_file(n);printf(“ 杩欎釜鏁版槸%d:\n”,n); max=MAX(n); save_file(max);return 0; }百度搜索“就爱阅读”,专业资料,生活学习,尽在就爱阅读网,您的在线图书馆。
贪心算法 实验报告
贪心算法实验报告贪心算法实验报告引言：贪心算法是一种常用的算法设计策略，它通常用于求解最优化问题。
贪心算法的核心思想是在每一步选择中都选择当前最优的解，从而希望最终能够得到全局最优解。
本实验旨在通过实际案例的研究，探索贪心算法的应用和效果。
一、贪心算法的基本原理贪心算法的基本原理是每一步都选择当前最优解，而不考虑整体的最优解。
这种贪婪的选择策略通常是基于局部最优性的假设，即当前的选择对于后续步骤的选择没有影响。
贪心算法的优点是简单高效，但也存在一定的局限性。
二、实验案例：零钱兑换问题在本实验中，我们以零钱兑换问题为例，来说明贪心算法的应用。
问题描述：假设有不同面值的硬币，如1元、5元、10元、50元和100元，现在需要支付给客户x元，如何用最少的硬币数完成支付？解决思路：贪心算法可以通过每次选择当前面值最大的硬币来求解。
具体步骤如下：1. 初始化一个空的硬币集合，用于存放选出的硬币。
2. 从面值最大的硬币开始，如果当前硬币的面值小于等于待支付金额，则将该硬币放入集合中，并将待支付金额减去该硬币的面值。
3. 重复步骤2，直到待支付金额为0。
实验过程：以支付金额为36元为例，我们可以通过贪心算法求解最少硬币数。
首先，面值最大的硬币为100元，但36元不足以支付100元硬币，因此我们选择50元硬币。
此时，剩余待支付金额为36-50=-14元。
接下来，面值最大的硬币为50元，但待支付金额为负数，因此我们选择下一个面值最大的硬币，即10元硬币。
此时，剩余待支付金额为-14-10=-24元。
继续选择10元硬币，剩余待支付金额为-24-10=-34元。
再次选择10元硬币，剩余待支付金额为-34-10=-44元。
最后，选择5元硬币，剩余待支付金额为-44-5=-49元。
由于待支付金额已经为负数，我们无法继续选择硬币。
此时，集合中的硬币数为1个50元和3个10元，总共4个硬币。
实验结果：通过贪心算法，我们得到了36元支付所需的最少硬币数为4个。
贪心算法实验报告心得
贪心算法实验报告心得前言贪心算法是一种常见且重要的算法设计思想，通过每一步都选择当下最优的解决方案，以期望最终得到全局最优解。
在学习与实践贪心算法的过程中，我有了许多心得与体会。
什么是贪心算法？贪心算法是一种求解问题的算法思想，它的特点是每一步都选择当前最优的解决方案，而不考虑该选择对以后步骤的影响。
贪心算法通常适用于可以将问题分解为若干个子问题，并且通过每次选择当前最优解来得到整体最优解的情况。
贪心算法的基本步骤贪心算法的基本步骤可以总结为以下几个方面：1.确定问题的解空间，并找到问题的最优解。
贪心算法通常通过穷举法或者利用问题的特殊性质来确定解空间。
2.制定贪心策略。
贪心算法的核心是确定每一步选择的贪心策略，即选择当前最优解。
3.确定贪心策略的正确性。
贪心算法的一个关键问题是如何证明贪心策略的正确性。
可以通过数学证明、反证法或者举反例等方式来进行证明。
4.实现贪心算法。
将贪心策略转化为实际可执行的算法步骤，编写代码来求解问题。
贪心算法实验结果分析在本次实验中，我使用贪心算法解决了一个经典问题：找零钱问题（Change-Making Problem）。
给定一定面额的硬币和需找的金额，我们的目标是使用最少的硬币来完成找零钱。
贪心算法的思路是每次选择面额最大的硬币进行找零。
实验设计1.实验输入：我设计了多组输入来测试贪心算法的性能。
每组输入包括一个需找的金额和一个硬币集合。
2.实验输出：对于每组输入，贪心算法输出一个最优的硬币找零方案，以及使用的硬币数量。
3.实验评价：我使用了实际需找金额与贪心算法计算得到的找零金额的差值来评估算法的准确性，并统计了算法的时间复杂度。
实验结果从多组实验结果中可以观察到，贪心算法在大部分情况下给出了正确的找零金额，并且算法的时间复杂度较低。
结果分析贪心算法在找零钱问题中的应用是合理的。
每次选择面额最大的硬币进行找零，可以快速接近最优解，并且相对其他算法具有较低的时间复杂度。
《算法设计与分析》课程实验报告 (贪心算法(一))
《算法设计与分析》课程实验报告实验序号：07实验项目名称：实验8 贪心算法（一）一、实验题目1.删数问题问题描述：键盘输入一个高精度的正整数N（不超过250 位），去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。
编程对给定的N 和k，寻找一种方案使得剩下的数字组成的新数最小。
若输出前有0则舍去2.区间覆盖问题问题描述：设x1,x2,...xn是实轴上的n个点。
用固定长度为k的闭区间覆盖n个点，至少需要多少个这样的固定长度的闭区间？请你设计一个有效的算法解决此问题。
3.会场安排问题问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。
设计一个有效的贪心算法进行安排。
（这个问题实际上是著名的图着色问题。
若将每一个活动作为图的一个顶点，不相容活动间用边相连。
使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。
）4.导弹拦截问题问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
给定导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
二、实验目的（1）通过实现算法，进一步体会具体问题中的贪心选择性质，从而加强对贪心算法找最优解步骤的理解。
（2）掌握通过迭代求最优的程序实现技巧。
（3）体会将具体问题的原始数据预处理后（特别是以某种次序排序后），常能用贪心求最优解的解决问题方法。
三、实验要求（1）写出题1的最优子结构性质、贪心选择性质及相应的子问题。
（2）给出题1的贪心选择性质的证明。
（3）（选做题）：写出你的算法的贪心选择性质及相应的子问题，并描述算法思想。
算法实验报告贪心
一、实验背景贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。
贪心算法并不保证能获得最优解，但往往能获得较好的近似解。
在许多实际应用中，贪心算法因其简单、高效的特点而被广泛应用。
本实验旨在通过编写贪心算法程序，解决经典的最小生成树问题，并分析贪心算法的优缺点。
二、实验目的1. 理解贪心算法的基本原理和应用场景；2. 掌握贪心算法的编程实现方法；3. 分析贪心算法的优缺点，并尝试改进；4. 比较贪心算法与其他算法在解决最小生成树问题上的性能。
三、实验内容1. 最小生成树问题最小生成树问题是指：给定一个加权无向图，找到一棵树，使得这棵树包含所有顶点，且树的总权值最小。
2. 贪心算法求解最小生成树贪心算法求解最小生成树的方法是：从任意一个顶点开始，每次选择与当前已选顶点距离最近的顶点，将其加入生成树中，直到所有顶点都被包含在生成树中。
3. 算法实现（1）数据结构- 图的表示：邻接矩阵- 顶点集合：V- 边集合：E- 已选顶点集合：selected- 最小生成树集合：mst（2）贪心算法实现```def greedy_mst(graph):V = set(graph.keys()) # 顶点集合selected = set() # 已选顶点集合mst = set() # 最小生成树集合for i in V:selected.add(i)mst.add((i, graph[i]))while len(selected) < len(V):min_edge = Nonefor edge in mst:u, v = edgeif v not in selected and (min_edge is None or graph[u][v] < graph[min_edge[0]][min_edge[1]]):min_edge = edgeselected.add(min_edge[1])mst.add(min_edge)return mst```4. 性能分析为了比较贪心算法与其他算法在解决最小生成树问题上的性能，我们可以采用以下两种算法：（1）Prim算法：从任意一个顶点开始，逐步添加边，直到所有顶点都被包含在生成树中。
算法设计策略实习报告
实习报告：算法设计策略一、实习背景与目的随着计算机技术的快速发展，算法在各种领域中的应用越来越广泛，算法设计能力成为计算机专业学生必备的技能。
为了提高自己的算法设计能力，了解并掌握不同的算法设计策略，我参加了本次算法设计策略实习。
实习目的是通过实践锻炼自己的算法思维，培养解决实际问题的能力，并加深对算法设计策略的理解。
二、实习内容与过程实习的主要内容包括贪心算法、动态规划和分治策略等算法设计策略。
在实习过程中，我完成了以下几个部分：1. 贪心算法：以 P118 习题 2 和 P118 习题 5 为例，分别解决邻接链表表示的有向无环图的最短路径问题和最小权匹配问题。
通过编写程序代码，验证了贪心算法的有效性和可行性。
2. 动态规划：以斐波那契数列和最长公共子序列为例，学习动态规划的基本思想和方法。
通过实现动态规划算法，了解了动态规划在解决最优化问题中的应用。
3. 分治策略：以快速排序和归并排序为例，学习分治策略的基本思想和实现方法。
通过编写程序代码，验证了分治策略在解决排序问题中的应用和效率。
4. 算法分析：对上述算法进行时间复杂度和空间复杂度分析，了解不同算法设计策略的优缺点。
三、实习收获与反思通过本次实习，我对算法设计策略有了更深入的了解，收获如下：1. 掌握了贪心算法、动态规划和分治策略等基本的算法设计策略，并能够运用这些策略解决实际问题。
2. 提高了编程能力，学会了如何将算法设计转化为程序代码，并能够调试和优化代码。
3. 加深了对算法分析的理解，能够从时间复杂度和空间复杂度两个方面评估算法的性能。
4. 培养了自己的团队协作能力和问题解决能力，在实习过程中学会了如何与他人合作，共同解决问题。
在实习过程中，我也意识到自己在算法设计方面还存在一些不足，如对一些复杂问题的解决能力有待提高，需要进一步加强学习和实践。
四、实习总结本次算法设计策略实习使我受益匪浅，不仅提高了自己的算法设计能力，而且加深了对算法设计策略的理解。
贪心算法_实验报告
贪心算法_实验报告一、设计分析●问题描述：键盘输入一个高精度的正整数N（N不超过240位），去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。
●设计思路：在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪心策略解决此问题。
删除高位较大的数字。
具体：相邻两位比较若高位比低位大则删除高位。
删除字符的方法：1）物理删除，用后面的字符覆盖已删除的字符。
有比较多字符移动操作，算法效率不高。
2）用数组记录字符的状态，“1”表示对应数字存在，“0”表示对应数字已删除。
3）利用数组，记录未删除字符的下标：n=“1 2 4 3 5 8 3 3”0 0 0 0 0 04比3大删除“1 2 3 5 8 3 3” 1 2 4 5 0 08比3大删除“1 2 3 5 3 3” 1 2 4 5 05比3大删除“1 2 3 3 3” 1 2 4 7 8二、程序代码c语言实现#include<stdio.h>#include<string.h>#define N 10000int main(void){char a[N];int i,j,k,n;printf("输入要处理的数据：\n");gets(a);printf("输入要删除的数字个数：\n");scanf("%d",&n);三、测试用例四、实验总结加深了对贪心算法的理解与运用。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
贪心算法设计实验报告
A
B
C
D
E
F
G
0
0
0
0
1
0
0
0
对表进行维护（维护后仍同上表，因为还没有两个集合合并）
0
A
B
C
D
E
F
G
0
0
0
0
1
0
0
0
C，选择第二条边 C----E （修改上表）
0
A
B
C
D
E
F
G
0
0
0
0
1
3
0
0
对上表进行维护（任同上表，因为还没有两个集合合并）
0
A
B
C
D
E
F
G
0
0
0
0
1
3
0
0
D，选择第三条边（ D-----F ） (根据条件 DF 两点不再同一集合，改边可选 ) 然后就合并 DF 两点所在的集合 D 的前去是 1，即 A 标记为 0， E 的标记也为 0，合并因为 6>1 所以表修改如下
Edge* selectionsort(Edge *array,int n)// 选择排序（对边按权重由高到低排序） {
int i,j,min,temp; for(i=0;i<n;i++) {
min=i; for(j=i+1;j<n;j++)
if(array[min].weight>array[j].weight) min=j;
在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中
只有一棵树，也即子图中含有
贪心算法求解TSP(旅行商问题)
例如给定一个城市和城市间的距离集合，求经过所有城 市恰好一次的最短回路， 即；给定图G=(V，E，W)，其中V为顶点集合，|V|=n ，E为边集合，W为边权函数，求集合{1,2，…n}的一个 排列使得下式最小。
解决思路：
借助矩阵把问题转化为矩阵中点的求解：
首先构造距离矩阵，任意节点到自身节点的距离为无穷大( 在这里我用100来表示无穷大)，在第一行找到最小项a[1][j]，
8）End while
特殊说明： 程序在访问最后一个节点钱，所访问的行中至少有1个允许访问的节 点，依次访问这些节点找到最小即可：在访问最后一个节点后，再 次访问，会返回k=0，即实现了访问源节点。所以，各个节点都被访 问，且访问路径为一简单回路。
实例演示：
例题： 以4个节点为例，演示算法运行过程（以100表示无大）： 输入连接矩阵： 100 3 9 3 100 1 2 4
核心算法说明：
1）输入节点数n和连接矩阵a
2）定义行、列允许矩阵row[n]={1,…,1}、row[n]={1,…,1} 3）赋初值：s=0,i=0 4）While row[i]=1 5） 6） 7） j=0,m=a[i][0],k=0 找到第一个允许访问的节点a[i][j] 寻找a[i][j~n-1]中的最小元素
从而跳到第j行；再找到最小值a[j][k]，从而跳到第k行进行查
找…… 然后构造各行允许数组row[n]={1,…,1}，各列允许数组 colable[n]={0,1,…,1}，其中1表示允许访问，即该节点未被访 问；0表示不允许访问，即该节点已被访问。如果该行或该列 不允许访问，则跳过该点访问下一节点。
最优子结构性质(n>=2)：
设sn是此问题的最优解，那么可以把它分解为 sn=s2+sn-1; 假设存在s’n-1为n-1规模是的最优解，则 sn<s2+s’n-1, 而这与假设矛盾，所以可以得出旅行商问题具有最 优子结构性质。
解决思路：
借助矩阵把问题转化为矩阵中点的求解：
首先构造距离矩阵，任意节点到自身节点的距离为无穷大( 在这里我用100来表示无穷大)，在第一行找到最小项a[1][j]，
8）End while
特殊说明： 程序在访问最后一个节点钱，所访问的行中至少有1个允许访问的节 点，依次访问这些节点找到最小即可：在访问最后一个节点后，再 次访问，会返回k=0，即实现了访问源节点。所以，各个节点都被访 问，且访问路径为一简单回路。
实例演示：
例题： 以4个节点为例，演示算法运行过程（以100表示无大）： 输入连接矩阵： 100 3 9 3 100 1 2 4
核心算法说明：
1）输入节点数n和连接矩阵a
2）定义行、列允许矩阵row[n]={1,…,1}、row[n]={1,…,1} 3）赋初值：s=0,i=0 4）While row[i]=1 5） 6） 7） j=0,m=a[i][0],k=0 找到第一个允许访问的节点a[i][j] 寻找a[i][j~n-1]中的最小元素
从而跳到第j行；再找到最小值a[j][k]，从而跳到第k行进行查
找…… 然后构造各行允许数组row[n]={1,…,1}，各列允许数组 colable[n]={0,1,…,1}，其中1表示允许访问，即该节点未被访 问；0表示不允许访问，即该节点已被访问。如果该行或该列 不允许访问，则跳过该点访问下一节点。
最优子结构性质(n>=2)：
设sn是此问题的最优解，那么可以把它分解为 sn=s2+sn-1; 假设存在s’n-1为n-1规模是的最优解，则 sn<s2+s’n-1, 而这与假设矛盾，所以可以得出旅行商问题具有最 优子结构性质。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（5） 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 （6） 最后，目标函数给出解的值。
2.2.2 贪心算法的缺陷
贪心算法（又称贪心算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解 或者是整体最优解的近似解。
1.3 贪心算法的概念
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解 或者是整体最优解的近似解。
为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪心算 法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择 函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行， 那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是 否构成解。如果贪心算法正确工作，那么找到的第一个解通常是最优的。
3. 课程实习报告内容
3.1 了解并掌握贪心算法
贪心算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技 术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作 最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费 的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将
2. 课程实习题目描述和要求.........................................................................................................1 2.1 TSP 问题介绍.................................................................................................................1 2.2 贪心算法的特性.............................................................................................................2 2.2.1 贪心算法的特性：............................................................................................ 2 2.2.2 贪心算法的缺陷................................................................................................ 2 2.3 关于贪心算法的备注.................................................................................................... 2
3. 课程实习报告内容.....................................................................................................................2 3.1 了解并掌握贪心算法.................................................................................................... 2 3.2 设计内容.........................................................................................................................3 3.2.1 问题描述.............................................................................................................3 3.2.2 设计思想.............................................................................................................3 3.3 需求分析.........................................................................................................................3 3.3.1 程序的功能：.................................................................................................... 3 3.3.2 输入输出的要求................................................................................................ 4 3.4 贪心算法解决 TSP 问题的流程图............................................................................... 4 3.5 贪心算法解决 TSP 问题的步骤................................................................................... 5
浙江农林大学信息工程学院
课 程 实习 报 告
课程名称： 班 级： 题 目： 组 长： 成 员： 指导教师：
数据结构实习 电信****班
TSP 问题的贪心算法 ******* ******* *******
2014 年 6 月 17 日
目
录
1. 课程实习目的.............................................................................................................................1 1.1 贪心算法实习的目的.................................................................................................... 1 1.2 TSP 问题的解决及贪心算法的应用............................................................................ 1 1.3 贪心算法的概念.............................................................................................................1
4. 总结.............................................................................................................................................5 5. 任务分配.....................................................................................................................................5
1
浙江农林大学信息工程学院课程大作业报告
且记 t(n+1)=t1，则旅行商问题的数学模型为：min =σd(t(i),t(i+1)) （i=0,···,9）。
2.2 贪心算法的特性
2.2.1 贪心算法的特性：
（1ห้องสมุดไป่ตู้ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的 集合：比如不同面值的硬币。
1. 课程实习目的
浙江农林大学信息工程学院课程大作业报告
1.1 贪心算法实习的目的
此次实习通过贪心算法来解决 TSP 问题。假设有 n 个城市，任意两个城市之间都有路 径相通，并设第 i 个城市与第 j 个城市之间的距离为 Dij，求从某个城市出发经过所有城市 并且只经过一次又回到原点的都短距离。 首先，本文运用 Visual C++集成开发环境将贪心 算法编程实现，并解决 TSP 问题。然后通过改变各个参数的值来观察计算结果，接着对运 算结果的进行对比分析，从而验证各个参数对贪心算法的影响。
2. 课程实习题目描述和要求
2.1 TSP 问题介绍
TSP 问题，也称旅行商问题。已知 n 个城市之间的相互距离，现有一个推销员必须遍访 这 n 个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他的访问顺 序，可使其旅行的总长度最短。用图论的术语来说，假设有一个图 g=(v , e),其中 v 是顶点集， e 是边集，设 d=dij 是由顶点 i 和顶点 j 之间距离所组成的距离矩阵，旅行商问题就是要求出 一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行 商问题( dij = dji )任意（i , j=1,2,3,···,n）和非对称旅行商问题(dij≠dji)任意 i , j=（1,2,3,···,n）。 城市 v={v1,v2,v3,···,vn 的一个访问顺序为 t(t1,t2,t3,···,ti,···,tn),其中 ti∈v(i=1,2,3,···,n)，
2.2.2 贪心算法的缺陷
贪心算法（又称贪心算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解 或者是整体最优解的近似解。
1.3 贪心算法的概念
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解 或者是整体最优解的近似解。
为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪心算 法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择 函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行， 那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是 否构成解。如果贪心算法正确工作，那么找到的第一个解通常是最优的。
3. 课程实习报告内容
3.1 了解并掌握贪心算法
贪心算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技 术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作 最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费 的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将
2. 课程实习题目描述和要求.........................................................................................................1 2.1 TSP 问题介绍.................................................................................................................1 2.2 贪心算法的特性.............................................................................................................2 2.2.1 贪心算法的特性：............................................................................................ 2 2.2.2 贪心算法的缺陷................................................................................................ 2 2.3 关于贪心算法的备注.................................................................................................... 2
3. 课程实习报告内容.....................................................................................................................2 3.1 了解并掌握贪心算法.................................................................................................... 2 3.2 设计内容.........................................................................................................................3 3.2.1 问题描述.............................................................................................................3 3.2.2 设计思想.............................................................................................................3 3.3 需求分析.........................................................................................................................3 3.3.1 程序的功能：.................................................................................................... 3 3.3.2 输入输出的要求................................................................................................ 4 3.4 贪心算法解决 TSP 问题的流程图............................................................................... 4 3.5 贪心算法解决 TSP 问题的步骤................................................................................... 5
浙江农林大学信息工程学院
课 程 实习 报 告
课程名称： 班 级： 题 目： 组 长： 成 员： 指导教师：
数据结构实习 电信****班
TSP 问题的贪心算法 ******* ******* *******
2014 年 6 月 17 日
目
录
1. 课程实习目的.............................................................................................................................1 1.1 贪心算法实习的目的.................................................................................................... 1 1.2 TSP 问题的解决及贪心算法的应用............................................................................ 1 1.3 贪心算法的概念.............................................................................................................1
4. 总结.............................................................................................................................................5 5. 任务分配.....................................................................................................................................5
1
浙江农林大学信息工程学院课程大作业报告
且记 t(n+1)=t1，则旅行商问题的数学模型为：min =σd(t(i),t(i+1)) （i=0,···,9）。
2.2 贪心算法的特性
2.2.1 贪心算法的特性：
（1ห้องสมุดไป่ตู้ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的 集合：比如不同面值的硬币。
1. 课程实习目的
浙江农林大学信息工程学院课程大作业报告
1.1 贪心算法实习的目的
此次实习通过贪心算法来解决 TSP 问题。假设有 n 个城市，任意两个城市之间都有路 径相通，并设第 i 个城市与第 j 个城市之间的距离为 Dij，求从某个城市出发经过所有城市 并且只经过一次又回到原点的都短距离。 首先，本文运用 Visual C++集成开发环境将贪心 算法编程实现，并解决 TSP 问题。然后通过改变各个参数的值来观察计算结果，接着对运 算结果的进行对比分析，从而验证各个参数对贪心算法的影响。
2. 课程实习题目描述和要求
2.1 TSP 问题介绍
TSP 问题，也称旅行商问题。已知 n 个城市之间的相互距离，现有一个推销员必须遍访 这 n 个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他的访问顺 序，可使其旅行的总长度最短。用图论的术语来说，假设有一个图 g=(v , e),其中 v 是顶点集， e 是边集，设 d=dij 是由顶点 i 和顶点 j 之间距离所组成的距离矩阵，旅行商问题就是要求出 一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行 商问题( dij = dji )任意（i , j=1,2,3,···,n）和非对称旅行商问题(dij≠dji)任意 i , j=（1,2,3,···,n）。 城市 v={v1,v2,v3,···,vn 的一个访问顺序为 t(t1,t2,t3,···,ti,···,tn),其中 ti∈v(i=1,2,3,···,n)，