Selles õpetuses saate teada, mis on ahne algoritm. Samuti leiate näite ahnest lähenemisest.
Ahne algoritm on lähenemisviis probleemi lahendamiseks, valides hetkel parima võimaliku variandi, muretsemata selle tulevase tulemuse pärast. Teisisõnu, kohalike parimate valikute eesmärk on saavutada ülemaailmselt parimaid tulemusi.
See algoritm ei pruugi olla kõigi probleemide jaoks parim variant. Mõnel juhul võib see anda valesid tulemusi.
See algoritm ei lähe kunagi tagasi tehtud otsuse ümberpööramiseks. See algoritm töötab ülalt-alla lähenemisviisis.
Selle algoritmi peamine eelis on:
- Algoritmi on lihtsam kirjeldada .
- See algoritm suudab paremini kui teised algoritmid (kuid mitte kõigil juhtudel).
Teostatav lahendus
Teostatav lahendus on probleemile optimaalne lahendus.
Ahne algoritm
- Alustuseks on vastuste komplekt (mis sisaldab vastuseid) tühi.
- Igal etapil lisatakse lahuste komplekti üksus.
- Kui lahenduskomplekt on teostatav, säilitatakse praegune üksus.
- Muul juhul lükatakse üksus tagasi ja seda ei kaaluta enam.
Näide - ahne lähenemine
Probleem: peate summat muutma, kasutades võimalikult väikest müntide arvu. Kogus: $ 28 Saadaval mündid: $ 5 münt $ 2 münt $ 1 münt
Lahendus:
- Looge tühi lahendus-komplekt = ().
- mündid = (5, 2, 1)
- summa = 0
- Summa sum 28 ajal tehke järgmist.
- Valige müntide hulgast C selline, et summa + C <28.
- Kui C + summa> 28, siis tagastage lahendus.
- Muidu summa = summa + C.
- Lisage lahusekomplekti C.
Kuni esimese viie iteratsioonini sisaldab lahenduskomplekt 5 münti 5 dollarit. Pärast seda saame 1 $ 2 mündi ja lõpuks 1 $ 1 mündi.
Ahned algoritmirakendused
- Valik Sorteeri
- Seljakotiprobleem
- Minimaalne laiuspuu
- Ühe allika lühima tee probleem
- Töö planeerimise probleem
- Primi minimaalse laiuva puu algoritm
- Kruskali minimaalse laiuva puu algoritm
- Dijkstra minimaalse laiuva puu algoritm
- Huffmani kodeerimine
- Ford-Fulkersoni algoritm
