Algorithm: Difference between revisions

Revision as of 01:25, 19 May 2025

Revision as of 01:34, 19 May 2025

Line 124:

: Brute force is a problem-solving method of systematically trying every possible option until the optimal solution is found. This approach can be very time-consuming, testing every possible combination of variables. It is often used when other methods are unavailable or too complex. Brute force can solve a variety of problems, including finding the shortest path between two points and cracking passwords.

; Divide and conquer

: A [[divide-and-conquer algorithm]] repeatedly reduces a problem to one or more smaller instances of itself (usually [[recursion|recursively]]) until the instances are small enough to solve easily. [[mergesort|Merge sorting]] is an example of divide and conquer, where an unordered list canis berepeatedly dividedsplit into segmentssmaller containinglists, onewhich itemare sorted in the same way and sortingthen ofmerged.<ref>{{cite thebook|title=Algorithm entireDesign: listFoundations, canAnalysis, beand obtainedInternet byExamples|first1=Michael mergingT.|last1=Goodrich|first2=Roberto|last2=Tamassia|publisher=John theWiley segments& Sons|year=2001|isbn=9780471383659|contribution=5.2 ADivide and Conquer|page=263}}</ref> In a simpler variant of divide and conquer is called a[[prune and search]] or ''decrease-and-conquer algorithm'', which solves one smaller instance of itself, and usesdoes thenot solutionrequire toa solvemerge the bigger problem. Divide and conquer divides the problem into multiple subproblems and so the conquer stage is more complex than decrease and conquer algorithmsstep.{{Citation neededsfnp|dateGoodrich|Tamassia|2001|loc=October4.7.1 2024Prune-and-search|p=245}} An example of a decreaseprune and conquersearch algorithm is the [[binary search algorithm]].

; Search and enumeration

: Many problems (such as playing [[Chess|ches]]s) can be modelled as problems on [[graph theory|graph]]s. A [[graph exploration algorithm]] specifies rules for moving around a graph and is useful for such problems. This category also includes [[search algorithm]]s, [[branch and bound]] enumeration, and [[backtracking]].