In mathematics and computer science, an algorithmic technique[1] is a general approach for implementing a process or computation.[2]
General techniques
There are several broadly recognized algorithmic techniques that offer a proven method or process for designing and constructing algorithms. Different techniques may be used depending on the objective, which may include searching, sorting, mathematical optimization, constraint satisfaction, categorization, analysis, and prediction.[3]
Brute force
Brute force is a simple, exhaustive technique that evaluates every possible outcome to find a solution.[4]
Divide and conquer
The divide and conquer technique decomposes complex problems recursively into smaller sub-problems. Each sub-problem is then solved and these partial solutions are recombined to determine the overall solution. This technique is often used for searching and sorting.[5]
Dynamic
Dynamic programming is a systematic technique in which a complex problem is decomposed recursively into smaller, overlapping subproblems for solution. Dynamic programming stores the results of the overlapping sub-problems locally using an optimization technique called memoization.[6]
Evolutionary
An evolutionary approach develops candidate solutions and then, in a manner similar to biological evolution, performs a series of random alterations or combinations of these solutions and evaluates the new results against a fitness function. The most fit or promising results are selected for additional iterations, to achieve an overall optimal solution.[7]
Graph traversal
Graph traversal is a technique for finding solutions to problems that can be represented as graphs. This approach is broad, and includes depth-first search, breadth-first search, tree traversal, and many specific variations that may include local optimizations and excluding search spaces that can be determined to be non-optimum or not possible. These techniques may be used to solve a variety of problems including shortest path and constraint satisfaction problems.[8]
Greedy
A greedy approach begins by evaluating one possible outcome from the set of possible outcomes, and then searches locally for an improvement on that outcome. When a local improvement is found, it will repeat the process and again search locally for additional improvements near this local optimum. A greedy technique is generally simple to implement, and these series of decisions can be used to find local optimums depending on where the search began. However, greedy techniques may not identify the global optimum across the entire set of possible outcomes.,[9]
Heuristic
A heuristic approach employs a practical method to reach an immediate solution not guaranteed to be optimal.[10]
Learning
Learning techniques employ statistical methods to perform categorization and analysis without explicit programming. Supervised learning, unsupervised learning, reinforcement learning, and deep learning techniques are included in this category.[11]
Mathematical optimization
Mathematical optimization is a technique that can be used to calculate a mathematical optimum by minimizing or maximizing a function.[12]
Modeling
Modeling is a general technique for abstracting a real-world problem into a framework or paradigm that assists with solution.[13]
Recursion
Recursion is a general technique for designing an algorithm that calls itself with a progressively simpler part of the task down to one or more base cases with defined results.[14][15]
Window sliding
The window sliding is used to reduce the use of nested loop and replace it with a single loop, thereby reducing the time complexity.
See also
Notes
- ^ "technique | Definition of technique in English by Oxford Dictionaries". Oxford Dictionaries | English. Archived from the original on September 28, 2016. Retrieved 2019-03-23.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction To Algorithms. MIT Press. p. 9. ISBN 9780262032933.
- ^ Skiena, Steven S. (1998). The Algorithm Design Manual: Text. Springer Science & Business Media. ISBN 9780387948607.
- ^ "What is brute force? Webopedia Definition". www.webopedia.com. 30 March 1998. Retrieved 2019-03-23.
- ^ Bentley, Jon Louis; Shamos, Michael Ian (1976). "Divide-and-conquer in multidimensional space". Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76. STOC '76. New York, NY, USA: ACM. pp. 220–230. doi:10.1145/800113.803652. S2CID 6400801.
- ^ Bellman, Richard (1966-07-01). "Dynamic Programming". Science. 153 (3731): 34–37. Bibcode:1966Sci...153...34B. doi:10.1126/science.153.3731.34. ISSN 0036-8075. PMID 17730601. S2CID 220084443.
- ^ Coello Coello, Carlos A. (1999-08-01). "A Comprehensive Survey of Evolutionary-Based Multiobjective Optimization Techniques". Knowledge and Information Systems. 1 (3): 269–308. doi:10.1007/BF03325101. ISSN 0219-3116. S2CID 195337963.
- ^ Kumar, Nitin; Wayne, Kevin (2014-02-01). Algorithms. Addison-Wesley Professional. ISBN 9780133799101.
- ^ "greedy algorithm". xlinux.nist.gov. Retrieved 2019-03-23.
- ^ "heuristic". xlinux.nist.gov. Retrieved 2019-03-23.
- ^ Witten, Ian H.; Frank, Eibe; Hall, Mark A.; Pal, Christopher J. (2016-10-01). Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann. ISBN 9780128043578.
- ^ Marler, R.T.; Arora, J.S. (2004-04-01). "Survey of multi-objective optimization methods for engineering". Structural and Multidisciplinary Optimization. 26 (6): 369–395. doi:10.1007/s00158-003-0368-6. ISSN 1615-1488. S2CID 14841091.
- ^ Skiena, Steven S. (1998). The Algorithm Design Manual: Text. Springer Science & Business Media. ISBN 9780387948607.
- ^ "recursion". xlinux.nist.gov. Retrieved 2019-03-23.
- ^ "Programming - Recursion". www.cs.utah.edu. Retrieved 2019-03-23.
External links
- Algorithmic Design and Techniques - edX
- Algorithmic Techniques and Analysis – Carnegie Mellon
- Algorithmic Techniques for Massive Data – MIT
This page was last edited on 23 August 2023, at 17:13