Artificial Intelligence
Searching
Searching
Dr. Saleh Abu-Soud 1 Artificial Intelligence – Introduction to Searching
➣ State–space vs. Problem–reduction
➪ State–Space (Forward chaining):
to start with an initial state and reach a goal.
➪ Problem–Reduction (Backward chaining):
to start with the problem and try to prove it.
Dr. Saleh Abu-Soud 2 Artificial Intelligence – Introduction to Searching
1- State-Space Representation
➪ Puzzles and games provide a rich source of
example problems useful for illustrating and
testing problem-solving methods.
➪ Minsky says “It is not that the games and
mathematical problems are chosen because they are
clear and simple; rather it is that they give us, for the
smallest initial structures, the greatest complexity”.
➪ Board games are easy to play and understand
and suite a class problem.
Dr. Saleh Abu-Soud 3 Artificial Intelligence – Introduction to Searching
➪ A 15-Puzzle games is an example.
➪ With 15-Puzzle you can construct !16= (1.1 x 1013).
➪ 8-Puzzle is another example.
➪ The most straight forward approach is finding a
solution
to the 8-puzzle would be to try out various moves until
we happened to produce the goal configuration.
Dr. Saleh Abu-Soud 4 Artificial Intelligence – Introduction to Searching
➪ Such an attempt involves essentially a trial-and-error
search.
➪ Starting with the initial configuration, we might
compute the configuration produced by one or more
move, and so on until the goal configuration is reached.
➪ The initial and goal configurations are the initial and goal
states.
➪ The space of states reachable from the initial state
consists
of all of those tile configurations that can be produced by
moving tiles around in the
Dr. Saleh Abu-Soud 5
legal manner.
Artificial Intelligence – Introduction to Searching
➪ Many of the problems with which we shall be concerned
will have extremely large (if not infinite) state space.
➪ An operator transforms one state into another state.
e.g. a 15-Puzzle game has 4 operators.
➪ So, a solution to the 15-puzzle could be obtained by a
search process that first applies operators to the initial
state to produce new states, and the applies operators to
these, and so on until the goal state is produced.
➪ Any problem-solution method that relies on these ideas
of states & operators could be said to use state-space
approach to problem solving.
Dr. Saleh Abu-Soud 6 Artificial Intelligence – Introduction to Searching
Dr. Saleh Abu-Soud 7 Artificial Intelligence – Introduction to Searching
2- Reducing problems to sub problems
( Problem-Reduction )
➪ A somewhat more sophisticated problem-solving
approach involves the notion of sub problems.
➪ In some approaches, an analysis is made to the
original problem in order to produce a set of sub
problems such that solutions to some particular
subset of the sub problems would imply a solution to
the original problem.
Dr. Saleh Abu-Soud 8 Artificial Intelligence – Introduction to Searching
Example : a travel from Amman to Cairo.
here a solution to all of the sub problems would produce
a solution to the original problem.
➪ Each of the sub problems can be solved by any method
what so ever.
➪ They might be attacked by the state-space methods or they
themselves might be analyzed to produce sub problems.
➪ Eventually some primitive problems will be reached
whose solutions are trivial.
Dr. Saleh Abu-Soud 9 Artificial Intelligence – Introduction to Searching
➪ Any method that solves problems by generating and then
solving sub problems will be said to employ a
problem-reduction approach.
➪ Note that the state-space approach can be regarded as a
trivial case of problem-reduction approach:
Each operator application reduces a problem to a slightly
simpler sub problems.
➪ It is important to note that trial-and-error search still plays
an important role in the problem-reduction approach.
At any stage there may be several alternative sets of
sub problems to which some given problem may
be reduced.
Dr. Saleh Abu-Soud 10 Artificial Intelligence – Introduction to Searching
➪ Since some of there sets might not ultimately lead to a
final solution, one needs typically to search through a
space of sub problem sets in order to solve the original
problem.
Dr. Saleh Abu-Soud 11 Artificial Intelligence – Introduction to Searching
➣ The use of logic in problem solving
➪ Frequently the solution to a problem either requires or
is aided by a certain amount of logical analysis.
➪ Some times such an analysis shows that certain problems
are insoluble.
➪ The need to perform logical deductions can arise in both
the state-space and problem-reduction approaches.
➪ In the state-space approach, the test used to determine
what is not a state is a goal state might require logical
deductions.
Dr. Saleh Abu-Soud 12 Artificial Intelligence – Introduction to Searching
➪ Additionally, one may have to make logical deductions
to determine which operators are applicable in a given
state..
➪ Thus a complete treatment of problem-solving techniques
must include a discussion of mechanical proof-finding
methods.
➪ Some of these methods use search strategies.
➪ Resolution theorem-proving techniques is another example
Dr. Saleh Abu-Soud 13 Artificial Intelligence – Introduction to Searching
➣ Elements of problem solving
1- Representation, and
2- Search
➪ Each of the approaches to problem solving that we have
mentioned requires some sort of search for a solution.
➪ We will try to show how to conduct there searches as
efficiently as possible.
➪ There are alternative representations for the same problem
➪ Since even the most efficient search methods will be
inadequate if the space to be searched is too large, it is
important to be able to represent a problem in as
economical away as possible.
Dr. Saleh Abu-Soud 14 Artificial Intelligence – Introduction to Searching
➧State descriptions
➪ An important part of any state-space problem
formulation is the selection of some particular form of
description for the problem.
➪ Virtually any kind of data structure can be used.
to describe states:
- Symbol strings - Vectors
- Two-dimensional arrays - Trees
- Lists - Graphs
- Linear string
Dr. Saleh Abu-Soud 15 Artificial Intelligence – Introduction to Searching
Example1: for the 8-Puzzle 3x3 matrix
Example2: (AB + CD) / BC Binary tree
/
non-terminal
node
+ x
terminal node
x x B C
A B C D
Example3: (AB + CD) / BC Linear string
/ + x AB x CD x BC
Dr. Saleh Abu-Soud 16 Artificial Intelligence – Introduction to Searching
➧Operators
➪ Operators change one state into another.
➪ They can be considered functions whose domain and
and range are sets of states.
➪ Operators are considered as computations that transform
state description into another state description.
➪ Production rules can be used as strings in problem-
solving methods.
Dr. Saleh Abu-Soud 17 Artificial Intelligence – Introduction to Searching
➧Goal states
➪ Sometimes it is necessary to find any path to a goal.
➪ Sometimes it is necessary to find some path optimizing
some criterion.
➪ Such problems are most easily handled by making sure
that search does not terminate until an optimal solution
is found.
Dr. Saleh Abu-Soud 18 Artificial Intelligence – Introduction to Searching
➪ State-space:
1- State description of the initial state.
2- Operators
3- the properties of a goal state description
● Graph notation:
ancestor of X
parent node of X
weighted (cost)
arc
directed
X successor node X
Dr. Saleh Abu-Soud 19 Artificial Intelligence – Introduction to Searching
➧Selecting “good” Representations
➪ The selection of a state-space representation for a
problem has a great influence on the search effort
needed to solve it.
➪ One prefers representations with small state process.
Dr. Saleh Abu-Soud 20 Artificial Intelligence – Introduction to Searching
