（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)，