Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking, Optimization problem, Branch-and-bound, Constructs a partial…
-
-
Branch-and-bound
- Used to solve larger instances of intractable problems
- In it's worst case, still intractable
- Better than exhaustive search
Constructs a partial solution, if this one is not promising, it goes back and try a different one
-
-
-
- construct solutions one component at a time and evaluate such partially constructed candidates as follows, if a partially constructed solution can be developed further without violating the problems's constraints, it is done by taking the first remaining legitimate option for the next component
- State-space trees:
- Is promising if it correspond to a partially constructed solution that may stilled to a complete solution.
- Is nonpromising if the tree is not promising
- State-space trees: the nodes of the first level in the tree represent the choices made for the first component of a solution, the ones of the second level represent the coices for the second component, and so on
Problems:
- Subset-Sum
- Hamiltonian Circuit
- n-Queens
Seeks to minimize or maximize some objective function, usually subject to some constraints
- compared to Backtracking it has two additional items: the value of the best solution seen so far and a bound
on the best value of the objective function for each node of the state-space tree
Problems:
- Assignment
- Knapsack
- Traveling Salesman
-