Greedy algorithm (original) (raw)
خوارزمية جشعة هي خوارزمية التي تستند على الحدس المهني الذي يتم عن طريقه اختيار الإمكانية الأفضل المرئية في المرحلة الحالية، من دون الأخذ بالحسبان تأثير هذه الخطوة على تكملة الحل. الخوارزميات الجشعة مشهورة في حل مشاكل الاستمثال، حيث يتم عن طريقها محاولة الوصول إلى الجواب الأفضل.
| Property | Value |
|---|---|
| dbo:abstract | خوارزمية جشعة هي خوارزمية التي تستند على الحدس المهني الذي يتم عن طريقه اختيار الإمكانية الأفضل المرئية في المرحلة الحالية، من دون الأخذ بالحسبان تأثير هذه الخطوة على تكملة الحل. الخوارزميات الجشعة مشهورة في حل مشاكل الاستمثال، حيث يتم عن طريقها محاولة الوصول إلى الجواب الأفضل. (ar) En matemàtiques, un algorisme voraç és un algorisme que, per resoldre un problema d'optimització, fa una seqüència d'eleccions, prenent en cada pas un òptim local, amb l'esperança (no sempre complerta) d'arribar a un òptim global. L'algorisme voraç no torna mai enrere per reavaluar les eleccions ja preses. (ca) Hladový algoritmus (anglicky greedy search) je jedním z možných způsobů řešení optimalizačních úloh v matematice a informatice. V každém svém kroku vybírá lokální minimum, přičemž existuje šance, že takto nalezne minimum globální. Hladový algoritmus se uplatní v případě, kdy je třeba z množiny určitých objektů vybrat takovou podmnožinu, která splňuje jistou předem danou vlastnost a navíc má minimální (případně maximální) ohodnocení. Ohodnocení je obvykle reálné číslo w, přiřazené každému objektu dané množiny, ohodnocení množiny A je definováno jako . (cs) Greedy-Algorithmen oder gierige Algorithmen bilden eine spezielle Klasse von Algorithmen in der Informatik. Sie zeichnen sich dadurch aus, dass sie schrittweise den Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis (berechnet durch eine Bewertungsfunktion) verspricht (z. B. Gradientenverfahren). Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal. (de) A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the 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 the submodular structure. (en) Algoritmo irenskorrak hobereneratze-ebazkizun batean, hainbat alditan ebaztekoa dena, aldi bakoitzean optimora gehien hurbiltzen duen aukera edo soluzioa hartzen duen algoritmo bat da, ebazkizunaren erabateko soluzio hoberen edo optimora eramango duelakoan. Algoritmo irenskorraren abantaila bere soluzioa eratzeko duen sinpletasuna da, baina batzuetan soluzio hori benetako optimoa edo soluzio hoberena ez dela du eragozpen. Algoritmo irenskorrak batzuetan soluzio hoberenera eramaten ez duela erakusteko adibide gisa azaltzen da ondorengoa: 6 diru unitateko ordainketa bat egin behar denean, eskura dauden txanponak 1, 3 eta 4 unitatekoak izanik, ordainketa ahalik eta txanpon kopuru txikienarekin egiteko 3 unitateko 2 txanpon erabili behar dira. Algoritmo irenskorrak berriz 4 unitateko txanpon batekin hasiko luke ordainketa, lehenengo aldian ahalik eta gehien ordaintzeko eta ondoren unitate bateko 2 txanpon beharko lituzke, guztira 3 txanpon erabiliz. (eu) En ciencias de la computación, un algoritmo voraz (también conocido como goloso, ávido, devorador o greedy) es una estrategia de búsqueda por la cual se sigue una heurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización. (es) Un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Dans les cas où l'algorithme ne fournit pas systématiquement la solution optimale, il est appelé une heuristique gloutonne. L'illustration ci-contre montre un cas où ce principe est mis en échec. (fr) Un algoritmo greedy è un , dove l'algoritmo cerca una soluzione ammissibile da un punto di vista globale attraverso la scelta della soluzione più appetibile (definita in precedenza dal programmatore) per quel determinato programma a ogni passo locale. Quando applicabili, questi algoritmi consentono di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale, mentre negli altri non è garantita la convergenza all'ottimo globale. In particolare questi algoritmi cercano di mantenere una proprietà di sottostruttura ottima, quindi cercano di risolvere i sottoproblemi in maniera "avida" (da cui la traduzione letterale algoritmi avidi in italiano) considerando una parte definita migliore nell'input per risolvere tutti i problemi. Per fare ciò, solitamente, viene applicata una tecnica cut and paste (quindi scelgo l'input migliore per poter risolvere il sottoproblema). (it) 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다. 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다. 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다. (ko) Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji. Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny, jednak algorytm zachłanny nie zawsze odnajduje rozwiązanie optymalne. (pl) 貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（グリーディさんぽう）ともいう。 (ja) En girig algoritm (en: Greedy algorithm) är en algoritm som alltid tar den bästa vägen ur ett lokalt perspektiv då den letar efter en lösning. För vissa optimeringsproblem hittar den giriga algoritmen en , men för vissa problem kommer den inte att hitta någon garanterat optimal lösning. En egenskap hos en girig algoritm är att den aldrig tar steg tillbaka efter ett gjort val. Exempel på giriga algoritmer: * Dijkstras algoritm * Kruskals algoritm * Prims algoritm (sv) Algoritmo guloso ou míope é técnica de projeto de algoritmos que tenta resolver o problema fazendo a escolha localmente ótima em cada fase com a esperança de encontrar um ótimo global. Na solução de alguns problemas combinatórios a estratégia gulosa pode assegurar a obtenção de soluções ótimas, o que não é muito comum. No entanto, quando o problema a ser resolvido pertencer à classe NP-completo ou NP-difícil, a estratégia gulosa torna-se atrativa para a obtenção de solução aproximada em tempo polinomial. (pt) Жа́дібний алгори́тм (англ. Greedy algorithm) — простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на кожному етапі даних, не зважаючи на можливі наслідки, сподіваючись урешті-решт отримати оптимальний розв'язок. Легкий в реалізації і часто дуже ефективний за часом виконання. Багато задач не можуть бути розв'язані за його допомогою. Наприклад, використання жадібної стратегії для задачі комівояжера породжує такий алгоритм: «На кожному етапі вибирати найближче з невідвіданих міст». (uk) 贪心算法（英語：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。 贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情況，選擇最優的解，可能會導致辛普森悖論（Simpson's Paradox），不一定出現最優的解。 貪心算法在数据科学領域被广泛應用，特別是金融工程。其中一個貪心算法例子就是Ensemble method。 (zh) Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум. Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Greedy_algorithm_36_cents.svg?width=300 |
| dbo:wikiPageExternalLink | http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf https://www.cs.duke.edu/courses/cps296.2/spring07/papers/p634-feige.pdf http://www.oreillynet.com/onlamp/blog/2008/04/python_greedy_coin_changer_alg.html https://books.google.com/books%3Fid=NLngYyWFl_YC&pg=PA370 https://books.google.com/books%3Fid=YxliAgAAQBAJ&pg=PA71 https://ghostarchive.org/archive/20221009/http:/theory.epfl.ch/moranfe/Publications/SODA2014.pdf https://ghostarchive.org/archive/20221009/https:/www.cs.duke.edu/courses/cps296.2/spring07/papers/p634-feige.pdf https://www.researchgate.net/publication/242914003 |
| dbo:wikiPageID | 89247 (xsd:integer) |
| dbo:wikiPageLength | 15788 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123297774 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prim's_algorithm dbr:Algorithm dbc:Matroid_theory dbr:Best-first_search dbr:Vector_spaces dbr:Decision_tree_learning dbr:Independent_set_(graph_theory) dbr:Connected_graph dbr:Geographic_routing dbr:NP-complete dbr:Crystal_Quest dbr:Optimal_substructure dbr:Load_balancing_(computing) dbr:Malfatti_circles dbr:Shortest_path_problem dbr:Steiner_tree_problem dbr:Combinatorial_optimization dbr:Horizon_effect dbr:Kruskal's_algorithm dbr:Multi-armed_bandit dbr:Theoretical_computer_science dbr:Matching_pursuit dbr:Matroid dbc:Greedy_algorithms dbr:Activity_selection_problem dbr:Ad_hoc_network dbr:Admissible_heuristic dbc:Combinatorial_algorithms dbc:Optimization_algorithms_and_methods dbr:Travelling_salesman_problem dbr:Linear_independence dbr:Graph_search dbr:A*_search_algorithm dbr:Dynamic_programming dbc:Exchange_algorithms dbr:Hill_climbing dbr:Mathematical_problem dbr:Artificial_intelligence dbr:Heuristic_(computer_science) dbr:Dijkstra's_algorithm dbr:Distributed_hash_table dbr:Greedy_algorithm_for_Egyptian_fractions dbr:Greedy_coloring dbr:Greedy_source dbr:Huffman_coding dbr:Graph_coloring_problem dbr:Minimum_spanning_tree dbr:Routing dbr:Set_cover_problem dbr:ID3_algorithm dbr:Macintosh_computer dbr:Huffman_tree dbr:Set_cover dbr:Small_world_routing dbr:Submodular dbr:File:Greedy_algorithm_36_cents.svg |
| dbp:caption | Starting 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". (en) 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. (en) |
| dbp:direction | vertical (en) |
| dbp:header | Examples on how a greedy algorithm may fail to achieve the optimal solution. (en) |
| dbp:id | p/g110210 (en) |
| dbp:image | Greedy Glouton.svg (en) Greedy-search-path-example.gif (en) |
| dbp:title | Greedy algorithm (en) |
| dbp:width | 300 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Springer dbt:Authority_control dbt:Cite_book dbt:Cite_journal dbt:Cite_web dbt:Commons_category dbt:Div_col dbt:Div_col_end dbt:Expand_section dbt:Main dbt:More_citations_needed_section dbt:Multiple_image dbt:Portal dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Optimization_algorithms dbt:Algorithmic_paradigms |
| dct:subject | dbc:Matroid_theory dbc:Greedy_algorithms dbc:Combinatorial_algorithms dbc:Optimization_algorithms_and_methods dbc:Exchange_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | owl:Thing dbo:Software yago:WikicatCombinatorialAlgorithms yago:WikicatOptimizationAlgorithmsAndMethods yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatExchangeAlgorithms |
| rdfs:comment | خوارزمية جشعة هي خوارزمية التي تستند على الحدس المهني الذي يتم عن طريقه اختيار الإمكانية الأفضل المرئية في المرحلة الحالية، من دون الأخذ بالحسبان تأثير هذه الخطوة على تكملة الحل. الخوارزميات الجشعة مشهورة في حل مشاكل الاستمثال، حيث يتم عن طريقها محاولة الوصول إلى الجواب الأفضل. (ar) En matemàtiques, un algorisme voraç és un algorisme que, per resoldre un problema d'optimització, fa una seqüència d'eleccions, prenent en cada pas un òptim local, amb l'esperança (no sempre complerta) d'arribar a un òptim global. L'algorisme voraç no torna mai enrere per reavaluar les eleccions ja preses. (ca) Hladový algoritmus (anglicky greedy search) je jedním z možných způsobů řešení optimalizačních úloh v matematice a informatice. V každém svém kroku vybírá lokální minimum, přičemž existuje šance, že takto nalezne minimum globální. Hladový algoritmus se uplatní v případě, kdy je třeba z množiny určitých objektů vybrat takovou podmnožinu, která splňuje jistou předem danou vlastnost a navíc má minimální (případně maximální) ohodnocení. Ohodnocení je obvykle reálné číslo w, přiřazené každému objektu dané množiny, ohodnocení množiny A je definováno jako . (cs) Greedy-Algorithmen oder gierige Algorithmen bilden eine spezielle Klasse von Algorithmen in der Informatik. Sie zeichnen sich dadurch aus, dass sie schrittweise den Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis (berechnet durch eine Bewertungsfunktion) verspricht (z. B. Gradientenverfahren). Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal. (de) En ciencias de la computación, un algoritmo voraz (también conocido como goloso, ávido, devorador o greedy) es una estrategia de búsqueda por la cual se sigue una heurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización. (es) 貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（グリーディさんぽう）ともいう。 (ja) En girig algoritm (en: Greedy algorithm) är en algoritm som alltid tar den bästa vägen ur ett lokalt perspektiv då den letar efter en lösning. För vissa optimeringsproblem hittar den giriga algoritmen en , men för vissa problem kommer den inte att hitta någon garanterat optimal lösning. En egenskap hos en girig algoritm är att den aldrig tar steg tillbaka efter ett gjort val. Exempel på giriga algoritmer: * Dijkstras algoritm * Kruskals algoritm * Prims algoritm (sv) Algoritmo guloso ou míope é técnica de projeto de algoritmos que tenta resolver o problema fazendo a escolha localmente ótima em cada fase com a esperança de encontrar um ótimo global. Na solução de alguns problemas combinatórios a estratégia gulosa pode assegurar a obtenção de soluções ótimas, o que não é muito comum. No entanto, quando o problema a ser resolvido pertencer à classe NP-completo ou NP-difícil, a estratégia gulosa torna-se atrativa para a obtenção de solução aproximada em tempo polinomial. (pt) Жа́дібний алгори́тм (англ. Greedy algorithm) — простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на кожному етапі даних, не зважаючи на можливі наслідки, сподіваючись урешті-решт отримати оптимальний розв'язок. Легкий в реалізації і часто дуже ефективний за часом виконання. Багато задач не можуть бути розв'язані за його допомогою. Наприклад, використання жадібної стратегії для задачі комівояжера породжує такий алгоритм: «На кожному етапі вибирати найближче з невідвіданих міст». (uk) 贪心算法（英語：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。 贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情況，選擇最優的解，可能會導致辛普森悖論（Simpson's Paradox），不一定出現最優的解。 貪心算法在数据科学領域被广泛應用，特別是金融工程。其中一個貪心算法例子就是Ensemble method。 (zh) Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум. Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование. (ru) A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. (en) Algoritmo irenskorrak hobereneratze-ebazkizun batean, hainbat alditan ebaztekoa dena, aldi bakoitzean optimora gehien hurbiltzen duen aukera edo soluzioa hartzen duen algoritmo bat da, ebazkizunaren erabateko soluzio hoberen edo optimora eramango duelakoan. Algoritmo irenskorraren abantaila bere soluzioa eratzeko duen sinpletasuna da, baina batzuetan soluzio hori benetako optimoa edo soluzio hoberena ez dela du eragozpen. (eu) Un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global. (fr) Un algoritmo greedy è un , dove l'algoritmo cerca una soluzione ammissibile da un punto di vista globale attraverso la scelta della soluzione più appetibile (definita in precedenza dal programmatore) per quel determinato programma a ogni passo locale. Quando applicabili, questi algoritmi consentono di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale, mentre negli altri non è garantita la convergenza all'ottimo globale. In particolare questi algoritmi cercano di mantenere una proprietà di sottostruttura ottima, quindi cercano di risolvere i sottoproblemi in maniera "avida" (da cui la traduzione letterale algoritmi avidi in italiano) considerando una parte definita migliore nell'input per risolvere tutti i problemi. (it) 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다. 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다. (ko) Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji. (pl) |
| rdfs:label | خوارزمية جشعة (ar) Algorisme voraç (ca) Hladový algoritmus (cs) Greedy-Algorithmus (de) Greedy algorithm (en) Algoritmo voraz (es) Algoritmo irenskor (eu) Algorithme glouton (fr) Algoritmo greedy (it) 탐욕 알고리즘 (ko) 貪欲法 (ja) Algorytm zachłanny (pl) Algoritmo guloso (pt) Жадный алгоритм (ru) Girig algoritm (sv) 贪心算法 (zh) Жадібний алгоритм (uk) |
| owl:sameAs | freebase:Greedy algorithm yago-res:Greedy algorithm wikidata:Greedy algorithm dbpedia-ar:Greedy algorithm dbpedia-az:Greedy algorithm dbpedia-ca:Greedy algorithm dbpedia-cs:Greedy algorithm dbpedia-da:Greedy algorithm dbpedia-de:Greedy algorithm dbpedia-es:Greedy algorithm dbpedia-eu:Greedy algorithm dbpedia-fa:Greedy algorithm dbpedia-fi:Greedy algorithm dbpedia-fr:Greedy algorithm dbpedia-he:Greedy algorithm dbpedia-hu:Greedy algorithm dbpedia-it:Greedy algorithm dbpedia-ja:Greedy algorithm dbpedia-ko:Greedy algorithm http://mn.dbpedia.org/resource/Шуналтай_алгоритм dbpedia-no:Greedy algorithm dbpedia-pl:Greedy algorithm dbpedia-pt:Greedy algorithm dbpedia-ro:Greedy algorithm dbpedia-ru:Greedy algorithm dbpedia-simple:Greedy algorithm dbpedia-sk:Greedy algorithm dbpedia-sl:Greedy algorithm dbpedia-sr:Greedy algorithm dbpedia-sv:Greedy algorithm dbpedia-th:Greedy algorithm dbpedia-uk:Greedy algorithm dbpedia-vi:Greedy algorithm dbpedia-zh:Greedy algorithm https://global.dbpedia.org/id/4gRC1 |
| prov:wasDerivedFrom | wikipedia-en:Greedy_algorithm?oldid=1123297774&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Greedy-search-path-example.gif wiki-commons:Special:FilePath/Greedy_Glouton.svg wiki-commons:Special:FilePath/Greedy_algorithm_36_cents.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Greedy_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Greed_(disambiguation) dbr:Greedy |
| is dbo:wikiPageRedirects of | dbr:Applications_of_greedy_algorithms dbr:Greedy_Algorithm dbr:Greedy_algorithms dbr:Greedy_heuristic dbr:Greedy_method dbr:Greedy_search dbr:Exchange_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Beam_search dbr:Prim's_algorithm dbr:Merkle–Hellman_knapsack_cryptosystem dbr:MaMF dbr:Metric_k-center dbr:Participatory_budgeting_algorithm dbr:1926_in_science dbr:Bell_Labs dbr:Bellman–Ford_algorithm dbr:Algorithm dbr:Algorithmic_paradigm dbr:Algorithmic_technique dbr:Antimatroid dbr:Approximation_algorithm dbr:Best-first_search dbr:Patience_sorting dbr:Regular_expression dbr:Reverse-delete_algorithm dbr:Charging_argument dbr:Cycle_basis dbr:Vehicle_routing_problem dbr:De_novo_sequence_assemblers dbr:Decision_tree_learning dbr:Deep_belief_network dbr:Deep_learning dbr:Independence_Theory_in_Combinatorics dbr:Independent_set_(graph_theory) dbr:Information_fuzzy_networks dbr:Instruction_selection dbr:Interval_scheduling dbr:Introduction_to_the_Theory_of_Error-Correcting_Codes dbr:Pseudoforest dbr:Matching_(graph_theory) dbr:Matroid_parity_problem dbr:Maximum_disjoint_set dbr:Geometric_set_cover_problem dbr:Geometry_of_binary_search_trees dbr:Online_algorithm dbr:Online_analytical_processing dbr:Online_machine_learning dbr:Weighted_matroid dbr:Rado_graph dbr:Clique_problem dbr:Glossary_of_graph_theory dbr:Grammar_induction dbr:Graph_coloring dbr:Continuous_knapsack_problem dbr:Contraction_hierarchies dbr:Convolutional_deep_belief_network dbr:Cooperative_game_theory dbr:Cop-win_graph dbr:Optimal_binary_search_tree dbr:Optimal_substructure dbr:Applications_of_greedy_algorithms dbr:Malfatti_circles dbr:Simulated_annealing dbr:Combinatorial_number_system dbr:Zeckendorf's_theorem dbr:Feature_learning dbr:Feature_selection dbr:Feedback_arc_set dbr:Horizon_effect dbr:Howard_Eves dbr:Kernighan–Lin_algorithm dbr:Kruskal's_algorithm dbr:Kruskal–Katona_theorem dbr:Multi-armed_bandit dbr:Parsing_expression_grammar dbr:Plateau_effect dbr:Proper_generalized_decomposition dbr:Matching_pursuit dbr:Matroid dbr:Matroid-constrained_number_partitioning dbr:Matroid_embedding dbr:Matroid_oracle dbr:Maximum_coverage_problem dbr:Brown_clustering dbr:Bucket_queue dbr:Activity_selection_problem dbr:Travelling_salesman_problem dbr:Václav_Chvátal dbr:K-medoids dbr:Layered_graph_drawing dbr:Line_wrap_and_word_wrap dbr:Linear_programming_relaxation dbr:Link-state_routing_protocol dbr:Local_search_(constraint_satisfaction) dbr:Greedy_Algorithm dbr:Min-conflicts_algorithm dbr:Package-merge_algorithm dbr:Minimum_k-cut dbr:Oriented_matroid dbr:A*_search_algorithm dbr:Alias_method dbr:Fibonacci_nim dbr:No-three-in-line_problem dbr:Non-integer_base_of_numeration dbr:Numbers_(season_3) dbr:Parallel_metaheuristic dbr:Discrete_tomography dbr:Farthest-first_traversal dbr:Ford–Fulkerson_algorithm dbr:Goldbach's_conjecture dbr:Gradient_boosting dbr:Graph_cuts_in_computer_vision dbr:Graph_traversal dbr:Hill_climbing dbr:Knowledge_space dbr:Komornik–Loreti_constant dbr:Greed_(disambiguation) dbr:Greedy dbr:Quadratic_knapsack_problem dbr:Rearrangement_inequality dbr:TeX dbr:Small-world_routing dbr:Stanley_sequence dbr:Birkhoff_algorithm dbr:Blow-up_lemma dbr:Eight_queens_puzzle dbr:Heuristic_(computer_science) dbr:Hierarchical_clustering dbr:Polygon_triangulation dbr:SUBCLU dbr:Dijkstra's_algorithm dbr:Distributed_hash_table dbr:Automatic_label_placement dbr:Automatic_summarization dbr:Borůvka's_algorithm dbr:Square-difference-free_set dbr:Circuit_rank dbr:Freiman's_theorem dbr:Greedoid dbr:Greedy_Perimeter_Stateless_Routing_in_Wireless_Networks dbr:Greedy_algorithm_for_Egyptian_fractions dbr:Greedy_coloring dbr:Greedy_embedding dbr:Greedy_geometric_spanner dbr:Greedy_number_partitioning dbr:Greedy_randomized_adaptive_search_procedure dbr:Greedy_triangulation dbr:Huffman_coding dbr:Greedy_algorithms dbr:Greedy_heuristic dbr:Greedy_method dbr:Greedy_search dbr:Metric_dimension_(graph_theory) dbr:Minimum_spanning_tree dbr:Neighbor_joining dbr:Odd_greedy_expansion dbr:Cantor's_isomorphism_theorem dbr:Capacitated_minimum_spanning_tree dbr:Change-making_problem dbr:Knapsack_problem dbr:Seam_carving dbr:Longest-processing-time-first_scheduling dbr:Set_cover_problem dbr:Structure_mapping_engine dbr:Nearest-neighbor_chain_algorithm dbr:Tyranny_of_small_decisions dbr:Factor-critical_graph dbr:ID3_algorithm dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Robert_C._Prim dbr:Event_monitoring dbr:NOR_flash_replacement dbr:Vertex_k-center_problem dbr:Multivariate_adaptive_regression_spline dbr:Pillai_sequence dbr:Sequence_clustering dbr:Packing_in_a_hypergraph dbr:Robbins'_theorem dbr:SGI_algorithm dbr:Outline_of_combinatorics dbr:Outline_of_computer_programming dbr:Small-world_experiment dbr:Random_graph dbr:United_States_of_America_Computing_Olympiad dbr:Take-the-best_heuristic dbr:Types_of_artificial_neural_networks dbr:Submodular_set_function dbr:Sussman_anomaly dbr:Exchange_algorithm |
| is dbp:class of | dbr:Dijkstra's_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Greedy_algorithm |
