Data Structure Unit 5
- Greedy which is based on the idea to repeatedly make the decision which according to some criterion appears best without ever undoing decisions. Greedy algorithms are general and efficient, but for many problems they do not give the best possible solutions. Only for matroids the greedy algorithm is guaranteed to find the optimum.
- Dynamic-programming which is a way to prevent a recursive explosion by using a table. It is generally applicable whenever the “principal of optimality” holds. It is relatively inefficient, particularly if one performs a conventional bottom-up approach computing all values in the table, even those that are not needed. In that case further problems can be solved fast. For solving single problems it is often better to choose the top-down approach, which is not more than solving a problem recursively, using a table to look-up values of earlier solved subproblems. The memory usage can be reduced by replacing the table by a set data structure.
- Backtracking which is an optimized method to traverse an (implicit) graph of partial solutions. Only branches corresponding to partial solutions that still might lead to a complete solution, called “promising”, are further developed. Backtracking is mainly thought for finding solutions to decision problems. It is particularly useful in games for determining a winning strategy. Focusing the search may give great performance improvements. Backtracking can also be used for optimization problems, but then the entire tree has to be evaluated which is possible only for small problems.
- Branch-and-bound which is the natural improvement of backtracking for optimization problems. Assume we are considering a minimization problem. The idea is to maintain at all times upper and lower bounds on the achievable values. If after a certain number of decisions (branching operations) we come to a node for which the lower bound is larger than or equal to an already established upper bound, then there is no need to further develop this branch. For maximization problems the rule is reversed: as soon as the upper bound is smaller than or equal to an earlier established lower bound the branch is cut.