Please enable JavaScript.
Coggle requires JavaScript to display documents.
COPING WITH THE LIMITATIONS OF THE ALGORITHM POWER - Coggle Diagram
COPING WITH THE LIMITATIONS OF THE ALGORITHM POWER
BACKTRACKING
HAMILTONIAN CIRCUIT PROBLEM
STATE-SPACE TREE
PROMISSING
NONPROMISSING
N-QUEENS PROBLEM
SUBSET-SUM PROBLEM
GENERAL REMARKS
BRANCH-AND-BOUND
FEASIBLE SOLUTION
OPTIMAL SOLUTION
ASSIGNMENT PROBLEM
KNAPSACK PROBLEM
TRAVELING SALESMAN PROBLEM
BRANCH-AND-BOUND REQUIRES TWO ADDITIONAL ITEMS:
A WAY TO PROVIDE, FOR EVERY NODE OF A STATE-SPACE TREE, A BOUND ON THE BEST VALUE OF THE OBJECTIVE FUNCTION1 ON ANY SOLUTION THAT CAN BE OBTAINED BY ADDING FURTHER COMPONENTS TO THE PARTIALLY CONSTRUCTED SOLUTION REPRESENTED BY THE NODE
THE VALUE OF THE BEST SOLUTION SEEN SO FAR
IN GENERAL, WE TERMINATE A SEARCH PATH AT THE CURRENT NODE IN A STATE-SPACE TREE OF A BRANCH-AND-BOUND ALGORITHM FOR ANY ONE OF THE FOLLOWING THREE REASONS:
THE VALUE OF THE NODE’S BOUND IS NOT BETTER THAN THE VALUE OF THE BEST SOLUTION SEEN SO FAR.
THE NODE REPRESENTS NO FEASIBLE SOLUTIONS BECAUSE THE CONSTRAINTS OF THE PROBLEM ARE ALREADY VIOLATED.
THE SUBSET OF FEASIBLE SOLUTIONS REPRESENTED BY THE NODE CONSISTS OF A SINGLE POINT (AND HENCE NO FURTHER CHOICES CAN BE MADE)—IN THIS CASE, WE COMPARE THE VALUE OF THE OBJECTIVE FUNCTION FOR THIS FEASIBLE SOLUTION WITH THAT OF THE BEST SOLUTION SEEN SO FAR AND UPDATE THE LATTER WITH THE FORMER IF THE NEW SOLUTION IS BETTER.