logo

TechCodeview

Ahneet algoritmit

Ahneita algoritmeja ovat luokka algoritmeja, jotka tekevät paikallisesti optimaalinen valintoja jokaisessa vaiheessa toivoen löytävänsä a globaali optimi ratkaisu. Näissä algoritmeissa päätökset tehdään tällä hetkellä saatavilla olevan tiedon perusteella ottamatta huomioon näiden päätösten seurauksia tulevaisuudessa. Keskeisenä ajatuksena on valita jokaisessa vaiheessa paras mahdollinen vaihtoehto, mikä johtaa ratkaisuun, joka ei välttämättä aina ole optimaalisin, mutta joka on usein riittävän hyvä moniin ongelmiin.

Tässä artikkelissa ymmärrämme ahneita algoritmeja esimerkkien avulla. Tarkastellaan myös ongelmia ja niiden ratkaisuja ahneella lähestymistavalla.

Ahneet algoritmit



Sisällysluettelo

Mikä on Greedy Algorithm?

A ahne algoritmi on eräänlainen optimointialgoritmi, joka tekee paikallisesti optimaaliset valinnat jokaisessa vaiheessa globaalisti optimaalisen ratkaisun löytämiseksi. Se toimii periaatteella valita paras vaihtoehto nyt ottamatta huomioon pitkän aikavälin seurauksia.

Jos haluat oppia, mikä on ahne menetelmä ja kuinka käyttää ahnetta lähestymistapaa, lue annettu opetusohjelma ahneesta algoritmista:

Vaiheet ahneen algoritmin luomiseen

Vaiheet ahneen algoritmin määrittämiseksi ovat:

  1. Määrittele ongelma: Kerro selkeästi ratkaistava ongelma ja optimoitava tavoite.
  2. Tunnista ahne valinta: Määritä paikallisesti optimaalinen valinta kussakin vaiheessa nykyisen tilan perusteella.
  3. Tee ahne valinta: Valitse ahne valinta ja päivitä nykyinen tila.
  4. Toistaa: Jatka ahneiden valintojen tekemistä, kunnes ratkaisu löytyy.

Annettujen vaiheiden jälkeen voidaan oppia käyttämään ahneita algoritmeja optimaalisten ratkaisujen löytämiseen.

Esimerkkejä ahneista algoritmeista

Esimerkit ahneista algoritmeista ovat paras tapa ymmärtää algoritmi. Joitakin ahneita algoritmeja tosielämässä ovat:

rekursio javassa
  • Murtoreppu : Optimoi niiden esineiden arvon, jotka voidaan sisällyttää osittaisesti rajoitetun kapasiteetin reppuun.
  • Dijkstran algoritmi : Löytää lyhimmän polun lähdepisteestä kaikkiin muihin painotetun graafin kärkikohtiin.
  • Kruskalin algoritmi : Löytää painotetun graafin pienimmän virittävän puun.
  • Huffman koodaus : Pakkaa tiedot määrittämällä lyhyempiä koodeja useammin esiintyville symboleille.

Greedy Algorithmin sovellukset

On olemassa monia ahneen menetelmän sovelluksia DAA:ssa . Joitakin tärkeitä ahneita algoritmisovelluksia ovat:

  • Tehtävien osoittaminen resursseille odotusajan minimoimiseksi tai tehokkuuden maksimoimiseksi.
  • Arvokkaimpien esineiden valinta rajoitettuun reppuun mahtuviksi.
  • Kuvan jakaminen alueisiin, joilla on samanlaiset ominaisuudet.
  • Tietojen koon pienentäminen poistamalla tarpeettomat tiedot.

Ahneen algoritmin käytön haitat/rajoitukset

Alla on joitain Greedy-algoritmin haittoja:

  • Ahneet algoritmit eivät välttämättä aina löydä parasta mahdollista ratkaisua.
  • Järjestys, jossa elementit otetaan huomioon, voi vaikuttaa merkittävästi lopputulokseen.
  • Ahneet algoritmit keskittyvät paikallisiin optimointiin ja saattavat jättää huomiotta parempia ratkaisuja, jotka edellyttävät laajempaa kontekstia.
  • Ahneet algoritmit eivät sovellu ongelmiin, joissa ahne valinta ei johda optimaaliseen ratkaisuun.

Greedy-algoritmin perusteet:

  • Ahneet algoritmit (yleinen rakenne ja sovellukset)
  • Ero Greedy Algorithmin ja Divide and Conquer -algoritmin välillä
  • Ahne lähestymistapa vs dynaaminen ohjelmointi
  • Greedy-, Divide and Conquer- ja Dynamic Programming -algoritmien vertailu

Normaalit ahneet algoritmit:

  • Toiminnon valintaongelma
  • Työn järjestysongelma
  • Huffman koodaus
  • Huffmanin dekoodaus
  • Vesiliitäntäongelma
  • Vähimmäisvaihtoja kannakkeiden tasapainottamista varten
  • Egyptin fraktio
  • Poliisit saavat varkaat kiinni
  • Ongelma hyllyjen asentamisessa
  • Määritä hiiret reikiin

