Algoritmická technika - Algorithmic technique - Wikipedia

v matematika a počítačová věda, an algoritmická technika[1] je obecný přístup k implementaci procesu nebo výpočet.[2]

Obecné techniky

Existuje několik široce uznávaných algoritmických technik, které nabízejí osvědčenou metodu nebo postup pro navrhování a konstrukci algoritmů. V závislosti na cíli, který může zahrnovat, lze použít různé techniky vyhledávání, třídění, matematická optimalizace, omezení spokojenosti, kategorizace, analýza, a předpověď.[3]

Hrubou silou

Hrubou silou je jednoduchá, vyčerpávající technika, která hodnotí každý možný výsledek a hledá řešení.[4]

Rozděl a panuj

The rozděl a panuj technika rekurzivně rozkládá složité problémy na menší dílčí problémy. Každý dílčí problém je poté vyřešen a tato dílčí řešení jsou rekombinována za účelem stanovení celkového řešení. Tato technika se často používá pro vyhledávání a třídění.[5]

Dynamický

Dynamické programování je systematická technika, při které se složitý problém rekurzivně rozkládá na menší, překrývající se dílčí problémy pro řešení. Dynamické programování ukládá výsledky překrývajících se dílčích problémů lokálně pomocí optimalizační techniky zvané memorování.[6]

Evoluční

An evoluční přístup vyvíjí kandidátská řešení a poté podobným způsobem jako biologická evoluce provádí řadu náhodných změn nebo kombinací těchto řešení a hodnotí nové výsledky proti fitness funkci. Nejvhodnější nebo nejslibnější výsledky jsou vybrány pro další iterace, aby se dosáhlo celkového optimálního řešení.[7]

Traverz grafu

Traverz grafu je technika pro hledání řešení problémů, které lze reprezentovat jako grafy. Tento přístup je široký a zahrnuje hloubkové vyhledávání, vyhledávání na šířku, traversal strom, a mnoho konkrétních variací, které mohou zahrnovat místní optimalizace a vyloučení vyhledávacích prostorů, které lze určit jako neoptimální nebo nemožné. Tyto techniky lze použít k řešení řady problémů včetně nejkratší cesta a problémy s uspokojením omezení.[8]

Chamtivý

A chamtivý přístup začíná hodnocením jednoho možného výsledku ze souboru možných výsledků a poté hledá místní zlepšení tohoto výsledku. Když se najde místní vylepšení, bude proces opakovat a znovu bude hledat lokálně další vylepšení poblíž tohoto místního optima. Chamtivá technika je obecně snadno implementovatelná a tyto řady rozhodnutí lze použít k nalezení lokálních optim v závislosti na tom, kde hledání začalo. Avšak chamtivé techniky nemusí identifikovat globální optimum v celé sadě možných výsledků.[9],

Heuristický

A heuristický přístup využívá praktickou metodu k dosažení okamžitého řešení, u kterého není zaručeno, že bude optimální.[10]

Učení se

Učení se techniky využívají statistické metody k provedení kategorizace a analýzy bez explicitního programování. Kontrolované učení, neřízené učení, posilování učení, a hluboké učení techniky jsou zahrnuty v této kategorii.[11]

Matematická optimalizace

Matematická optimalizace je technika, kterou lze použít k výpočtu matematického optima minimalizací nebo maximalizací funkce.[12]

Modelování

Modelování je obecná technika pro abstrahování problému reálného světa do rámce nebo paradigma který pomáhá s řešením.[13]

Rekurze

Rekurze je obecná technika pro návrh algoritmu, který se nazývá postupně jednodušší částí úkolu až k jednomu nebo více základním případům s definovanými výsledky.[14][15]

Viz také

Poznámky

  1. ^ "technika | Definice techniky v angličtině Oxfordskými slovníky". Oxfordské slovníky | Angličtina. Citováno 2019-03-23.
  2. ^ Cormen, Thomas H .; Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Úvod do algoritmů. MIT Stiskněte. p. 9. ISBN  9780262032933.
  3. ^ Skiena, Steven S. (1998). Příručka pro návrh algoritmu: Text. Springer Science & Business Media. ISBN  9780387948607.
  4. ^ „Co je to hrubá síla? Definice Webopedie“. www.webopedia.com. Citováno 2019-03-23.
  5. ^ Bentley, Jon Louis; Shamos, Michael Ian (1976). „Rozděluj a panuj ve vícerozměrném prostoru“. Proceedings of the Eighth Annual ACM Symposium on Theory of Computing. STOC '76. New York, NY, USA: ACM: 220–230. doi:10.1145/800113.803652.
  6. ^ Bellman, Richard (01.07.1966). "Dynamické programování". Věda. 153 (3731): 34–37. doi:10.1126 / science.153.3731.34. ISSN  0036-8075. PMID  17730601.
  7. ^ Coello Coello, Carlos A. (01.08.1999). „Komplexní průzkum technik optimalizace multiobjektivů založených na evoluci“. Znalostní a informační systémy. 1 (3): 269–308. doi:10.1007 / BF03325101. ISSN  0219-3116.
  8. ^ Kumar, Nitin; Wayne, Kevin (01.02.2014). Algoritmy. Addison-Wesley Professional. ISBN  9780133799101.
  9. ^ "chamtivý algoritmus". xlinux.nist.gov. Citováno 2019-03-23.
  10. ^ "heuristický". xlinux.nist.gov. Citováno 2019-03-23.
  11. ^ Witten, Ian H .; Frank, Eibe; Hall, Mark A .; Pal, Christopher J. (01.10.2016). Dolování dat: Praktické nástroje a techniky strojového učení. Morgan Kaufmann. ISBN  9780128043578.
  12. ^ Marler, RT; Arora, J.S. (2004-04-01). "Průzkum metod optimalizace více cílů pro strojírenství". Strukturální a multidisciplinární optimalizace. 26 (6): 369–395. doi:10.1007 / s00158-003-0368-6. ISSN  1615-1488.
  13. ^ Skiena, Steven S. (1998). Příručka pro návrh algoritmu: Text. Springer Science & Business Media. ISBN  9780387948607.
  14. ^ "rekurze". xlinux.nist.gov. Citováno 2019-03-23.
  15. ^ „Programování - rekurze“. www.cs.utah.edu. Citováno 2019-03-23.

externí odkazy