Linkek

Programozási ismeretek

Alapoktól a speciálisig...

Mohó-algoritmusok

Optimális megoldás(?)

Ebben a bejegyzésben néhány mohó algoritmust mutatunk be. Ezúttal a SZTE egyik bejegyzését vesszük alapul, hogy definiáljuk a mohó algoritmust:

SZTE mohó-algoritmus:

„Optimalizálási probléma megoldására szolgáló algoritmus sokszor olyan lépések sorozatából áll, ahol minden lépésben adott halmazból választhatunk. Ezt gyakran dinamikus programozás alapján oldjuk meg, de előfordul, hogy ˝ a dinamikus programozás túl sok esetet vizsgál annak érdekében, hogy az optimális választást meghatározza.
A mohó algoritmus mindig az adott lépésben optimálisnak látszó választást teszi. Vagyis, a lokális optimumot választja abban a reményben, hogy ez globális optimumhoz fog majd vezetni.
Mohó algoritmus nem mindig ad optimális megoldást, azonban sok probléma megoldható mohó algoritmussal.”

Példánk a gráfokhoz kapcsolódik (és ott is megtekinthető /hogy minek? :)/): GRÁF oldal

PRIM-algoritmus

A mintapéldában egy szótár szerkezetben megadott gráfunk van, melyet csúcsmátrix (vagy szomszédsági mátrix) formába átírunk, majd azt dolgozzuk fel ezzel a mohó algoritmussal.

Wikipédia: (egy másik forrás: ELTE, csak, hogy ilyen is legyen :))
(Az ELTE-forrás eredeti elérhetősége: https://people.inf.elte.hu/scmqaai/algoadat2/csoport/FarkasAttila/Prim_algoritmus.pdf)

„Az algoritmus lépésenként építi fel a minimális feszítőfát, minden lépésben egy csúcsot adva hozzá.
Az algoritmus lépései a következők:

  • Válasszuk ki a gráf egy tetszőleges csúcsát, legyen ez egy egycsúcsú fa.
  • Ameddig van a gráfnak olyan csúcsa, amelyik nincs benne a fában, végezzük el a következőket:
    - Válasszuk ki a fa csúcsai és a gráf többi csúcsa között futó élek közül a legkisebb súlyút.
    - A kiválasztott él nem fabeli csúcsát tegyük át a fába az éllel együtt.”

PRIM-ALGORITMUS - Python példa (letöltés: prim_moho.py)

Eseménykiválasztási probléma

Tipikus - mohó stratégiával - megoldható probléma, egy adott intervallum maximális lefedése részintervallumokkal. Ehhez kapcsolódik az alábbi példa is. Feladatleírás a kódban!
(A feladatban szereplő foglalas.txt fájl letöltése: foglalas.txt)

A fájl tartalma:

5 9
3 5
8 12
5 7
3 8
12 14
0 6
1 4
2 13
6 10
8 11

ESEMÉNYKIVÁLASZTÁSI PROBLÉMA - Python példa (letöltés: esemeny_moho.py)

Párosítás

Feladatleírás a kódban! (letöltés: parositas_moho.py)

Pénzösszeg minimális címletezése

A lehető legkevesebb címlet felhasználásával írjunk le egy összeget! (letöltés: min_ermek.py)

Pénzösszeg minimális címletezése

C++ megoldás - A lehető legkevesebb címlet felhasználásával írjunk le egy összeget! (letöltés: cimletezes_C++.cpp)