Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM15 - Coggle Diagram
MM15
Branch-and-Bound
-
provide for every node of a state-space tree a (lower/higher) bound on the best value of the objective function
If the node's bound value is not better than the value of the best solution so far the node is nonpromising and can be terminated
Assignment Problem
-
The cost of any solution cannot be smaller than the sum of the smallest elements in each of the matrix's row (lower bound)
-
-
Knapsack Problem
given n items of known weights wi and values vi and a knapsack of capacity W, find the most valuable subset of the items that fit in the knapsack
-
-
Creates an upper bound with the total value of the items already selected, the product of the remaining capacity of the knapsack and the best per unit payoff among the remaining items
-
Backtracking
state-space tree
-
-
-
-
-
to estime the size of the state-space tree, generate several estimates and compute their avarage
-
n-Queens problem
place n queens on an n x n chessboard so that no two queens attack each other by being in the same row or in the same column or in the same diagonal
-
-
Position a queen in a square and sees if the next can be positioned, if not, backtrack to the previous queen and position it in other square
-
-
the output can be seen as a n-tuple where each coordinate is an element of some finite linearly ordered set Si