Egy mohó algoritmusban meghozzuk azt a választást, ami pillanatnyilag legjobbnak tűnik, abban a reményben, hogy globálisan optimális megoldáshoz vezet. A dinamikus programozásban minden lépésben döntést hozunk, figyelembe véve az aktuális problémát és a korábban megoldott részprobléma megoldását az optimális megoldás kiszámításához.
Hány megvalósítható megoldás létezik a mohó módszerben?
A Greedy algoritmus minden lépésben mohó döntéseket hoz, hogy biztosítsa a célfüggvény optimalizálását. A Greedy algoritmusnak csak egy lövése van az optimális megoldás kiszámítására, hogy soha ne térjen vissza és ne fordítsa meg a döntést.
Mi a mohó módszer fogalma?
Definíció: Egy algoritmus, amely mindig a legjobb azonnali vagy helyi megoldást választja, miközben megtalálja a választ. A mohó algoritmusok megtalálják az általános vagy globálisan optimális megoldást egyes optimalizálási problémákra, de más problémákra is találhatnak az optimálisnál kevésbé megfelelő megoldást.
Milyen előnyei vannak a mohó megközelítésnek?
A mohó algoritmus használatának az az előnye, hogy a probléma kisebb eseteire a megoldások egyszerűek és könnyen érthetők. Hátránya, hogy teljesen lehetséges, hogy a legoptimálisabb rövid távú megoldások a lehető legrosszabb hosszú távú eredményhez vezethetnek.
Mikor használjuk a mohó szót?
Az alábbiakban felsorolunk néhány olyan problémát, amelyek az optimális megoldást használják a Greedy megközelítést alkalmazva
- Utazó értékesítő probléma.
- Kruskal minimális feszítőfa algoritmusa.
- Dijkstra minimális feszítőfa algoritmusa.
- Hátizsákprobléma.
- Munkaütemezési probléma.
