摘要
本文主要描述了分治策略和贪心算法的基本思想,并且用分治策略实现了快速排序和归并排序两种排序算法。从分、解、合三方面剖析排序,从而得到分割方式影响排序效率的关键,并将分治法扩展应用到更多排序方法中。本文还用贪心算法实现了背包问题与单源点最短路径问题,从荷值比等方面对资源分配进行分析,并将贪心算法应用更广泛。
This paper describes the basic idea of greedy algorithms and the strategy of Divide- and-Conquer, with which quick-sort and merge-sort are implemented . Analysis of the three sorts from the points , the solution and combined , resulting in split by which way is the key to affect the efficiency of the sorting , and will extend Divide-and-Conquer to more sorting method . This article also solve the knapsack and single-source-shorted path problems with greedy algorithm , analysis the value from the charge in terms of resource allocation , and the greedy algorithm is applied more widely .
出处
《武汉船舶职业技术学院学报》
2013年第1期30-36,共7页
Journal of Wuhan Institute of Shipbuilding Technology
关键词
分治策略
贪心算法
快速排序
归并排序
背包问题
单源点最短路径问题
divide-and-conquer
greedy algorithms
quick-sort
merge-sort
knapsack prob- lem
single-source shortest path problem
