Algorisme voraç

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,[1] amb l'esperança (no sempre complerta)[2] d'arribar a un òptim global. L'algorisme voraç no torna mai enrere per reavaluar les eleccions ja preses.

Esquema

Tot algorisme voraç conté el següent:[3]

  • Un conjunt no infinit de candidats, de possibles solucions (parcials o totals) del problema,
  • Una funció de selecció, que ens permet seleccionar el millor dels candidats,
  • Una funció de factibilitat, que ens permet avaluar si el candidat ajuda a resoldre el problema,
  • Una funció solució, que avalua si el conjunt de candidats seleccionats soluciona el problema (totalment o parcialment).

Exemples

Un algorisme voraç determina el mínim nombre de monedes al tornar un canvi. Aquests són els pasos que qualsevol persona fa emulant un algorisme voraç per obtenir els 36 cèntims utilitzant monedes només de {1, 5, 10, 20} cèntims.

L'exemple més habitual és el de tornar un canvi amb el mínim de monedes de determinat valor. A la dreta es pot veure com s'escullen les monedes per tornar un canvi de 36 cèntims. El conjunt de candidats és {20, 10, 5, 1}, la funció de selecció és escollir sempre la de valor més alt, la funció de factibilitat és no superar mai els 36 cèntims amb els candidats escollits, la funció solució és aconseguir 36 cèntims.

Els algorismes voraços no garanteixen sempre una solució, ni que la solució obtinguda sigui l'òptima. En l'exemple anterior, si el conjunt de candidats hagués sigut {50, 20, 10, 5, 2}, l'algorisme no retornaria cap solució perquè en arribar a 35 cèntims {20+10+5} no tindria cap candidat que ajudés a resoldre el problema. En canvi, és obvi que existeix una solució amb {20+10+2+2+2}. En general, l'algorisme voraç produeix sempre una solució quan el conjunt de candidats té estructura de matroide.[4][5][6]

Altres exemples típics són el de minimitzar el recorregut que ha de fer un viatjant de comerç per a visitar una sèrie de clients distanciats entre ells (vegeu algorisme de Dijkstra)[7] o el d'empaquetar objectes de diferents volums en el mínim nombre de caixes idèntiques.[8]

Referències

  1. ↑ Curtis, pàgina 125.
  2. ↑ Franquesa Niubó, pàgina 199.
  3. ↑ Bofill i Arasa, pàgines 135-136.
  4. ↑ Cormen, pàgines 370 i 393 i ss.
  5. ↑ Curtis, pàgina 148.
  6. ↑ Franquesa Niubó, pàgina 200.
  7. ↑ Bofill i Arasa, pàgines 137 i següents.
  8. ↑ Serna Iglesias, pàgina 197.

Bibliografia

Vegeu també

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Algorisme voraç
  • Paul E., Black. «Greedy algorithm». Dictionary of Algorithms and Data Structures, 2005. [Consulta: 3 abril 2015].

Read other articles:

Portugal

Country in Southwestern Europe For other uses, see Portugal (disambiguation). Portuguese RepublicRepública Portuguesa (Portuguese) Flag Coat of arms Anthem: A PortuguesaThe PortugueseShow globeShow map of the European UnionLocation of Portugal (dark green)– in Europe (green & dark grey)– in the European Union (green)Capitaland largest cityLisbon38°46′N 9°9′W / 38.767°N 9.150°W / 38.767; -9.150Official l...

 

 

Joshua Oppenheimer

Joshua OppenheimerJoshua Oppenheimer pada peluncuran film The Act of Killing di PrancisLahirJoshua Lincoln Oppenheimer23 September 1974 (umur 49)Texas, Amerika SerikatKebangsaanAmerika Serikat, InggrisPekerjaanSutradara Joshua Lincoln Oppenheimer (lahir 23 September 1974 di Texas, Amerika Serikat) adalah sutradara film berkebangsaan Amerika dan Inggris tinggal di Copenhagen, Denmark. Film karya Oppenheimer mengaburkan batas antara fiksi dan dokumenter. Dipengaruhi oleh montase eksperime...

 

 

Braničevo (district)

Pour les articles homonymes, voir Braničevo. Cet article est une ébauche concernant la Serbie et la géographie. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Braničevo Administration Pays Serbie Villesou municipalités Veliko GradištePožarevacGolubacMalo CrnićeŽabariPetrovac na MlaviKučevoŽagubica Démographie Population 180 480 hab. (2011) Densité 47 hab./km2 Géographie Superficie 3...

Jacques Babinet

