похлепни алгоритам

Uses your system voice; voice and rate in settings.

The name shown is in sr. The article below is in English and is not a translation.

Q504353Snapshot

≈ 12 min read

Names in other languages

  • ไทยขั้นตอนวิธีแบบละโมบGreedy algorithm, อัลกอริทึมเชิงละโมบ
  • Tiếng ViệtGiải thuật tham lamThuật toán tham lam
  • Češtinahladový algoritmus
  • DeutschGreedy-AlgorithmusGreedy-Algorithmen, gieriger Algorithmus, greedy Algorithmus
  • euAlgoritmo irenskor
  • Françaisalgorithme gloutonméthode gloutonne
  • glalgoritmo cobizosoalgoritmo guloso
  • Polskialgorytm zachłanny
  • skPažravý algoritmusHladný algoritmus, Greedy algoritmus
  • Српскипохлепни алгоритамПохлепни алгоритми
  • Српскипохлепни алгоритам
  • Српскиpohlepni algoritam
  • mnШуналтай алгоритм
  • Українськажадібний алгоритм
  • dagrådig algoritme
  • Englishgreedy algorithm
  • فارسیالگوریتم حریصانه
  • Italianoalgoritmo greedy
  • nbgrådig algoritme
  • Nederlandsgreedy algorithm
  • Portuguêsalgoritmo gulosoalgoritmos gulosos, algoritmo ganancioso
  • caalgorisme voraç
  • eoavida algoritmo
  • Españolalgoritmo vorazestrategia voraz, algoritmo avido, algoritmos voraces, algoritmo ávido, algoritmo greedy
  • Magyarmohó algoritmus
  • Bahasa Indonesiaalgoritma tamakAlgoritma rakus, Algoritma serakah
  • mkлаком алгоритам
  • Românăalgoritm greedymetodă lacomă, algoritm lacom
  • Русскийжадный алгоритмЖА, жадные алгоритмы
  • slPožrešna metoda
  • azAcgöz alqoritm
  • fiahne algoritmi
  • Svenskagirig algoritmThe greedy method, Den giriga algoritmen, Giriga metoden, Den giriga metoden
  • العربيةخوارزمية جشعة
  • עבריתאלגוריתם חמדןאלגוריתם חמדני
  • 한국어탐욕 알고리즘욕심쟁이 방법, 탐욕적 알고리즘, 그리디 알고리즘
  • yue貪心演算法
  • 日本語貪欲法グリーディ算法, 貪欲アルゴリズム, 欲張り法
  • 中文贪心法貪心演算法, 貪婪演算法, 貪進法, 貪心法, 饕餮法
  • 简体中文贪心法
  • 繁體中文貪心法
  • 中文貪心法

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A greedy algorithm is an algorithm which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices. Greedy algorithms are often used to solve combinatorial optimization problems. If an optimization problem only depends on the partial solution of solving it for one subproblem, we can solve this problem by "greedily" considering only the locally optimal subproblem. In this sense, a greedy algorithm is a special case of a dynamic programming algorithm. Uriel Feige[1] notes that:

[Greedy algorithms] may be viewed as the ultimate form of dynamic programming, in which only one partial solution is maintained. The problem needs to have much more structure for this approach to work.

In many cases, a greedy algorithm does not produce an exact solution, but can yield solutions that approximate an exact solution in a reasonable amount of time.[2]

An example of a problem which admits an exact greedy solution, the activity selection problem. Given a collection of tasks which can be done between allotted time intervals, the problem is to determine the maximum number of tasks that can be done. A greedy algorithm in O(nlog⁡(n)) which solves this problem sorts the tasks by the end time and then repeatedly chooses the first task that begins after the last task ended.

Many classic algorithms in computer science such as the Huffman coding algorithm, Prim's algorithm, Kruskal's algorithm, and Dijkstra's algorithm all use greedy properties in their design. Mathematicians frequently use greedy strategies in proofs as well. A classic example is what Raphael Yuster refers to as the greedy proof[3] that every tournament contains a Hamiltonian path.

Characterizations

edit edit source

Since there is no formal definition of what a greedy algorithm is,[4] a complete characterization of when a problem admits a greedy algorithm as a solution is not known. However, special cases have been identified. Jack Edmonds showed that a greedy algorithm can be used to solve a class of linear combinatorial optimization problems with a matroid structure.[5]

Later Bernhard Korte and László Lovász characterized a broader class of optimization problems by introducing the notion of a greedoid. This allowed, for example, a proof of the optimality of Prim's algorithm.

Algorithms which undo past steps are not greedy. For example, the Gale-Shapley algorithm is not a greedy algorithm since although it constructs a solution by choosing the current best pairing, in the process, existing solutions may be modified.

Correctness

edit edit source

One technique used to prove the optimality of greedy algorithms is an exchange argument.[6] The exchange argument demonstrates that any solution different from the greedy solution is at most as good as the greedy solution. This proof pattern typically follows these steps:

  1. Assume there exists an optimal solution different from the greedy solution.
  2. Consider the first point where the optimal and greedy solutions differ.
  3. Prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the optimal solution.
  4. Conclude by induction that the greedy solution is optimal.
Examples of how a greedy algorithm may fail to achieve the optimal solutionStarting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M".To reach the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.

Further examples

