Solving
Problems by
Searching-II
PREPARED BY:
MRS. S. R. GHORPADE
Example Problems:
The problem-solving approach has been applied to a vast array of
task environments. We list some of the best known Problems,
distinguishing between toy and real-world problems.
Toy Problem:
intended to illustrate or exercise various problem-solving
methods.
It can be given a concise, exact description and hence is
usable by different researchers to compare the performance of
algorithms.
Real World Problem:
is one whose solutions people actually care about.
Such problems tend not to have a single agreed-upon
description.
Toy problems -Vacuum
[Link]
States: The state is determined by both the agent location and the dirt
locations. The agent is in one of two locations, each of which might or might
not contain dirt. Thus, there are (2 × 2^2 = 8) possible world states. A larger
environment with n locations has (n .2^n) states.
2. Initial state: Any state can be designated as the initial state.
3. Actions: In this simple environment, each state has just three actions: Left,
Right, and Suck. Larger environments might also include Up and Down.
4. Transition model: The actions have their expected effects, except that
moving Left in the leftmost square, moving Right in the rightmost square,
and Sucking in a clean square have no effect. The complete state space is
shown in Figure
5. Goal test: This checks whether all the squares are clean.
6. Path cost: Each step costs 1, so the path cost is the number of steps in the
path.
The state space for the vacuum world. Links denote actions: L =
Left, R = Right, S = Suck.
Toy problems - 8-puzzle
1. States: A state description specifies the location of each of the eight tiles and
the blank in one of the nine squares.
2. Initial state: Any state can be designated as the initial state. Note that any
given goal can be reached from exactly half of the possible initial states
3. Actions: The simplest formulation defines the actions as movements of the
blank space Left, Right, Up, or Down. Different subsets of these are possible
depending on where the blank is.
4. Transition model: Given a state and action, this returns the resulting state;
for example, if we apply Left to the start state in Figure 3.4, the resulting
state has the 5 and the blank switched.
5. Goal test: This checks whether the state matches the goal configuration
shown in Figure.
6. Path cost: Each step costs 1, so the path cost is the number of steps in the
path.
A typical instance of the 8-puzzle.
Toy problems -8-queens problem
1. States: Any arrangement of 0 to 8 queens on the board is a state.
2. Initial state: No queens on the board.
3. Actions: Add a queen to any empty square.
4. Transition model: Returns the board with a queen added to the specified
square.
5. Goal test: 8 queens are on the board, none attacked. In this formulation,
we have 64 ・ 63 ・ ・ ・ 57 ≈ 1.8×1014 possible sequences to
investigate. A better formulation would prohibit placing a queen in any
square that is already attacked:
6. States: All possible arrangements of n queens (0 ≤ n ≤ 8), one per column
in the leftmost n columns, with no queen attacking another.
7. Actions: Add a queen to any square in the leftmost empty column such
that it is not attacked by any other queen.
Almost a solution to the 8-queens problem.
Toy problems - Infinite state spaces
Our final toy problem was devised by Donald Knuth (1964) and illustrates
how infinite state spaces can arise. Knuth conjectured that, starting with the
number 4, a sequence of factorial, square root, and floor operations will
reach any desired positive integer. For example, we can reach 5 from 4 as
follows: (4!)! = 5 .
The problem definition is very simple:
1. States: Positive numbers.
2. Initial state: 4.
3. Actions: Apply factorial, square root, or floor operation (factorial for
integers only).
4. Transition model: As given by the mathematical definitions of the
operations.
5. Goal test: State is the desired positive integer.
Real-world problems
The route-finding problem ROUTE-FINDING is defined
in terms of specified locations and transitions along links
between them.
Route-finding algorithms are used in a variety of
applications.
Some, such as Web sites and in-car systems that provide
driving directions, are relatively straightforward extensions
of the Romania example.
Others, such as routing video streams in computer
networks, military operations planning, and airline travel-
planning systems, involve much more complex
specifications.
Airline Travel Problems
1. States: Each state obviously includes a location (e.g., an airport) and the
current time. Furthermore, because the cost of an action (a flight segment)
may depend on previous segments, their fare bases, and their status as
domestic or international, the state must record extra information about these
“historical” aspects.
2. Initial state: This is specified by the user’s query.
3. Actions: Take any flight from the current location, in any seat class, leaving
after the current time, leaving enough time for within-airport transfer if
needed.
4. Transition model: The state resulting from taking a flight will have the
flight’s destination as the current location and the flight’s arrival time as the
current time.
5. Goal test: Are we at the final destination specified by the user?
6. Path cost: This depends on monetary cost, waiting time, flight time, customs
and immigration procedures, seat quality, time of day, type of airplane,
frequent-flyer mileage awards, and so on.
Real-world problems
TOURING PROBLEM are closely related to route-finding problems, but
with an important difference.
Consider, for example, the problem “Visit every city at least once, starting
and ending in Bucharest.”
As with route finding, the actions correspond to trips between adjacent
cities.
The state space, however, is quite different. Each state must include not just
the current location but also the set of cities the agent has visited.
So the initial state would be In(Bucharest ), Visited({Bucharest}), a typical
intermediate state would be In(Vaslui ), Visited({Bucharest , Urziceni ,
Vaslui}),
The goal test would check whether the agent is in Bucharest and all 20
cities have been visited.
Real-world problems
The city TRAVELING SALESPERSON PROBLEM (TSP) is a
touring problem in which each must be visited exactly once.
The aim is to find the shortest tour.
The problem is known to be NP-hard, but an enormous amount of effort
has been expended to improve the capabilities of TSP algorithms.
In addition to planning trips for traveling salespersons, these algorithms
have been used for tasks such as planning movements of automatic
circuit-board drills and of stocking machines on shop floors.
Real-world problems
A VLSI LAYOUT PROBLEM requires positioning millions of
components and connections on a chip to minimize area, minimize circuit
delays, minimize stray capacitances, and maximize manufacturing yield.
The layout problem comes after the logical design phase and is usually split
into two parts: cell layout and channel routing.
In cell layout, the primitive components of the circuit are grouped into cells,
each of which performs some recognized function. Each cell has a fixed
footprint (size and shape) and requires a certain number of connections to
each of the other cells. The aim is to place the cells on the chip so that they
do not overlap and so that there is room for the connecting wires to be
placed between the cells.
Channel routing finds a specific route for each wire through the gaps
between the cells. These search problems are extremely complex, but
definitely worth solving. Later in this chapter, we present some algorithms
capable of solving them.
Real-world problems
Robot navigation is a generalization of the route-finding problem described
earlier.
Rather than following a discrete set of routes, a robot can move in a
continuous space with (in principle) an infinite set of possible actions and
states.
For a circular robot moving on a flat surface, the space is essentially two-
dimensional.
When the robot has arms and legs or wheels that must also be controlled, the
search space becomes many-dimensional.
Advanced techniques are required just to make the search space finite.
In addition to the complexity of the problem, real robots must also deal with
errors in their sensor readings and motor controls.
Real-world problems
AUTOMATIC ASSEMBLY SEQUENCING of complex objects by a
robot was first demonstrated by FREDDY (Michie, 1972).
Progress since then has been slow but sure, to the point where the assembly
of intricate objects such as electric motors is economically feasible.
In assembly problems, the aim is to find an order in which to assemble the
parts of some object.
If the wrong order is chosen, there will be no way to add some part later in
the sequence without undoing some of the work already done.
Checking a step in the sequence for feasibility is a difficult geometrical
search problem closely related to robot navigation.
Thus, the generation of legal actions is the expensive part of assembly
sequencing.
Any practical algorithm must avoid exploring all but a tiny fraction of the
state space.
Real-world problems
Another important assembly problem is PROTEIN
DESIGN , in which the goal is to find a sequence of amino
acids that will fold into a three-dimensional protein with the
right properties to cure some disease.
Thank You