Ahne algoritmi

Tässä opetusohjelmassa opit, mikä on ahne algoritmi. Löydät myös esimerkin ahneesta lähestymistavasta.

Ahne algoritmi on lähestymistapa ongelman ratkaisemiseen valitsemalla parhaiten käytettävissä oleva vaihtoehto tällä hetkellä huolimatta tulevasta tuloksesta. Toisin sanoen paikallisesti parhaiden valintojen tavoitteena on tuottaa maailmanlaajuisesti parhaat tulokset.

Tämä algoritmi ei ehkä ole paras vaihtoehto kaikkiin ongelmiin. Joissakin tapauksissa se voi tuottaa vääriä tuloksia.

Tämä algoritmi ei koskaan palaa takaisin päinvastaiseksi tehdyn päätöksen kanssa. Tämä algoritmi toimii ylhäältä alas -menetelmällä.

Tämän algoritmin tärkein etu on:

  1. Algoritmia on helpompi kuvata .
  2. Tämä algoritmi voi toimia paremmin kuin muut algoritmit (mutta ei kaikissa tapauksissa).

Mahdollinen ratkaisu

Mahdollinen ratkaisu on se, joka tarjoaa optimaalisen ratkaisun ongelmaan.

Ahne algoritmi

  1. Ensinnäkin ratkaisujoukko (joka sisältää vastauksia) on tyhjä.
  2. Jokaisessa vaiheessa tuote lisätään ratkaisusarjaan.
  3. Jos ratkaisujoukko on mahdollista, nykyinen kohde säilytetään.
  4. Muuten kohde hylätään eikä sitä enää koskaan harkita.

Esimerkki - ahne lähestymistapa

 Ongelma: Sinun on muutettava määrää käyttämällä pienintä mahdollista kolikoiden määrää. Määrä: 28 dollaria Saatavilla olevat kolikot: 5 dollarin kolikko 2 dollarin kolikko 1 dollarin kolikko

Ratkaisu:

  1. Luo tyhjä ratkaisujoukko = ().
  2. kolikot = (5, 2, 1)
  3. summa = 0
  4. Kun summa sum 28, toimi seuraavasti.
  5. Valitse kolikko C kolikoista siten, että summa + C <28.
  6. Jos C + summa> 28, palauta mitään ratkaisua.
  7. Muuten summa = summa + C.
  8. Lisää C liuosjoukkoon.

Ensimmäiseen 5 iteraatioon asti ratkaisusarja sisältää 5 $ 5 kolikkoa. Sen jälkeen saamme 1 $ 2 kolikon ja lopuksi 1 $ 1 kolikon.

Ahneiden algoritmien sovellukset

  • Valinta Lajittele
  • Selkäreppuongelma
  • Pienin ulottuva puu
  • Yhden lähteen lyhimmän polun ongelma
  • Työn ajoitusongelma
  • Primin pienin ulottuva puu -algoritmi
  • Kruskalin vähimmäispitoisuuspuun algoritmi
  • Dijkstran vähimmäispitoisuuspuun algoritmi
  • Huffman-koodaus
  • Ford-Fulkerson-algoritmi

Mielenkiintoisia artikkeleita...