edit edit source
  • In the fractional knapsack problem, one is given a list of items with weights and values. The goal is to choose fractional amounts of each item such that the total value is maximised, and the weight is below a fixed constraint. Unlike the knapsack problem, which is known to be NP-hard, the fractional knapsack problem admits a polynomial time greedy algorithm.
  • Instances of the Frobenius coin problem admit greedy solutions. However, in some cases the greedy algorithm does not yield an optimal solution.[7]
  • The matching pursuit is an example of a greedy algorithm applied on signal approximation.
  • A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a given triangle that maximize the total area of the circles; it is conjectured that the same greedy algorithm is optimal for any number of circles.
  • In decision tree learning, greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.
    • One popular such algorithm is the ID3 algorithm for decision tree construction.
  • A greedy algorithm constructs the Zeckendorf representation (or Fibonacci coding) of a natural number. Subtracting the largest Fibonacci number less than or equal to the natural number repeatedly gives its Zecekndorf representation. The greedy algorithm is extracted from the existence proof of the Zeckendorf representation. The uniqueness of the Zeckendorf representation guarantees that no other non-consecutive Fibonacci sum can give a different output.
  • Fibonacci described a greedy algorithm for computing Egyptian fractions.
  • Greedy algorithms appear in network routing. Using greedy routing, a message is forwarded to the neighbouring 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.

Greedy algorithms on graphs

edit edit source

Graph theory is a rich source of greedy algorithms. Computing scientists frequently use greedy algorithms to compute graph invariants.

Greedy algorithms are also used to find upper bounds for the chromatic numbers[8]. A simple example is the bound χ(G)≤Δ(G)+1 obtained by a greedy algorithm.[9] We begin by taking a vertex that has not been colored. Since it has at most Δ(G) neighbours, at most Δ(G) colors are used in adjacent vertices, leaving a color free for the vertex under consideration.

Greedy approximation algorithms

edit edit source

A solution to the NP-complete travelling salesman problem can be approximated by starting from an empty edge set and then adding the next cheapest edge which is a subgraph of a complete tour. This greedy algorithm has been proven to yield at most Θ(log⁡n) times longer than the optimal tour.[10]

Another example is that a solution for the 0-1 knapsack problem can be approximated by using the greedy algorithm for the fractional knapsack problem. This greedy algorithm has been proven to yield a solution at least half the value of the optimal solution.[11]

Solutions for submodular maximization are approximated using a greedy algorithm which yields a solution at least half the value of the optimal solution.[12]

Problems for which greedy algorithms are used to provide approximation algorithms include the set cover, load balancing, Steiner tree and independent set[13] problem.

See also

edit edit source

References

edit edit source
  1. ^ Feige, Uriel. "Greedy algorithms and Matroids" (PDF). Department of Computer Science and Applied Mathematics, Weizmann Institute of Science. Retrieved 30 April 2026.
  2. ^ van Melkebeek, Dieter. "Greedy Approximations" (PDF). University of Wisconsin–Madison. Retrieved 2025-07-25.
  3. ^ Yuster, Raphael (January 2021). "Paths with many shortcuts in tournaments". Discrete Mathematics. 344 (1) 112168. arXiv:2009.13985. doi:10.1016/j.disc.2020.112168.
  4. ^ "Lecture 1 – Basics and Greedy Algorithms" (PDF). KTH Social. KTH Royal Institute of Technology. Retrieved 30 April 2026.
  5. ^ Edmonds, Jack (December 1971). "Matroids and the greedy algorithm". Mathematical Programming. 1 (1): 127–136. doi:10.1007/BF01584082. ISSN 0025-5610.
  6. ^ Erickson, Jeff (2019). "Greedy Algorithms". Algorithms. University of Illinois at Urbana-Champaign.
  7. ^ Gupta, Shreya; Huang, Boyang; Impagliazzo, Russell (2024-11-27), The Greedy Coin Change Problem, arXiv:2411.18137
  8. ^ Campos, Victor; Gyárfás, András; Havet, Frédéric; Linhares Sales, Claudia; Maffray, Frédéric (April 2010). New bounds on the Grundy number of products of graphs (Technical report). INRIA. RR-7243.
  9. ^ Diestel, Reinhard (2025). Graph Theory. Graduate Texts in Mathematics (Sixth Edition 2025 ed.). Erscheinungsort nicht ermittelbar: Springer. ISBN 978-3-662-70106-5.
  10. ^ Brecklinghaus, Judith; Hougardy, Stefan (2015-05-01). "The approximation ratio of the greedy algorithm for the metric traveling salesman problem". Operations Research Letters. 43 (3): 259–261. doi:10.1016/j.orl.2015.02.009. ISSN 0167-6377.
  11. ^ Nelson, Jelani (March 7, 2017). "Lecture 13: PTAS/FPTAS/FPRAS examples; Approximation algorithms via SDP" (PDF). CS 224: Advanced Algorithms, Spring 2017. Scribe: Hongyao Ma. Harvard University. Retrieved May 1, 2026.
  12. ^ Grimsman, David; Hespanha, Joao P.; Marden, Jason R. (December 17–19, 2018). Strategic Information Sharing in Greedy Submodular Maximization. IEEE Conference on Decision and Control. Miami, Fla.: IEEE. pp. 2722–2727. doi:10.1109/CDC.2018.8619166. ISBN 978-1-5386-1395-5.
  13. ^ "Lecture 5: Introduction to Approximation Algorithms" (PDF). Advanced Algorithms (2IL45) — Course Notes. TU Eindhoven. Archived (PDF) from the original on 2022-10-09.

Sources

edit edit source edit edit source Wikimedia Commons has media related to Greedy algorithms. Optimization: Algorithms, methods, and heuristics Hessians Network flows Data structures and algorithmsData structures Algorithms and algorithmic paradigms InternationalNational

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376013393 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot greedy-algorithm-058053-d6bb41bc04217a31 · hash d6bb41bc04217a313c9d9b20f9abd40a089cf613e9a07269a87c89e6e5a5967f · captured 1789990870.0 · version history

Cite this page as: encyclopegia.org, “похлепни алгоритам”, snapshot greedy-algorithm-058053-d6bb41bc04217a31. https://encyclopegia.org/a/greedy-algorithm