Algorithm Types

  • Algorithms that use a similar problem-solving approaches can be grouped together. We can classify algorithms in these groups:

    • Brute-force algorithms generate every possible answer and select only the valid ones.

    • Greedy algorithms picks the “best” next partial solution (aka locally optimal solution) from the current partial solution at every step and may not always produce an optimal solution.

    • Backtracking algorithms solve constraint satisfaction problems and find a single solution or all solution by using a search tree method to generate permutations of solutions and by exploring only “valid” branches of the search tree, eliminating invalid partial solutions along the way.

    • Branch-and-bound algorithms solve optimization problems and find the best solution also by using a search tree, eliminating the branches that will not lead to a better solution that the one currently known.

    • Divide-and-conquer algorithms divides a problem into multiple non-overlapping subproblems to construct a solution.

    • Dynamic programming algorithms divides a problem into multiple overlapping subproblems and build a solution (either bottom-up or top-down) only calculating the solution to a given subproblem once.

  • This classification scheme is neither exhaustive nor disjoint. The purpose is to highlight the various ways in which problems can be solved, so that we can apply similar techniques when solving new problems.

results matching ""

    No results matching ""