A greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimal choice at each stage

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • A greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimal choice at each stage
  • Greedy-Algorithmen oder gierige Algorithmen bilden eine spezielle Klasse von Algorithmen, die in der Informatik auftreten. 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 verspricht. Um unter den Folgezuständen eine Auswahl zu treffen, wird oft eine Bewertungsfunktion verwendet. Greedy-Algorithmen sind meist schnell, lösen viele Probleme aber nicht optimal.
  • Hladový algoritmus 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 <math>\mathit{w(A)} = \sum_{a \in A} w(a)</math>.
  • Un algoritmo voraz (también conocido como ávido o devorador) es aquel que, para resolver un determinado problema, sigue una metaheurí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.
  • Ahne algoritmi tarkoittaa algoritmia, joka pyrkii ratkaisemaan optimointiongelman tekemällä aina kussakin tilassa optimaalisen päätöksen. Esimerkiksi Kauppamatkustajan ongelmaan sovellettu ahne algoritmi kuuluisi näin: "Seuraavaksi vieraile lähimmässä sellaisessa kaupungissa, jossa et ole vielä käynyt. " Ahneet algoritmit eivät yleensä löydä parasta ratkaisua ongelmaan, mutta ne ovat yksinkertaisia soveltaa ja ne löytävät ratkaisuja, jotka ovat samaa suuruusluokkaa parhaan ratkaisun kanssa.
  • Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l'espoir 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.
  • Mohó algoritmussal meghatározható a legkevesebb pénzérme, amivel ki lehet az aprót fizetni. A legnagyobb értékű érme, amivel ki lehet fizetni a megmaradt összeget, a helyi optimum. A mohó algoritmus vagy greedy algoritmus az a problémamegoldó algoritmus, amely helyi optimumok megvalósításával próbálja megtalálni a globális optimumot. Ez például az utazó ügynök problémájaként ismert feladatban azt jelenti, hogy minden állomásról a legközelebbi, addig még nem látogatott városba fog utazni az ügynök. Általánosan öt pillérre támaszkodik: egy halmazból veszi a jelölteket, amelyekkel felállítja a megoldáshalmazt egy kiválasztó függvény, amely a legjobb jelöltet választja ki a megoldás reményében egy lehetőségvizsgáló függvény, amely megnézi, hogy egy jelölt alkalmas-e a megoldásra egy célfüggvény, amely egy értéket megoldásnak, vagy részleges megoldásnak jelöl egy megoldásfüggvény, amely jelzi, ha megtaláltuk a teljes megoldást. A módszer jól alkalmazható néhány matematikai probléma megoldásában, de nem garantálja sok probléma megoldását.
  • Un algoritmo greedy è un algoritmo che cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più golosa (aggressiva o avida, a seconda della traduzione preferita del termine greedy dall'inglese) ad ogni passo locale. Questa tecnica consente, dove applicabile (infatti non sempre si arriva ad una soluzione ottima), di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale (cfr. Problemi NP-Completi, cioè problemi di soluzione non deterministica polinomiale).
  • 貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（-さんぽう）ともいう。
  • En grådig algoritme er en algoritme som hele tiden velger det som ser best ut i øyeblikket. For eksempel kan problemet med å gi tilbake vekslepenger løses med en grådig algoritme. For å gi tilbake færrest mulig mynter, er det best å hele tiden gi tilbake mynter med størst mulig verdi. 46 kr = 20 kr + 20 kr + 5 kr + 1 kr = 4 mynter. Kjennetegnet for en grådig algoritme, er at det ikke går an å endre valgene som allerede er gjort. I eksempelet med vekslepenger, betyr det at algoritmen må velge å gi ut 20 kr, uten å vite om det finnes en god måte å gi ut de resterende 26 kr på. Grådige algoritmer er som regel raske, men de gir ikke alltid riktig svar. Anta det finnes en mynt med verdien 16 kr. Da vil det være optimalt å gi tilbake 20 kr + 16 kr + 10 kr = 3 mynter. Dermed er det i mange tilfeller nødvendig å bruke dynamisk programmering for å kunne prøve ut flere forskjellige valg parallelt. Andre eksempler hvor grådige algoritmer er nyttige, er i en vektet graf å bruke Prims algoritme for å finne minste spenntre og Dijkstras algoritme for å finne korteste vei. Ofte er det også nok å finne en god løsning, som ikke trenger å være optimal. Grådige algoritmer kan da ofte gi tilnærmingsløsninger på relativt kort tid.
  • Algorytm zachłanny – 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 patrzy 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. W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".
  • Algoritmo guloso, ou ganancioso, é uma técnica de algoritmos para resolver problemas de otimização, sempre realizando a escolha que parece ser a melhor no momento; fazendo uma escolha ótima local, na esperança de que esta escolha leve até a solução ótima global. Vantagens: Algoritmos simples e de fácil implementação. Desvantagens: Nem sempre conduz à soluções ótimas globais. Podem efetuar cálculos repetitivos.
  • Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование.
  • Girig algoritm, 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 så hittar den giriga algoritmen en optimal lösning, men för vissa problem kommer den inte att hitta någon garanterat optimal lösning. Exempel på giriga algoritmer: Dijkstras algoritm Kruskals algoritm Prims algoritm
  • 贪心法（ Greedy algorithm ，直譯：貪心演算法） 是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。 贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
dbpprop:hasPhotoCollection
dbpprop:reference
dbpprop:relatedInstance
rdf:type
rdfs:comment
  • A greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimal choice at each stage
  • Greedy-Algorithmen oder gierige Algorithmen bilden eine spezielle Klasse von Algorithmen, die in der Informatik auftreten. 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 verspricht. Um unter den Folgezuständen eine Auswahl zu treffen, wird oft eine Bewertungsfunktion verwendet. Greedy-Algorithmen sind meist schnell, lösen viele Probleme aber nicht optimal.
  • Hladový algoritmus 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í.
  • Un algoritmo voraz (también conocido como ávido o devorador) es aquel que, para resolver un determinado problema, sigue una metaheurí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.
  • Ahne algoritmi tarkoittaa algoritmia, joka pyrkii ratkaisemaan optimointiongelman tekemällä aina kussakin tilassa optimaalisen päätöksen. Esimerkiksi Kauppamatkustajan ongelmaan sovellettu ahne algoritmi kuuluisi näin: "Seuraavaksi vieraile lähimmässä sellaisessa kaupungissa, jossa et ole vielä käynyt.
  • Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l'espoir 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.
  • Mohó algoritmussal meghatározható a legkevesebb pénzérme, amivel ki lehet az aprót fizetni. A legnagyobb értékű érme, amivel ki lehet fizetni a megmaradt összeget, a helyi optimum. A mohó algoritmus vagy greedy algoritmus az a problémamegoldó algoritmus, amely helyi optimumok megvalósításával próbálja megtalálni a globális optimumot.
  • Un algoritmo greedy è un algoritmo che cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più golosa (aggressiva o avida, a seconda della traduzione preferita del termine greedy dall'inglese) ad ogni passo locale. Questa tecnica consente, dove applicabile (infatti non sempre si arriva ad una soluzione ottima), di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale (cfr.
  • 貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（-さんぽう）ともいう。
  • En grådig algoritme er en algoritme som hele tiden velger det som ser best ut i øyeblikket. For eksempel kan problemet med å gi tilbake vekslepenger løses med en grådig algoritme. For å gi tilbake færrest mulig mynter, er det best å hele tiden gi tilbake mynter med størst mulig verdi. 46 kr = 20 kr + 20 kr + 5 kr + 1 kr = 4 mynter. Kjennetegnet for en grådig algoritme, er at det ikke går an å endre valgene som allerede er gjort.
  • Algorytm zachłanny – 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 patrzy 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.
  • Algoritmo guloso, ou ganancioso, é uma técnica de algoritmos para resolver problemas de otimização, sempre realizando a escolha que parece ser a melhor no momento; fazendo uma escolha ótima local, na esperança de que esta escolha leve até a solução ótima global. Vantagens: Algoritmos simples e de fácil implementação. Desvantagens: Nem sempre conduz à soluções ótimas globais. Podem efetuar cálculos repetitivos.
  • Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.
  • Girig algoritm, 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 så hittar den giriga algoritmen en optimal lösning, men för vissa problem kommer den inte att hitta någon garanterat optimal lösning. Exempel på giriga algoritmer: Dijkstras algoritm Kruskals algoritm Prims algoritm
rdfs:label
  • Greedy algorithm
  • Greedy-Algorithmus
  • Hladový algoritmus
  • Algoritmo voraz
  • Ahne algoritmi
  • Algorithme glouton
  • Mohó algoritmus
  • Algoritmo greedy
  • 貪欲法
  • Grådig algoritme
  • Algorytm zachłanny
  • Algoritmo guloso
  • Жадный алгоритм
  • Girig algoritm
  • 贪心法
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of
is owl:sameAs of