Editing Algorithm (section)

=== Optimization problems ===
For [[optimization problem]]s there is a more specific classification of algorithms; an algorithm for such problems may fall into one or more of the general categories described above as well as into one of the following:

; [[Linear programming]]
: When searching for optimal solutions to a linear function bound by linear equality and inequality constraints, the constraints can be used directly to produce optimal solutions. There are algorithms that can solve any problem in this category, such as the popular [[simplex algorithm]].<ref>
[[George B. Dantzig]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.</ref> Problems that can be solved with linear programming include the [[maximum flow problem]] for directed graphs. If a problem also requires that any of the unknowns be [[integer]]s, then it is classified in [[integer programming]]. A linear programming algorithm can solve such a problem if it can be proved that all restrictions for integer values are superficial, i.e., the solutions satisfy these restrictions anyway. In the general case, a specialized algorithm or an algorithm that finds approximate solutions is used, depending on the difficulty of the problem.
; [[Dynamic programming]]
: When a problem shows optimal substructures—meaning the optimal solution can be constructed from optimal solutions to subproblems—and [[overlapping subproblem]]s, meaning the same subproblems are used to solve many different problem instances, a quicker approach called ''dynamic programming'' avoids recomputing solutions. For example, [[Floyd–Warshall algorithm]], the shortest path between a start and goal vertex in a weighted [[graph (discrete mathematics)|graph]] can be found using the shortest path to the goal from all adjacent vertices. Dynamic programming and [[memoization]] go together. Unlike divide and conquer, dynamic programming subproblems often overlap. The difference between dynamic programming and simple recursion is the caching or memoization of recursive calls. When subproblems are independent and do not repeat, memoization does not help; hence dynamic programming is not applicable to all complex problems. Using memoization dynamic programming reduces the complexity of many problems from exponential to polynomial.
; The greedy method
: [[Greedy algorithm]]s, similarly to a dynamic programming, work by examining substructures, in this case not of the problem but of a given solution. Such algorithms start with some solution and improve it by making small modifications. For some problems, they always find the optimal solution but for others they may stop at [[local optimum|local optima]]. The most popular use of greedy algorithms is finding minimal spanning trees of graphs without negative cycles. [[Huffman coding|Huffman Tree]], [[kruskal's algorithm|Kruskal]], [[Prim's algorithm|Prim]], [[Sollin's algorithm|Sollin]] are greedy algorithms that can solve this optimization problem.
;The heuristic method
:In [[optimization problem]]s, [[heuristic algorithm]]s find solutions close to the optimal solution when finding the optimal solution is impractical. These algorithms get closer and closer to the optimal solution as they progress. In principle, if run for an infinite amount of time, they will find the optimal solution. They can ideally find a solution very close to the optimal solution in a relatively short time. These algorithms include [[local search (optimization)|local search]], [[tabu search]], [[simulated annealing]], and [[genetic algorithm]]s. Some, like simulated annealing, are non-deterministic algorithms while others, like tabu search, are deterministic. When a bound on the error of the non-optimal solution is known, the algorithm is further categorized as an [[approximation algorithm]].