Greedy algorithm (nonfiction): Difference between revisions

From Gnomon Chronicles
Jump to navigation Jump to search
(Created page with "File:Greedy_algorithm_36_cents.svg|thumb|Greedy algorithms determine minimum number of coins to give while making change. These are the steps a human would take to emulate a...")
 
 
(3 intermediate revisions by the same user not shown)
Line 6: Line 6:


<gallery>
<gallery>
File:APTO logo.jpg|link=Algorithmic Paradigm Treaty Organization|January 10, 2018: The [[Algorithmic Paradigm Treaty Organization]] (APTO) files [[Crimes against mathematical constants|math crime charges]] against greedy algorithms.
File:Greedy colorings.svg|link=Greedy coloring (nonfiction)|September 4, 1973: An experimental graph coloring model accidentally generates a [[Greedy coloring (nonfiction)|Greedy coloring]] computer virus which causes the color [[Green (nonfiction)|green]] to become [[Red (nonfiction)|red]] in the vicinity of every computer terminal around the world. The virus will be eliminated several hours later by [[Algorithmic Paradigm Treaty Organization|APTO]] troubleshooters, restoring [[Green (nonfiction)|green]] to its normal appearance.
</gallery>
</gallery>


Line 24: Line 26:
External links:
External links:


* [https://en.wikipedia.org/wiki/Greedy_coloring Greedy coloring] @ Wikipedia
* [https://en.wikipedia.org/wiki/Greedy_algorithm Greedy algorithm] @ Wikipedia


[[Category:Nonfiction (nonfiction)]]
[[Category:Nonfiction (nonfiction)]]
[[Category:Algorithms (nonfiction)]]
[[Category:Algorithms (nonfiction)]]
[[Category:Mathematicians (nonfiction)]]
[[Category:Mathematicians (nonfiction)]]

Latest revision as of 11:38, 3 September 2018

Greedy algorithms determine minimum number of coins to give while making change. These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}. The coin of the highest value, less than the remaining change owed, is the local optimum. (In general the change-making problem requires dynamic programming to find an optimal solution; however, most currency systems, including the Euro and US Dollar, are special cases where the greedy strategy does find an optimal solution.)

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic doesn't intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximations to optimization problems with submodular structure.

In the News

Fiction cross-reference

Nonfiction cross-reference

External links: