【作者】 任文轩；

【导师】 刘贵全；

【作者基本信息】 中国科学技术大学 ， 计算机应用技术， 2011， 硕士

【摘要】 贪婪技术就是在每一步操作中,“贪婪”地选择最佳操作,并希望通过一系列局部的最优选择进而对全局问题产生一个最优解。他的特点是一步一步的进行操作,每一步都采用某个优化测度作最优选择从而对目前构造的部分解做一个扩展,直到获得问题的完整解为止。贪婪算法作为一种改进了的分级处理方法,其能否真正解决问题的关键还在于其能否找到合适的量度标准。在一个给定的问题上面,通常都会有好几种不同的量度标准。并且这些量度标准仿佛都是可取的,然而在实际情况中我们如果采用其中大多数的量度标准作处理,我们所得到的“最优解”并不是真正的问题最优解。所以决定一个贪婪算法的效用往往是看其能否选择出产生问题最优解的最优量度标准。本文提出了一种计算物流成本的量度标准,并以该标准作为后面判断的依据。在现代社会中物流产业已经成为国民经济发展的动脉,其发展程度可以说是衡量一国现代化程度和综合国力的重要标志之一。但是目前我国物流成本占GDP比例较高,下降速度也较为缓慢,这反映出我国物流效益整体水平仍然较低。而要改善现状就要提高我们的物流服务,减少物流成本。而运用贪婪算法来处理实际物流中所遇到的物流中心选址和路径选择问题已经成为一个研究方向被人们所关注。本文以舟山海洋经济新区的发展规划为背景,主要工作如下:1)介绍了贪婪算法的概念以及研究现状,并对几种经典的算法(Dijkstra算法和Prim算法)进行了简要介绍和分析。2)研究了贪婪算法在物流中心选址问题上的应用。包括选址问题是如何产生的,以及目前所用的几种解决方法,并着重介绍了运用贪婪算法解决这一问题时的基本原理和计算方法。3)研究了贪婪算法在解决物流路径问题上的应用,并分析所用的基本原理和存在的不足,进而提出一种新的并行计算方法来加以解决。4)运用上述算法对舟山市的物流网络进行分析,并进行了技术实现。更多还原

【Abstract】 The Greed technology is a strategy by which we―greedily‖choose the optimal operation in every step, hoping that we get an optimal solution of the whole problem through a series of locally optimal choice. His characteristic lies in solving the problem step by step, with each step using an optimization measure to make optimal choices to make an extension on the current construction until we completely solve the problem.As an improved hierarchical processing method, the Greedy algorithm’s effectiveness also lies in whether we could find a suitable standard of measurement. There are often several different standards of measurement in a given problem. And all these measures are seemed desirable. However, actually, the" optimal" we get is not the real optimal solution if we adopt most of these standard measures for treatment to the problem. So the effectiveness of a greedy algorithm depends on whether we could find the best standard of measurement. This article offers a standard of measurement and uses it to deal with the mentioned problems.In modern society, logistics has become the artery of national economic development. Its development can be regarded as a measure of a country’s modernization and also as the symbol of a country’s comprehensive national strength. But at present our country content sheds cost to occupy GDP proportion is still in high position, the falling speed is relatively slow, which reflects the overall level of China’s logistics benefit is still low. In order to improve the service of logistics, we need to minimize the cost of the logistics network. Using the greedy algorithm to deal with the practical logistics center location and path selection has become one of the hot research topics concerned by scientists..This article under the background of the ZhouShan Marine Economic Zone Development Plan introduces :1)The concept and research status quo of greedy algorithm and introduce several classical algorithms(Prim algorithm, Dijkstra algorithm), and then put forward the innovation of this article and article structure.2) This article introduces how to use the greedy algorithm to solve the logistics center location problem, including the introduction of how the location problem comes up and the using of several solving methods. Then it introduces the use of the greedy algorithm and the basic principles and the methods of calculation to solve these problems.3) This article studies the greedy algorithm in solving logistics routing problem on the application and analysises the basic principle, then proposes a new method of parallel computing.4) Based on this algorithm, we analysis the Zhoushan city logistics with the application of this technology.更多还原