Algoritmo voraz

Un algoritmo voraz determina el mínimo número de monedas que debe devolverse en el cambio. En la figura se muestran los pasos que un ser humano debería seguir para emular a un algoritmo voraz para acumular 36 céntimos usando solamente monedas de valores nominales de 1, 5, 10 y 20. La moneda del mayor valor menor que el resto debido es el óptimo local en cada paso. Nótese que en general el problema de devolución del cambio requiere programación dinámica o programación lineal para encontrar una solución óptima. Sin embargo, muchos sistemas monetarios, incluyendo el euro y el dólar estadounidense, son casos especiales donde la estrategia del algoritmo voraz da con la solución óptima.

En ciencias de la computación, un algoritmo voraz (también conocido como codicioso, 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.

Esquema

Dado un conjunto finito de entradas , un algoritmo voraz devuelve un conjunto (seleccionados) tal que y que además cumple con las restricciones del problema inicial. A cada conjunto que satisfaga las restricciones se le suele denominar prometedor, y si este además logra que la función objetivo se minimice o maximice (según corresponda) diremos que es una solución óptima.

Características

Se utilizan generalmente para resolver problemas de optimización (obtener el máximo o el mínimo). Toman decisiones en función de la información que está disponible en cada momento. Una vez tomada la decisión, ésta no vuelve a replantearse en el futuro. Suelen ser rápidos y fáciles de implementar. No siempre garantizan alcanzar la solución óptima.

El enfoque “greedy” no nos garantiza obtener soluciones óptimas. Por lo tanto, siempre habrá que estudiar la corrección del algoritmo para demostrar si las soluciones obtenidas son óptimas o no.

Elementos de los que consta la técnica

  • El conjunto de candidatos, entradas del problema.
  • Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos forma una solución (no importa si es óptima o no lo es).
  • Función de selección. Informa cuál es el elemento más prometedor para completar la solución. Este no puede haber sido escogido con anterioridad. Cada elemento es considerado una sola vez. Luego, puede ser rechazado o aceptado y pertenecerá a .
  • Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución. Lo aplicaremos al conjunto de seleccionados unido con el elemento más prometedor.
  • Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del problema.

Funcionamiento

El algoritmo escoge en cada paso al mejor elemento posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos () y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados () produce una solución factible.

En caso de que así sea, se incluye ese elemento en . Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.

Algoritmo

Greedy (conjunto de candidatos C): solución S

S = Ø

while (S no sea una solución y C ≠ Ø) {

x = selección(C)

C = C – {x}

if (S∪{x} es factible)

S = S∪{x}

}

if (S es una solución)

return S;

else

return “No se encontró una solución”;

Aplicaciones

  • Planificación de tareas.
  • Minimización del tiempo de espera=Almacenamiento en cintas.
  • Planificación de tareas a plazo fijo = Selección de actividades.
  • Cajero (devolver un número mínimo de monedas/billetes [pero no sellos]).
  • Caminos mínimos en grafos (algoritmo de Dijkstra).
  • Árbol generador minimal (algoritmos de Prim & Kruskal Kruskal).
  • Códigos Huffman y compresión de datos.
  • Construcción de árboles de decisión.
  • Heurísticas greedy…

Heurísticas greedy

Hay situaciones en las cuales no podemos encontrar un algoritmo greedy que proporcione una solución óptima…

En muchas ocasiones, se podrían obtener mejores soluciones reconsiderando alternativas desechadas por un algoritmo greedy (cuando, a partir de una solución óptima local no se puede alcanzar una solución óptima global).

Pese a ello, resultan útiles los algoritmos greedy que proporcionan una solución rápida a problemas complejos, aunque ésta no sea óptima.

Ejemplos de algoritmos voraces

Temas relacionados

Referencias

  • Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces». Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X. 
  • Departamento de ciencias de la computación Universidad de Granada. (s. f.). Algoritmos Greedy.
  • Abad Soriano, M. T. (2007–2008). Algoritmos voraces.
  • Fillottrani, P. R. (2017). Algoritmos y complejidad.

Enlaces externos

En inglés:

Read other articles:

Ricardo González Vigil Información personalNacimiento 31 de julio de 1949 (74 años)Lima, PerúNacionalidad PerúPerúEducaciónEducado en Pontificia Universidad Católica del PerúInformación profesionalOcupación Poeta, escritor, crítico literarioEmpleador Pontificia Universidad Católica del Perú Movimiento Generación del 70Género Ensayo[editar datos en Wikidata] Ricardo González-Vigil (Lima, 31 de julio de 1949) es un poeta, crítico literario y antologador peruano....

 

MeteoraAlbum studio karya Linkin ParkDirilis25 Maret 2003DirekamApril – Desember 2002StudioNRG Recording Studios(North Hollywood, California)Genre Nu metal rap metal rap rock metal alternatif rock alternatif Durasi36:35Label Warner Bros. Machine Shop Produser Don Gilmore Linkin Park Kronologi album studio Linkin Park Hybrid Theory(2000) Meteora(2003) Minutes to Midnight(2007) Singel dalam album Meteora Somewhere I BelongDirilis: 17 Maret 2003 FaintDirilis: 9 Juni 2003 NumbDirilis: 8 Sep...

 

Celeste Ntuli Información personalNacimiento 25 de agosto de 1978 (45 años)Empangeni (Sudáfrica) Nacionalidad SudafricanaInformación profesionalOcupación Comediante y actriz [editar datos en Wikidata] Celeste Ntuli (Empangeni, 25 de agosto de 1978) es una comediante y actriz sudafricana.[1]​[2]​ Se le conoce como la reina de la comedia zulú y es conocida por ser la primera comediante local en grabar un DVD con su programa.[3]​[4]​[5]​[6]​ Bi...

Montañas Glass House listed on the Australian National Heritage List Cordillera Gran Cordillera DivisoriaCoordenadas 26°54′S 152°55′E / -26.9, 152.92Localización administrativaPaís AustraliaDivisión QueenslandCaracterísticas generalesAltitud 556 metrosMapa de localización Montañas Glass House Ubicación en Queensland. [editar datos en Wikidata] Las dos montañas Tunbubudula En la zona de las montañas Glass House, también llamada montañas Glasshouse, h...

 

Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Moorende (Begriffsklärung) aufgeführt. Moorende Gemeinde Jork Koordinaten: 53° 30′ N, 9° 44′ O53.502359.731931Koordinaten: 53° 30′ 8″ N, 9° 43′ 55″ O Höhe: 1 m Eingemeindung: 1. Juli 1972 Postleitzahl: 21635 Vorwahl: 04162 Moorende (Niedersachsen) Lage von Moorende in Niedersachsen Fachwerkhaus in MoorendeFachwerkhaus in Moorende Moorende ist ...

 

The Von Bondies The Von Bondies en vivo en Suecia, (2004).Datos generalesOrigen Detroit, Míchigan,  Estados UnidosInformación artísticaGénero(s) Indie rockPunk bluesGarage rockRock alternativoPost-punk revivalPeríodo de actividad 1997 - 2011Discográfica(s) Sire RecordsDim Mak RecordsMajordomo RecordsFierce Panda RecordsModel Citizen RecordsSympathy for the Record IndustryArtistas relacionados Peter KatisJim DiamondButch WalkerJerry HarrisonHounds BelowWebSitio web -Miembr...

1978年こちらもご覧下さい   社会 政治 経済 法 労働 教育 交通 文化と芸術 映画 日本公開映画 音楽 日本のラジオ日本のテレビ 芸術 文学 出版 スポーツ スポーツ 日本競馬 サッカー 自転車競技 バスケ バレー 野球 相撲 競輪 科学と技術 科学 気象・地象・天象 台風 道路 鉄道 航空 地域 日本 日本の女性史 各年のテレビ(日本) 1976 1977 1978 1979 1980 各年のラジオ (日本) ...

 

Untuk kegunaan lain, lihat Tubalcain (disambiguasi). Tubal-KainTubal-Kain di tempat penempaan. Tapestri, Musée de Cluny – Musée national du Moyen ÂgeLahirTubal-cainNama lainTubal-Cain, Tubalcain, Tubal (nama sederhana)PekerjaanPndai besarDikenal atasBapak para pandai besarGelarbapa semua tukang tembaga dan tukang besiOrang tuaLamekh dan ZilaKerabatYabal (saudara tiri)Yubal (saudara tiri)Naama (saudari) Tubal-kain atau Tubalkain (Ibrani: תּוּבַל קַיִן – Tū́ḇal Qáyi...

 

Type of motorcycle CB550Honda CB550KManufacturerHondaProduction1974–1978PredecessorHonda CB500SuccessorHonda CB650Classstandard motorcycleEngine544 cc (33.2 cu in) air-cooled 8-valve SOHC transverse fourBore / stroke58.5 mm × 50.6 mm (2.30 in × 1.99 in)Compression ratio9.0:1Top speed109 mph (175 km/h)[1]Power50 bhp (37 kW) @ 8,500 rpm[1][2]Torque26.04 lbf⋅ft (35.31 N⋅m) 7,000 r...

Marian Bartłomiej Radwański podpułkownik dyplomowany piechoty Data i miejsce urodzenia 23 sierpnia 1893 Rzeszów Przebieg służby Siły zbrojne Armia Austro-Węgier Wojsko Polskie Polskie Siły Zbrojne Główne wojny i bitwy I wojna światowawojna polsko-bolszewicka II wojna światowa kampania wrześniowa Odznaczenia Marian Bartłomiej Radwański vel Kluska[a] (ur. 23 sierpnia 1893 w Rzeszowie) – podpułkownik dyplomowany piechoty Wojska Polskiego i Polskich Sił Zbrojnych, kawaler...

 

Not to be confused with Drama (rapper). American DJ and record executive DJ DramaDJ Drama performing in 2016Background informationBirth nameTyree Cinque SimmonsBorn (1978-04-22) April 22, 1978 (age 45)Philadelphia, Pennsylvania, U.S. EducationClark Atlanta University (BS) GenresHip hopOccupation(s) Disc jockey record executive music promoter Years active1999–presentLabels Aphilliates Generation Now E1 (current) Grand Hustle Atlantic (former) Websitedramalikethedj.comMusical artist Tyre...

 

Three-dimensional chess variant 3D rendering of starting position Millennium 3D chess is a three-dimensional chess variant created by William L. d'Agostino in 2001. It employs three vertically stacked 8×8 boards, with each player controlling a standard set of chess pieces.[1][2] The inventor describes his objective as extending the traditional chess game into a multilevel environment without distorting the basic game.[3] Rules Millennium 3D сhess extends the traditio...

Village in Kuyavian-Pomeranian Voivodeship, PolandSuchomVillageSuchomCoordinates: 53°33′33″N 18°08′31″E / 53.55917°N 18.14194°E / 53.55917; 18.14194Country PolandVoivodeshipKuyavian-PomeranianCountyTucholaGminaCekcynPopulation30 Suchom [ˈsuxɔm] is a village in the administrative district of Gmina Cekcyn, within Tuchola County, Kuyavian-Pomeranian Voivodeship, in north-central Poland.[1] References ^ Central Statistical Office (GUS) – TE...

 

President of Haiti This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Pierre Théoma Boisrond-Canal – news · newspapers · books · scholar · JSTOR (September 2010) (Learn how and when to remove this template message) Pierre Théoma Boisrond-CanalPresident of the Provisional Government of HaitiIn office26 May 1902 – 17 ...

 

此條目需要擴充。 (2017年11月25日)请協助改善这篇條目,更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 第二次世界大戰義大利軍事佔領法國義大利军事占领1940年-1943年 義大利王國國旗 紋章 首府芒通 • 类型軍事行政(英语:Military administration) 歷史時期第二次世界大戰• 義大利入侵法國 1940年年6月10日• 法義停戰(英...

American sketch comedy television series This article is about the American live-action comedy program. For the 2010 animated sketch comedy show, see Mad (TV series). For other uses, see Mad TV (disambiguation). Mad TVGenreSketch comedyParodySatireCreated by David Salzman Fax Bahr Adam Small Based onMadby EC ComicsStarringsee List of Mad TV cast membersTheme music composer Greg O'Connor Blake Aaron Country of originUnited StatesOriginal languageEnglishNo. of seasons15No. of episodes321 (list ...

 

Bridge between Manhattan and the Bronx, New York Spuyten Duyvil BridgeCircle Line boat passing through bridge, 2014Coordinates40°52′42″N 73°55′32″W / 40.87833°N 73.92556°W / 40.87833; -73.92556CarriesAmtrak West Side Line/Empire Connection (1 track)CrossesHarlem RiverLocaleManhattan and the Bronx, New York CityCharacteristicsDesignRailroad swing bridgeTotal length610 feet (190 m)[1]Longest span286 feet (87 m)[2]Clearance below5 fee...

 

Brouwerij d'Hollander kan verwijzen naar: Brouwerij d'Hollander (Baasrode), een voormalige brouwerij in Baasrode van familie d'Hollander. Brouwerij d'Hollander (Eke), een voormalige brouwerij in Eke van familie d'Hollander. Een brouwershuis te Hamme Bekijk alle artikelen waarvan de titel begint met Brouwerij d'Hollander of met Brouwerij d'Hollander in de titel. Dit is een doorverwijspagina, bedoeld om de verschillen in betekenis of gebruik van Brouwerij d'Hollander in...

Park in Malmö, Sweden You can help expand this article with text translated from the corresponding article in Swedish. (November 2009) Click [show] for important translation instructions. View a machine-translated version of the Swedish article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated te...

 

Douglas DC-3 modified with turboprop engines BT-67 A BT-67 of the Royal Thai Air Force Role Utility aircraftType of aircraft National origin United States Manufacturer Basler Turbo Conversions First flight 1990 Status in service Produced 1990–present[1] Number built 68[2] Developed from Douglas DC-3 The Basler BT-67 is a utility aircraft produced by Basler Turbo Conversions of Oshkosh, Wisconsin. It is a remanufactured and modified Douglas C-47 (DC-3); the modifications are ...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!