Branch
and Bound
The branch and bound approach are based on the
principle that the total set of feasible solutions can be partitioned into
smaller subsets of solutions.
LC (Least Cost) branch and bound search /
LCBB search
Definition of LCBB
The
least-cost method of branch and bound selects the next node based on the
Heuristic Cost Function,
It uses a heuristic cost function to compute the bound
values at each node. Nodes are added to the list of live nodes as soon as they
get generated.
The node with the least value of a cost function selected as a next E-node.
Bounding function
Bounding function is needed to help kill some
live nodes without actually expanding them. A good bounding function for this
problem is obtained by using an upper bound on the value of the best feasible
solution obtainable by expanding the given live node and any of its
descendants.
Ranking function
ranking function we will calculate the cost of each
node.
Branch and Bound solution have three types
of strategies:
FIFO (first in and first out) branch and
bound.
LIFO (last in and first out) branch and
bound.
Least Cost branch and bound.
FIFO BB (branch and bound) Search
FIFO branch and bound search is the one that follows
the BFS like method. It does so as the list follows first in and first out.
Traveling Salesperson problem
Travelling
Salesman Problem (TSP) is an interesting problem. Problem is defined as “given
n cities and distance between each pair of cities, find out the path which
visits each city exactly once and come back to starting city, with the
constraint of minimizing the travelling distance.
Given the vertices, the problem here is that we have
to travel each vertex exactly once and reach back to the starting point.
Formulation using LCBB
The least-cost method of branch and bound selects the
next node based on the Heuristic Cost Function, and it picks the one with the
least count, therefore it is one of the best methods
h(x) is the cost of reaching from x to root.
In LC search, the cost function c(.) is defined as
follows:
If x is the answer node, then c(x) is the cost of
reaching x from the root
If x is not the answer node and the subtree of x does
not contain the answer node then c(x) = ∞
Otherwise, c(x) is the cost of the minimum cost answer
node in subtree x.
Milan Tomic
Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.
0 comments:
Post a Comment