Home | | **An Introduction to Parallel Programming** | | **Multi - Core Architectures and Programming** | Tree Search

Many problems can be solved using a tree search. As a simple example, consider the traveling salesperson problem, or TSP. In TSP, a salesperson is given a list of cities she needs to visit and a cost for traveling between each pair of cities.

**TREE SEARCH**

Many problems can be solved using a tree
search. As a simple example, consider the traveling salesperson problem, or
TSP. In TSP, a salesperson is given a list of cities she needs to visit and a
cost for traveling between each pair of cities. Her problem is to visit each
city once, returning to her hometown, and she must do this with the least
possible cost. A route that starts in her hometown, visits each city once and
returns to her hometown is called a *tour*; thus, the TSP is to find a minimum-cost tour.

Unfortunately, TSP is what’s known as an **NP-complete** problem. From a practi-cal standpoint, this
means that there is no algorithm known for solving it that, in all cases, is
significantly better than exhaustive search. Exhaustive search means exam-ining
all possible solutions to the problem and choosing the best. The number of
possible solutions to TSP grows exponentially as the number of cities is
increased. For example, if we add one additional city to an *n*-city problem, we’ll increase the number of
possible solutions by a factor of *n*-1. Thus, although there are only six possible solutions to a
four-city problem, there are 4 x 6 ** =** 24 to a five-city problem, 5x 24

Furthermore, if we could find a solution to TSP
that’s significantly better in all cases than exhaustive search, then there are
literally hundreds of other very hard problems for which we could find fast
solutions. Not only is there no known solution to TSP that is better in all
cases than exhaustive search, it’s very unlikely that we’ll find one.

So how can we solve TSP? There are a number of
clever solutions. However, let’s take a look at an especially simple one. It’s
a very simple form of tree search. The idea is that in searching for solutions,
we build a *tree.* The leaves of the tree correspond to tours,
and the other tree nodes correspond to “partial” tours—routes that have visited
some, but not all, of the cities.

Each node of the tree has an associated cost,
that is, the cost of the partial tour. We can use this to eliminate some nodes
of the tree. Thus, we want to keep track of the cost of the best tour so far,
and, if we find a partial tour or node of the tree that couldn’t possibly lead
to a less expensive complete tour, we shouldn’t bother searching the children
of that node (see Figures 6.9 and 6.10).

In Figure 6.9 we’ve represented a four-city TSP
as a labeled, directed graph. A **graph **(not to be confused with a graph in calculus) is a collection of
vertices and** **edges or line segments joining pairs of vertices. In a **directed graph** or **digraph**, the edges are oriented—one end of each edge is the tail, and the
other is the head. A graph or digraph is **labeled** if the vertices and/or edges have labels. In our example, the
vertices of the digraph correspond to the cities in an instance of the TSP, the
edges correspond to routes between the cities, and the labels on the edges
correspond to the costs of the routes. For example, there’s a cost of 1 to go
from city 0 to city 1 and a cost of 5 to go from city 1 to city 0.

If we choose vertex 0 as the salesperson’s home
city, then the initial partial tour consists only of vertex 0, and since we’ve
gone nowhere, it’s cost is 0. Thus, the root of the tree in Figure 6.10 has the
partial tour consisting only of the vertex 0 with cost 0. From 0 we can first
visit 1, 2, or 3, giving us three two-city partial tours with costs 1, 3, and
8, respectively. In Figure 6.10 this gives us three chil-dren of the root.
Continuing, we get six three-city partial tours, and since there are

only four cities, once we’ve chosen three of
the cities, we know what the complete tour is.

Now, to find a least-cost tour, we should
search the tree. There are many ways to do this, but one of the most commonly
used is called **depth-first search**. In depth-first search, we probe as deeply as
we can into the tree. After we’ve either reached a leaf or found a tree node
that can’t possibly lead to a least-cost tour, we back up to the deepest
“ancestor” tree node with unvisited children, and probe one of its children as
deeply as possible.

In our example, we’ll start at the root, and
branch left until we reach the leaf labeled

0 ** ->** 1

Then we back up to the tree node labeled 0 ** !** 1, since it is the deepest ancestor node with unvisited children,
and we’ll branch down to get to the leaf labeled

0 ** ->** 1

Continuing, we’ll back up to the root and
branch down to the node labeled 0 ** !** 2. When we visit its child, labeled

0 ** ->** 2

we’ll go no further in this subtree, since
we’ve already found a complete tour with cost less than 21. We’ll back up to 0 ** !** 2 and branch down to its remaining unvisited child. Continuing in
this fashion, we eventually find the least-cost tour

0 ** ->** 3

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.