数字删除的贪心算法概要.docx

题目：贪心算法求解数字删除问题学生姓名：唐健峰学生姓名：吴贺寿专业班级：计算机科学与技术（非师范班）指导老师：石春2016年12月16日Greedy algorithm to solve the problem of digital deleteAbstract:n the process of seeking the optimal solution of the problem, on thebasis of a greedy standard, starting from the initial state of the problem,to find the optimal solution for each step, through several greedy selection, finally obtains the optimal solution to the problem, this method is a greedy algorithm. From the definition of the greedy algorithm can be seen, the greedy method is not to think about the problem from the whole, it is the choice made by the local optimum in the sense of the solution, and the characteristics of the problem itself determines the use of greedy algorithm can achieve the optimal solution. The selection of the greedy algorithm can rely on previously made choices, but it does not depend on the choice of the future, does not depend on the solution of sub problems, so the greedy algorithm and other algorithm has certain advantages compared to the speed. If a problem can be solved simultaneously in several ways, the greedy algorithm should be one of the best options. This paper first analyzes the digital delete problem, and then gives the greedy solution of the problem, finally proposed the time complexity of the algorithm is analyzed and the core of the problem, the greedy algorithm of the basic properties, characteristics and existing.Keyword：Greedy Algorithm，Digital deletion problem，Optimal solution problem，Complexity。贪心算法求解数字删除问题摘要：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文首先对数字删除删除问题进行了分析，然后给出了该问题的贪心解法，最后对所提出算法的时间复杂度进行了分析以及贪心算法的核心、基本性质、特点及其存在的问题。关键字：贪心算法 数字删除问题 最优解问题 复杂度引言贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心选择。即希望通过问题的局部最优解来求出整个问题的最优解。这种策略是一种很简洁的