https://wikimd.com/index.php?action=history&feed=atom&title=Greedy_algorithmGreedy algorithm - Revision history2026-04-24T09:39:50ZRevision history for this page on the wikiMediaWiki 1.44.2https://wikimd.com/index.php?title=Greedy_algorithm&diff=5888750&oldid=prevPrab: CSV import2024-06-05T21:45:17Z<p>CSV import</p>
<p><b>New page</b></p><div>[[File:_Greedy_algorithm_36_cents.svg|thumb|_Greedy_algorithm_36_cents]] '''Greedy algorithm'''<br />
<br />
A '''greedy algorithm''' is a [[algorithm]]ic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. Greedy algorithms are used for solving [[optimization problem]]s and are known for their simplicity and efficiency. However, they do not always produce the optimal solution for all problems.<br />
<br />
== Characteristics ==<br />
Greedy algorithms follow a problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. The main characteristics of greedy algorithms include:<br />
* **Greedy choice property**: A global optimum can be arrived at by selecting a local optimum.<br />
* **Optimal substructure**: An optimal solution to the problem contains an optimal solution to subproblems.<br />
<br />
== Applications ==<br />
Greedy algorithms are widely used in various fields, including:<br />
* [[Graph theory]]: Algorithms like [[Prim's algorithm]] and [[Kruskal's algorithm]] for finding the [[minimum spanning tree]].<br />
* [[Job scheduling]]: The [[Huffman coding]] algorithm for data compression.<br />
* [[Mathematics]]: The [[Dijkstra's algorithm]] for finding the shortest path in a graph.<br />
* [[Computer science]]: The [[Fractional knapsack problem]].<br />
<br />
== Examples ==<br />
Some well-known examples of greedy algorithms include:<br />
* **Prim's algorithm**: Used to find the minimum spanning tree of a graph.<br />
* **Kruskal's algorithm**: Another algorithm for finding the minimum spanning tree.<br />
* **Dijkstra's algorithm**: Used for finding the shortest path between nodes in a graph.<br />
* **Huffman coding**: Used for lossless data compression.<br />
<br />
== Advantages and Disadvantages ==<br />
=== Advantages ===<br />
* **Simplicity**: Greedy algorithms are often easier to understand and implement.<br />
* **Efficiency**: They can be more efficient in terms of time and space complexity for certain problems.<br />
<br />
=== Disadvantages ===<br />
* **Non-optimal solutions**: Greedy algorithms do not always produce the optimal solution.<br />
* **Problem-specific**: They are not universally applicable and work only for problems with the greedy choice property and optimal substructure.<br />
<br />
== Related Pages ==<br />
* [[Algorithm]]<br />
* [[Optimization problem]]<br />
* [[Graph theory]]<br />
* [[Prim's algorithm]]<br />
* [[Kruskal's algorithm]]<br />
* [[Dijkstra's algorithm]]<br />
* [[Huffman coding]]<br />
* [[Fractional knapsack problem]]<br />
<br />
== See Also ==<br />
* [[Dynamic programming]]<br />
* [[Divide and conquer algorithm]]<br />
* [[Backtracking]]<br />
<br />
{{Algorithm-stub}}<br />
[[Category:Algorithms]]<br />
[[Category:Optimization algorithms and methods]]<br />
[[Category:Graph algorithms]]</div>Prab