| 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)
|
| 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)
|
