Greedy algorithm

From Wikipedia, the free encyclopedia

Jump to: navigation, search
The greedy algorithm determines the minimum number of US coins to give while making change. These are the steps a human would take to emulate a greedy algorithm. The coin of the highest value, less than the remaining change owed, is the local optimum. (Note that in general the change-making problem requires dynamic programming or integer programming to find an optimal solution; US and other currencies are special cases where the greedy strategy works.)

A greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimal choice at each stage[1] with the hope of finding the global optimum.

For example, applying the greedy strategy to the traveling salesman problem yields the following algorithm: "At each stage visit the unvisited city nearest to the current city".



[edit] Specifics

In general, greedy algorithms have five pillars:

  1. A candidate set, from which a solution is created
  2. A selection function, which chooses the best candidate to be added to the solution
  3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
  4. An objective function, which assigns a value to a solution, or a partial solution, and
  5. A solution function, which will indicate when we have discovered a complete solution

Greedy algorithms produce good solutions on some mathematical problems, but not on others. Most problems for which they work well have two properties:

Greedy choice property 
We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution.
Optimal substructure 
"A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."[2] Said differently, a problem has optimal substructure if the best next move always leads to the optimal solution. An example of 'non-optimal substructure' would be a situation where capturing a queen in chess (good next move) will eventually lead to the loss of the game (bad overall move).

[edit] When greedy-type algorithms fail

For many other problems, greedy algorithms fail to produce the optimal solution, and may even produce the unique worst possible solutions. One example is the nearest neighbor algorithm mentioned above: for each number of cities there is an assignment of distances between the cities for which the nearest neighbor heuristic produces the unique worst possible tour. [3]

Imagine the coin example with only 25-cent, 10-cent, and 4-cent coins. We could make 41 cents change with one 25-cent coin and four 4-cent coins, but the greedy algorithm could only make change for 39 or 43 cents, as it would have committed to using one dime.

[edit] Types

Greedy algorithms can be characterized as being 'short sighted', and as 'non-recoverable'. They are ideal only for problems which have 'optimal substructure'. Despite this, greedy algorithms are best suited for simple problems (e.g. giving change). It is important, however, to note that the greedy algorithm can be used as a selection algorithm to prioritize options within a search, or branch and bound algorithm. There are a few variations to the greedy algorithm:

  • Pure greedy algorithms
  • Orthogonal greedy algorithms
  • Relaxed greedy algorithms

[edit] Applications

Greedy algorithms mostly (but not always) fail to find the globally optimal solution, because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimisation methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, Dijkstra's algorithm for finding single-source shortest paths, and the algorithm for finding optimum Huffman trees.

The theory of matroids, and the more general theory of greedoids, provide whole classes of such algorithms.

Greedy algorithms appear in network routing as well. Using greedy routing, a message is forwarded to the neighboring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad-hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

[edit] Examples

[edit] See also

Epsilon-greedy strategy

[edit] Notes

  1. ^ Paul E. Black, "greedy algorithm" in Dictionary of Algorithms and Data Structures [online], U.S. National Institute of Standards and Technology, February 2005, webpage: NIST-greedyalgo.
  2. ^ Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".
  3. ^ (G. Gutin, A. Yeo and A. Zverovich, 2002)

[edit] References

  • Introduction to Algorithms (Cormen, Leiserson, and Rivest) 1990, Chapter 16 "Greedy Algorithms" p. 329.
  • Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".
  • G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81–86.
  • J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121–127.
  • G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288–298.
by 짱가 updownme 2009.03.31 18:24


C++코딩으로 다시 돌아온 시점에….

헤더파일 뭐 썼었는지도 기억이 안나는건..ㅠㅠ 부끄럽다..
오늘부터 차근차근 다시 읽어가기+_+

언뜻 보기에도 cin이 scanf보다는 훨씬 더 좋아 보인다. 입출력 객체는 C 표준 라이브러리의 printf, scanf함수에 비해 많은 장점을 가지고 있다.

① 사용 방법이 훨씬 더 직관적이다. 출력할 때는 << 연산자로 데이터를 출력 객체에게 보내고 입력 객체는 >> 연산자로 입력받은 값을 변수로 보내는 모양을 하고 있어 사용하기 쉽다. <<, >> 연산자의 머리 부분이 입출력 방향을 명시하므로 모양대로 사용하면 된다.

② 입출력 객체가 데이터의 타입을 자동으로 판별하기 때문에 서식을 일일이 기억할 필요도 없고 서식을 잘못 적는 실수를 할 리도 없으니 안전하다. printf는 서식과 인수의 개수가 맞지 않거나 타입이 틀릴 경우 컴파일 에러는 발생하지 않지만 실행중에 프로그램이 다운될 수 있다. scanf는 입력받을 데이터가 문자열이 아닌 경우 반드시 &연산자로 주소를 넘겨야 하는데 이를 깜박 잊으면 마찬가지로 프로그램이 먹통이 되어 버린다. 입출력 객체는 자신이 처리하지 못하는 타입에 대해 컴파일 에러를 발생시키므로 훨씬 더 안전하다.

③ 입출력 객체의 <<, >> 연산자는 여러 가지 기본 타입에 대해 중복 정의되어 있는데 필요할 경우 사용자 정의 타입을 인식하도록 확장할 수 있다. 이때 사용되는 기술이 연산자 오버로딩이다. 이 기술을 사용하면 날짜, 시간, 신상 명세 등의 복잡한 정보도 표준 입력 객체로 출력할 수 있다. printf, scanf는 라이브러리가 제공하는 서식만 다룰 수 있는 것과 비교된다.

입출력 객체가 여러 가지 면에서 printf, scanf 보다는 장점이 많은 것이 사실이지만 이 책에서는 앞으로도 printf를 계속 애용할 것이다. 어차피 printf나 cout이나 예제 동작 확인용으로만 사용하는 것이므로 익숙한 방법을 계속 쓰는 것이 좋으며 가독성도 printf가 cout보다 오히려 더 좋다. 또한 C++ 표준이 적용되고 있는 중이라 컴파일러마다 cout을 쓰는 방법이 조금씩 달라 실습에 방해가 되는 점도 고려했다.

- 출처 WIN32 API

by 짱가 updownme 2009.03.16 20:48
| 1 |