Pour les articles homonymes, voir Babinet. Jacques BabinetBiographieNaissance 5 mars 1794LusignanDécès 21 octobre 1872 (à 78 ans)ParisNationalité FrançaisFormation École polytechniqueÉcole d'application de l'artillerie et du génieActivités Physicien, mathématicien, astronome, météorologueAutres informationsA travaillé pour Collège de FranceUniversité de ParisMembre de Société philomathique de ParisAcadémie des sciencesSociété d'encouragement de la locomotion aérienn...

 

 

Divisi Pertama Liga Inggris

Divisi Pertama Liga InggrisBadan yang mengaturThe Football LeagueNegara Inggris  WalesDibentuk1888Dibubarkan2004Jumlah tim24 (1992–2004)Tingkat pada piramida1 (1888–1992)2 (1992–2004)Promosi keLiga Utama Inggris (1992–2004)Degradasi keDivisi KeduaPiala domestikPiala FAPiala ligaPiala LigaPiala Full Members (1985–1992)Piala internasionalPiala Champions Eropa(1956–1985, 1991–1992)Piala Winners Eropa(1960–1985, 1990–1999)Piala UEFA(1971–1985, 1990–2004)Piala Inter...

 

 

Lake Aircraft

Amphibious aircraft manufacturer Lake AircraftCompany typePrivateIndustryAerospaceFounded1959HeadquartersKissimmee, FloridaNew HampshireKey peopleArmand RivardProductsparts for LA-4 aircraftNumber of employees6Websitelakeamphib.com Lake LA-4-200 Buccaneer Lake LA-4-200 Buccaneer Lake Model 250 Seawolf Lake Aircraft was a manufacturer of amphibious aircraft. Its factory was in Sanford, Maine, United States, and its sales offices were located at Laconia / Gilford, New Hampshire and Kissimmee, F...

格奥尔基·马林科夫

格奥尔基·马林科夫Гео́ргий Маленко́в苏联共产党中央书记处书记（排名第一）任期1953年3月5日—1953年3月13日前任约瑟夫·斯大林继任尼基塔·赫鲁晓夫（第一书记）苏联部长会议主席任期1953年3月5日—1955年2月8日前任约瑟夫·斯大林继任尼古拉·布尔加宁 个人资料出生1902年1月8日［儒略曆1901年12月26日］ 俄罗斯帝国奥伦堡逝世1988年1月14日(1988歲—01—14)（86歲）&#...

 

 

周處除三害 (電影)

周處除三害The Pig, The Snake and The Pigeon正式版海報基本资料导演黃精甫监制李烈黃江豐動作指導洪昰顥编剧黃精甫主演阮經天袁富華陳以文王淨李李仁謝瓊煖配乐盧律銘林孝親林思妤保卜摄影王金城剪辑黃精甫林雍益制片商一種態度電影股份有限公司片长134分鐘产地 臺灣语言國語粵語台語上映及发行上映日期 2023年10月6日 (2023-10-06)（台灣） 2023年11月2日 (2023-11-02)（香�...

 

 

Maus

Graphic novel by Art Spiegelman This article is about the book. For the tank, see Panzer VIII Maus. For other uses, see Maus (disambiguation). MausCover of the first volume of MausCreatorArt SpiegelmanDate1991Page count296 pagesPublisherPantheon BooksOriginal publicationPublished inRawIssuesVol. 1 No. 2 – Vol. 2 No. 3Date of publication1980–1991 Maus,[a] often published as Maus: A Survivor's Tale, is a graphic novel by American cartoonist Art Spiegelman, serialized ...

Kelaguen

Chamorro dish of meat and green onions in an acidic marinade KelaguenKelaguen with titiyasPlace of originMariana IslandsMain ingredientsPickling marinade of lemon juice, fresh coconut, green onions, salt and spicy hot peppersSimilar dishesKilawin, kinilaw, 'ota 'ika, hinava, poke, ceviche Kelaguen is a Chamorro dish from the Mariana Islands eaten as a side dish or as a main course. Similar to ceviche, a pickling marinade of lemon juice, fresh coconut, green onions, salt and spicy hot peppers ...

 

 

Guys Like Us

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Guys Like Us – news · newspapers · books · scholar · JSTOR (September 2017) (Learn how and when to remove this message) American TV series or program Guys Like UsTitle cardGenreSitcomCreated byDan SchneiderWritten byTemi AkinyemiGeorge Doty IVJeffrey DuteilAndr...

 

 

DuckDuckGo