Ahneita ongelmia Arrayssa:

  • Taulukon vähimmäistuoteosajoukko
  • Maksimoi taulukon summa K negation jälkeen käyttämällä lajittelua
  • Kahden taulukon tulon vähimmäissumma
  • Kahden taulukon parien absoluuttisen eron vähimmäissumma
  • Pienin lisäys/vähennys, jotta matriisi ei kasva
  • Lajittelutaulukko, jossa kääntöpuoli keskellä
  • Mahdollinen suorakulmioiden pinta-alojen summa taulukolle
  • Suurin leksikografinen taulukko, jossa on enintään K peräkkäistä vaihtoa
  • Osio kahteen aliryhmään, joiden pituus on k ja (N – k) siten, että summien ero on suurin

Ahneet ongelmat käyttöjärjestelmässä:

  • Ensimmäinen sovitusalgoritmi muistinhallinnassa
  • Muistinhallinnan paras sovitusalgoritmi
  • Huonoin sovitusalgoritmi muistinhallinnassa
  • Lyhyin työ ensin -aikataulu
  • Työaikataulu kahdella kerralla sallittu
  • Ohjelma optimaaliseen sivunvaihtoalgoritmiin

Ahneet ongelmat kaaviossa:

  • Kruskalin pienin ulottuva puu
  • Primin vähimmäisvirityspuu
  • Boruvkan pienin ulottuva puu
  • Dijkastran lyhimmän polun algoritmi
  • Dial's Algorithm
  • Vähimmäiskustannukset kaikkien kaupunkien yhdistämisestä
  • Max Flow -ongelman esittely
  • Yhden syklin komponenttien lukumäärä suuntaamattomassa graafissa

Likimääräinen Greedy Algorithm for NP Complete:

  • Aseta kansi ongelma
  • Säiliön pakkausongelma
  • Graafin väritys
  • K-keskusten ongelma
  • Lyhin supermerkkijono-ongelma
  • Likimääräinen ratkaisu Travelling Salesman -ongelmaan MST:n avulla

Ahne DP:n erityistapauksiin:

  • Murtoreppu-ongelma
  • Vähimmäismäärä kolikoita vaaditaan

Helppoja ongelmia Greedyllä Algoritmi :

  • Jaa n maksimiyhdistelmäluvuiksi
  • Osta Maximum Stocks, jos i-osakkeita voi ostaa i:nnenä päivänä
  • Etsi vähimmäis- ja enimmäismäärä kaikkien N karkkien ostamiseen
  • Suurin mahdollinen summa on yhtä suuri kuin kolmen pinon summa
  • Jaa kuutio kuutioiksi siten, että tilavuuksien summa on suurin
  • Enimmäismäärä asiakkaita, jotka voivat olla tyytyväisiä annettuun määrään
  • Vähimmäiskierrokset pyöreän lukon avaamiseksi
  • Minimihuoneita m tapahtumalle n erässä tietyllä aikataululla
  • Vähimmäiskustannukset taulukon kokoa 1 poistamalla suuremmista pareista
  • Vähimmäishinta kaikkien kolikoiden hankkimisesta käytettäessä jokaisen kolikon kanssa sallittua lisäkolikkoa
  • Pienin lisäys k toiminnolla, jotta kaikki elementit ovat yhtä suuret
  • Etsi vähimmäismäärä valuuttasetelit ja arvot, jotka summautuvat annettuun summaan
  • Pienin osajoukko, jonka summa on suurempi kuin kaikki muut elementit

Keskikokoisia ongelmia Greedyllä Algoritmi :

  • Suurin määrä junia, joille voidaan tarjota pysähdys
  • Fibonaccin vähimmäistermit, joiden summa on yhtä suuri kuin K
  • Jaa luvut 1 - n kahteen ryhmään pienimmällä summaerolla
  • Paperi leikataan vähimmäismäärään neliöitä
  • Vähimmäisero kahden koon ryhmien välillä
  • Yhdistä n köyttä pienin kustannuksin
  • Rautatie-/linja-autoasemalle vaadittava laiturien vähimmäismäärä
  • Minimi alkupisteet koko matriisin läpikulkua varten tietyillä ehdoilla
  • Suurin palindromiluku permutoimalla numeroita
  • Etsi pienin luku tietyllä määrällä numeroita ja numeroiden summa
  • Leksikografisesti suurin osasarja siten, että jokainen merkki esiintyy vähintään k kertaa

Kovia ongelmia Greedyllä Algoritmi :

  • Enimmäiselementit, jotka voidaan tehdä yhtäläisiksi k päivityksellä
  • Minimoi kassavirta ystävien kesken
  • Minimikustannukset laudan leikkaamisesta neliöiksi
  • Vähimmäiskustannukset käsitellä m tehtävää, joissa vaihto maksaa
  • Vähimmäisaika kaikkien töiden suorittamiseen tietyin rajoituksin
  • Minimoi tornien korkeusero
  • Vähimmäisreunat, jotka käännettävät polun muodostamiseksi lähteestä määränpäähän
  • Etsi suurin kuutio, joka muodostuu poistamalla numeron vähimmäisnumerot
  • Järjestä merkkijonon merkit uudelleen siten, että kaksi vierekkäistä ei ole samanlaista
  • Järjestä merkkijono uudelleen niin, että kaikki samat merkit ovat d etäisyydellä
  • Opi tietorakenne ja algoritmit | DSA opetusohjelma
  • 20 parasta ahneiden algoritmien haastattelukysymystä
  • 'Harjoitteluongelmat' ahneissa algoritmeissa
  • 'Visa' ahneista algoritmeista