Exhaustive Search:
1. Traveling Salesman Problem
2. Knapsack Problem
3. Assignment Problem
4. Exercises

**Exhaustive
Search**

*Exhaustive Search:*

*1. Traveling Salesman Problem*

*2. Knapsack Problem*

*3. Assignment Problem*

*4. Exercises*

Many
important problems require finding an element with a special property in a domain
that grows exponentially (or faster) with an instance size. Typically, such
problems arise in situations that involve—explicitly or
implicitly—combinatorial objects such as permutations, combinations, and
subsets of a given set. Many such problems are optimization problems: they ask
to find an element that maximizes or minimizes some desired characteristic such
as a path length or an assignment cost.

** Exhaustive
search **is simply a brute-force approach to combinatorial
prob-lems. It suggests generating each and every element of the problem domain,
se-lecting those of them that satisfy all the constraints, and then finding a
desired element (e.g., the one that optimizes some objective function). Note
that although the idea of exhaustive search is quite straightforward, its
implementation typically requires an algorithm for generating certain
combinatorial objects. We delay a dis-cussion of such algorithms until the next
chapter and assume here that they exist.

We
illustrate exhaustive search by applying it to three important problems: the
traveling salesman problem, the knapsack problem, and the assignment problem.

**Traveling
Salesman Problem**

The ** traveling
salesman problem (TSP)** has been intriguing researchers for the last 150
years by its seemingly simple formulation, important applications, and
interesting connections to other combinatorial problems. In layman’s terms, the
problem asks to find the shortest tour through a given set of

It is
easy to see that a Hamiltonian circuit can also be defined as a sequence of ** n **+

An
inspection of Figure 3.7 reveals three pairs of tours that differ only by their
direction. Hence, we could cut the number of vertex permutations by half. We
could, for example, choose any two intermediate vertices, say, ** b** and

This
improvement cannot brighten the efficiency picture much, however. The total
number of permutations needed is still _{2}^{1}** (n** − 1

**Knapsack
Problem**

Here is
another well-known problem in algorithmics. Given ** n** items of
known weights

valuable
loot that fits into his knapsack, think about a transport plane that has to
deliver the most valuable set of items to a remote location without exceeding
the plane’s capacity. Figure 3.8a presents a small instance of the knapsack
problem.

The
exhaustive-search approach to this problem leads to generating all the subsets
of the set of ** n** items
given, computing the total weight of each subset in order to identify feasible
subsets (i.e., the ones with the total weight not exceeding the knapsack
capacity), and finding a subset of the largest value among them. As an example,
the solution to the instance of Figure 3.8a is given in Figure 3.8b. Since the
number of subsets of an

Thus, for
both the traveling salesman and knapsack problems considered above, exhaustive
search leads to algorithms that are extremely inefficient on every input. In
fact, these two problems are the best-known examples of so-called ** NP-hard
problems**. No polynomial-time algorithm is known for any

similar
problems in less than exponential time. Alternatively, we can use one of many
approximation algorithms, such as those described in Section 12.3.

**Assignment
Problem**

In our
third example of a problem that can be solved by exhaustive search, there are ** n** people who need to be assigned
to execute

A small
instance of this problem follows, with the table entries representing the
assignment costs ** C**[

It is
easy to see that an instance of the assignment problem is completely specified
by its cost matrix ** C.** In terms
of this matrix, the problem is to select one element in each row of the matrix
so that all selected elements are in different columns and the total sum of the
selected elements is the smallest possible. Note that no obvious strategy for
finding a solution works here. For example, we cannot select the smallest
element in each row, because the smallest elements may happen to be in the same
column. In fact, the smallest element in the entire matrix need not be a
component of an optimal solution. Thus, opting for the exhaustive search may
appear as an unavoidable evil.

We can
describe feasible solutions to the assignment problem as ** n**-tuples

Since the
number of permutations to be considered for the general case of the assignment
problem is ** n**!, exhaustive search is
impractical for all but very small instances of the problem. Fortunately, there
is a much more efficient algorithm for this problem called the

This is
good news: the fact that a problem domain grows exponentially or faster does
not necessarily imply that there can be no efficient algorithm for solving it.
In fact, we present several other examples of such problems later in the book.
However, such examples are more of an exception to the rule. More often than
not, there are no known polynomial-time algorithms for problems whose domain
grows exponentially with instance size, provided we want to solve them exactly.
And, as we mentioned above, such algorithms quite possibly do not exist.

**Exercises
3.4**

** **1. **a. **Assuming
that each tour can be generated in constant time, what will be** **the efficiency class of the
exhaustive-search algorithm outlined in the text for the traveling salesman
problem?

** **b. If this algorithm is programmed on a computer that
makes ten billion additions per second, estimate the maximum number of cities
for which the problem can be solved in

**i. **1 hour. **ii. **24 hours. **iii. **1 year. **iv. **1 century.

** **2. Outline an exhaustive-search algorithm for the
Hamiltonian circuit problem.

** **3. **
**Outline an algorithm to determine whether a
connected graph represented by its adjacency matrix has an Eulerian circuit.
What is the efficiency class of your algorithm?

** **4. **
**Complete the application of exhaustive search to
the instance of the assign-ment problem started in the text.

5. Give an
example of the assignment problem whose optimal solution does not include the
smallest element of its cost matrix.

** **6. Consider the ** partition problem**: given

** **7. **
**Consider the ** clique problem**: given a graph

** **8. Explain how exhaustive search can be applied to the
sorting problem and determine the efficiency class of such an algorithm.

** **9. *Eight-queens
problem *Consider the classic puzzle of placing eight queens on* *an 8 × 8 chessboard
so that no two queens are in the same row or in the same column or on the same
diagonal. How many different positions are there so that

**
**no two queens are on the same square?

**
**no two queens are in the same row?

**
**no two queens are in the same row or in the same
column?

Also
estimate how long it would take to find all the solutions to the problem by
exhaustive search based on each of these approaches on a computer capable of
checking 10 billion positions per second.

** **10. **
***Magic
squares *A magic square of order* **n** *is an
arrangement of the integers* *from 1 to
*n*^{2} in an ** n** ×

**
**Prove that if a magic square of order ** n** exists, the sum in question must
be equal to

**
**Design an exhaustive-search algorithm for
generating all magic squares of order *n.*

**
**Go to the Internet or your library and find a
better algorithm for generating magic squares.

**
**Implement the two algorithms—the exhaustive search
and the one you have found—and run an experiment to determine the largest value
of ** n** for which each of the algorithms
is able to find a magic square of order

11. *Famous alphametic *A puzzle
in which the digits in a correct mathematical* *expression, such as a sum, are replaced by letters is called ** cryptarithm**;
if, in addition, the puzzle’s words make sense, it is said to be an

Two
conditions are assumed: first, the correspondence between letters and decimal
digits is one-to-one, i.e., each letter represents one digit only and
dif-ferent letters represent different digits. Second, the digit zero does not
appear as the left-most digit in any of the numbers. To solve an alphametic
means to find which digit each letter represents. Note that a solution’s
uniqueness cannot be assumed and has to be verified by the solver.

**
**Write a program for solving cryptarithms by
exhaustive search. Assume that a given cryptarithm is a sum of two words.

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

Introduction to the Design and Analysis of Algorithms : Brute Force and Exhaustive Search : Exhaustive Search |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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