Dynamic programming vs. Greedy vs. Partitioning vs. Backtracking algorithm

When beginners hear about algorithms, they will think they are so profound that they can go away. But as long as we understand the critical points of algorithmic ideas, practice more problems, and deepen our understanding and memory, we will not scare by the inertia in our brain. Discovering the algorithm is as simple as cutting vegetables. Algo.monster will mainly compare the four algorithmic ideas – dynamic programming and greedy, partitioning, and backtracking – to see the differences and connections between them. See it on fastwebpost.com.

If we categorize these four algorithmic ideas, greedy, backtracking, and dynamic programming can be into one category, while partitioning can be a separate category. The reason is that the first three algorithms solve problems with models that can be abstracted into this section’s multi-stage decision optimal solution model, while the partitioning algorithms solve problems that, although most of them are also optimal solution problems. And they cannot be abstracted into multi-stage decision models.

Dynamic programming

The design of the dynamic programming algorithm can be divided into four steps as follows.

– Describe the structure of the optimal solution

– Recursively defining the value of the optimal solution

– Calculate the value of the optimal solution in a bottom-up manner

– Constructing an optimal solution from the computed results

The partitioning method divides the problem into independent subproblems, solves each subproblem recursively, and then combines the solutions of the subproblems to resolve the original issue. In contrast, dynamic programming applies to the case where the subproblems are independent and overlapping, i.e., each subproblem contains a common subproblem. In this case, the partitioning method would do unnecessary work, i.e., solving the common subproblems repeatedly. The dynamic programming algorithm solves each sub-subproblem only once and saves its results in a table. Thus it’s avoiding recalculating the answer each time encountering the individual subproblem.

It may seem strange that dynamic programming requires its subproblems to be both independent and overlapping. Although these two requirements may sound contradictory, they describe two different concepts, not two aspects of the same problem. Two subproblems of the same issue are independent if they do not share resources. Two subproblems are overlapping if they are indeed the same subproblem but appear as subproblems of different problems. Then they overlap.

Backtracking algorithm

The backtracking algorithm is a “jack-of-all-trades.” A backtracking algorithm can solve any problem that can be solved by dynamic programming and greedy. The backtracking algorithm is equivalent to an exhaustive search. All cases are exhausting and then compared to get the optimal solution. However, the time complexity of the backtracking algorithm is very high and exponential, so it can only solve problems with small-scale data. For issues with large-scale data, the execution efficiency of solving with a backtracking algorithm is very low.

Partitioning algorithm

Although dynamic programming is more efficient than the backtracking algorithm, dynamic programming cannot solve all problems. The problems that can be solved by dynamic programming need to satisfy three characteristics, optimal substructure, no posteriority, and repeated subproblems. The distinction between dynamic programming and partitioning algorithms is evident on the point of repeating subproblems. Partitioning algorithms require partitioning into subproblems that cannot have duplicate subproblems, while dynamic programming is the opposite. Dynamic programming is efficient because of the large number of duplicate subproblems in the backtracking algorithm implementation.

In a word, partitioning — each subproblem is independent; dynamic programming — each subproblem overlaps.

The partitioning model has three steps at each level of recursion.

– Decomposition (Divide): decomposing the original problem into a series of subproblems.

– Solve (Conquer): recursively solve each subproblem. If the subproblems are small enough, they will be solved directly.

– Combine: Combine the results of the subproblems into the solution of the original problem.

Merge Sort is an example of a typical partitioning method. The corresponding intuitive operation is as follows:

Decomposition: dividing n elements into subsequences containing n/2 elements each.

Solving: sorting the two subsequences recursively using the Merge Sort.

Merge: Merge the two sorted subsequences to obtain the sorted result.

Greedy algorithm

The greedy algorithm is a special case of a dynamic programming algorithm. In particular, the problem to which the greedy algorithm applies is also the optimal substructure. One significant difference between the greedy algorithm and dynamic programming is that the greedy algorithm uses the optimal substructure in a top-down manner. Instead of first finding the optimal solution to the subproblem and then making a choice, which appears to be optimal at the time, the greedy algorithm will first make a choice and then solve a resultant subproblem.

The greedy algorithm is more efficient in solving the problem, and implementing it in code will be more concise. However, it is also more limited in terms of the problems it can solve. The problem it can solve is the need to satisfy three conditions, optimal substructure, no posteriority, and greedy selectivity (we do not emphasize repeated subproblems here). Among them, optimal substructure and no posteriority are no different from those in dynamic programming. The term “greedy selectivity” means that a locally optimal choice can produce a globally optimal choice. At each stage, we choose the decision that seems optimal at the moment. After all the steps are over, these locally optimal solutions form the optimal global solution finally.

Understanding the four algorithmic ideas in one sentence

Four algorithmic ideas. Greedy, backtracking, and dynamic programming can solve similar problem models. All of which can be into a multi-stage decision optimal solution model. Although partitioning algorithms can also solve optimal problems, the context of most problems does not lend itself to abstraction into a multi-stage decision model.

Dynamic programming: It’s god’s perspective, with the history of an infinite number of parallel universes archived in hand while developing an unlimited number of futures.

Partitioning: Divide and conquer, solving the subproblems first and then merging the solutions of the subproblems to find the original problem.

Greedy: It’s a path to black, choose the locally optimal route of the moment. There is no regret medicine.

Backtracking: It’s a path to black, with regret pills in hand and the ability to start over countless times.