DuckDuckGo URL duckduckgo.com Коммерческий да Тип сайта интернет-поисковая система Регистрация нет Язык (-и) многоязычный Язык программирования Perl, JavaScript и Си Расположение сервера Паоли, Пенсильвания, США[1] Владелец DuckDuckGo, Inc. Создатель Гэбриел Вайнберг Начало работы 25 се...

Economy of Oklahoma

Economy of OklahomaFlag of OklahomaCurrencyUS$ (USD)Fiscal yearJuly 1 - June 30StatisticsGDP$200.2 billion (nominal, Q1 2020)[1]GDP rank 30th (Q1 2020)GDP growth 4.0% (2020)[2]GDP per capita$50,594 (2020 est)GDP by sectorAgriculture 2% Industry 34% Services 64%Population below poverty line15.2% (2011)[3]Labor force 1.9 million (Q1 2020)[4]Labor force by occupationAgriculture 1% Industry 16% Services 83%Unemployment 5.7% (Q3 2020)[5]Average gross salary...

 

 

Frio County, Texas

County in Texas, United States County in TexasFrio CountyCountyThe Frio County Courthouse in PearsallLocation within the U.S. state of TexasTexas's location within the U.S.Coordinates: 28°52′N 99°07′W / 28.86°N 99.11°W / 28.86; -99.11Country United StatesState TexasFounded1871Named forFrio RiverSeatPearsallLargest cityPearsallArea • Total1,134 sq mi (2,940 km2) • Land1,134 sq mi (2,940 km2) �...

 

 

Giurisprudenza

Questa voce o sezione sull'argomento diritto è priva o carente di note e riferimenti bibliografici puntuali. Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento. La giurisprudenza (termine derivante dal latin...

Cristóbal Balenciaga

Spanish fashion designer (1895-1972) In this Spanish name, the first or paternal surname is Balenciaga and the second or maternal family name is Eizaguirre. Cristóbal BalenciagaBalenciaga in 1950BornCristóbal Balenciaga Eizaguirre(1895-01-21)21 January 1895Getaria, SpainDied23 March 1972(1972-03-23) (aged 77)Jávea, SpainResting placeGetaria Cemetery[1]NationalitySpanishOccupationFashion DesignerYears active1917–1972Known forHaute Couture FashionLabelBalenci...

 

 

Antonio Rukavina

Serbian footballer (born 1984) Not to be confused with Ante Rukavina. Antonio Rukavina Rukavina with Serbia at the 2018 FIFA World CupPersonal informationDate of birth (1984-01-26) 26 January 1984 (age 40)Place of birth Belgrade, SR Serbia, YugoslaviaHeight 1.77 m (5 ft 10 in)Position(s) Right-backYouth career BežanijaSenior career*Years Team Apps (Gls)2002–2006 Bežanija 145 (18)2007 Partizan 32 (4)2008 Borussia Dortmund 19 (0)2009–2012 1860 Munich 112 (1)2012–2014...

 

 

2022 Mackay Cutters season

Rugby league season 2022 Mackay Cutters seasonQueensland Cup Rank11thPlay-off resultMissed finals2022 recordWins: 6; draws: 0; losses: 9Points scoredFor: 326; against: 368Team informationChairmanSteve DowdenCoachDave ElliottCaptainRoss BellaStadiumBB Print StadiumTop scorersTriesBlake Paskins (10)GoalsBrandon Finnegan (47)PointsBrandon Finnegan (106) ← 2021 2023 → The 2022 Mackay Cutters season is the 15th in the club's history. Coached by Dave Elliott a...

Bartolomeo Bianco

Rubens, palazzo Durazzo-Pallavicini, facciata Bartolomeo Bianco (Coldrerio, 1590 – Genova, 1657) è stato un architetto italiano, principale interprete del barocco genovese in architettura. Indice 1 Biografia 1.1 L'attività a Genova 1.2 L'attività a Chiavari 2 Note 3 Altri progetti 4 Collegamenti esterni Biografia Nativo di Coldrerio si trasferì molto giovane a Genova per seguire il padre, Cipriano Bianco[1], impegnato nel capoluogo ligure in alcuni lavori per il locale convento ...

 

 

Modèle:Palette Industrie nucléaire en Amérique

v · mIndustrie nucléaire en Amérique Argentine Programme nucléaire de l'Argentine Atucha Embalse Carem Brésil Programme nucléaire du Brésil Institut de recherche énergétique et nucléaire Angra Université fédérale du Minas Gerais Canada Industrie nucléaire au Canada Liste des réacteurs nucléaires au Canada Colombie Programme nucléaire de Colombie Réacteur TRIGA de Bogota Cuba Programme nucléaire de Cuba Juragua (VVER, construction interrompue) États-Unis Programme nuc...