Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithm design techniques - Coggle Diagram
Algorithm design techniques
They construct candidate solutions one component at a time and evaluate the partially constructed solutions
Backtracking and Branch-and-bound are based on the construction of a state-space tree whose nodes reflect specific choices made for a solution's components. Both techniques terminate a node as soon as it can be guaranteed that no solution can be obtained using that set of choices
Backtracking
definition
If a partially constructed solution can be developed further without violating the problem’s constraints, it is done by taking the first remaining legitimate option for the next component. If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered. In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option.
convenient to implement using state-space tree
convenient to implement using state-space tree
Hamiltonian Circuit Problem
The idea is to find a path from one vertex that passes to all of the other vertices only one time and returns to the first vertex
n-Queens Problem
the problem is to place n queens on an n x n chessboard so that no two queens attack each other
branch-and-bound
Assingment Problem
assigning n people to n jobs so that the total cost of the assignment is as small as possible.
Best-first branch-and-bound
consider a node with the best bound as most promising
Knapsack Problem
given n items of known weights wi and values vi, i = 1, 2, . . . , n, and a knapsack of capacity W , find the most valuable subset of the items that fit in the knapsack.
definition
Works on optimization problems, searching for the best solution of a given problem, unlike backtracking, this technique store the value of the best solution so far and when a partially solution is no better than the best solution so far, the node is considered nonpromising and can be terminated