Chamtivá metoda je jednou ze strategií, jako je Rozděl a panuj, která se používá k řešení problémů. Tato metoda se používá pro řešení optimalizačních problémů. Optimalizační problém je problém, který vyžaduje maximální nebo minimální výsledky. Pojďme si rozumět přes některé pojmy.
Greedyho metoda je nejjednodušší a přímočarý přístup. Není to algoritmus, ale technika. Hlavní funkcí tohoto přístupu je, že rozhodnutí je přijímáno na základě aktuálně dostupných informací. Ať jsou aktuální informace jakékoli, rozhodnutí je učiněno bez obav z dopadu aktuálního rozhodnutí v budoucnu.
slovník c#
Tato technika se v zásadě používá k určení proveditelného řešení, které může nebo nemusí být optimální. Možné řešení je podmnožina, která splňuje daná kritéria. Optimálním řešením je řešení, které je nejlepším a nejvýhodnějším řešením v podmnožině. V případě proveditelného, pokud daná kritéria splňuje více než jedno řešení, budou tato řešení považována za proveditelná, přičemž optimální řešení je nejlepší řešení ze všech řešení.
Charakteristika Greedyho metody
Následují charakteristiky chamtivé metody:
- Pro optimální konstrukci řešení tento algoritmus vytvoří dvě sady, kde jedna sada obsahuje všechny vybrané položky a druhá sada obsahuje odmítnuté položky.
- Greedy algoritmus dělá dobré místní volby v naději, že řešení by mělo být proveditelné nebo optimální.
Komponenty Greedy Algorithmu
Komponenty, které lze použít v chamtivém algoritmu, jsou:
ternární operátor java
Aplikace Greedy Algorithm
- Používá se při hledání nejkratší cesty.
- Používá se k nalezení minimální kostry pomocí primova algoritmu nebo Kruskalova algoritmu.
- Používá se v posloupnosti úloh s termínem.
- Tento algoritmus se také používá k řešení problému frakčního batohu.
Pseudo kód Greedy Algorithm
Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } Výše uvedené je chamtivý algoritmus. Zpočátku je řešení přiřazena nulová hodnota. Předáme pole a počet prvků v chamtivém algoritmu. Uvnitř cyklu for postupně vybíráme prvek a kontrolujeme, zda je řešení proveditelné nebo ne. Pokud je řešení proveditelné, provedeme spojení.
Pojďme to pochopit na příkladu.
Předpokládejme, že existuje problém 'P'. Chci cestovat z A do B, jak je uvedeno níže:
P: A → B
Problém je v tom, že tuto cestu musíme absolvovat z A do B. Existují různá řešení, jak se dostat z A do B. Můžeme jet z A do B chůze, auto, kolo, vlak, letadlo , atd. V cestě je omezení, že tuto cestu musíme ujet do 12 hodin. Pokud pojedu vlakem nebo letadlem, mohu tuto vzdálenost překonat do 12 hodin. Existuje mnoho řešení tohoto problému, ale existují pouze dvě řešení, která splňují omezení.
příklady java kódu
Řekneme-li, že cestu musíme pokrýt s minimálními náklady. To znamená, že tuto vzdálenost musíme urazit co nejméně, takže tento problém je známý jako problém minimalizace. Doposud máme dvě proveditelná řešení, tedy jedno vlakem a druhé letecky. Vzhledem k tomu, že cestování vlakem povede k minimálním nákladům, je to optimální řešení. Optimální řešení je také proveditelné řešení, ale poskytující nejlepší výsledek, takže řešení je optimální řešení s minimálními náklady. Bylo by jen jedno optimální řešení.
Problém, který vyžaduje buď minimální nebo maximální výsledek, se pak tento problém nazývá optimalizační problém. Greedy metoda je jednou ze strategií používaných pro řešení optimalizačních problémů.
Nevýhody použití Greedyho algoritmu
Greedy algoritmus se rozhoduje na základě informací dostupných v každé fázi, aniž by zvažoval širší problém. Může tedy existovat možnost, že chamtivé řešení neposkytuje nejlepší řešení pro každý problém.
binární strom v Javě
Sleduje volbu lokálního optima v každé fázi se záměrem nalézt globální optimum. Pojďme to pochopit na příkladu.
Zvažte graf, který je uveden níže:
Musíme cestovat od zdroje do cíle s minimálními náklady. Protože máme tři proveditelná řešení s nákladovými cestami 10, 20 a 5. 5 je cesta minimálních nákladů, takže je to optimální řešení. Toto je lokální optimum a tímto způsobem najdeme lokální optimum v každé fázi, abychom mohli vypočítat globální optimální řešení.