Problem Solving by Intelligent Search

Problem solving requires two prime considerations: first representation of
the problem by an appropriately organized state space and then testing the
existence of a well-defined goal state in that space. Identification of the goal
state and determination of the optimal path, leading to the goal through one
or more transitions from a given starting state, will be addressed in this
chapter in sufficient details. we, thus, starts with some well-known
search algorithms, such as the depth first and the breadth first search, with
special emphasis on their results of time and space complexity. It then
gradually explores the ‘heuristic search’ algorithms, where the order of
visiting the states in a search space is supported by thumb rules, called
heuristics, and demonstrates their applications in complex problem solving.
It also discusses some intelligent search algorithms for game playing.
Depending on the methodology of expansion of the state space and
consequently the order of visiting the states, search problems are differently
named in AI. For example, consider the state space of a problem that takes the
form of a tree. Now, if we search the goal along each breadth of the tree,
starting from the root and continuing up to the largest depth, we call it
breadth first search. On the other hand, we may sometimes search the goal
along the largest depth of the tree, and move up only when further traversal
along the depth is not possible. We then attempt to find alternative offspring
of the parent of the node (state) last visited. If we visit the nodes of a tree
using the above principles to search the goal, the traversal made is called
depth first traversal and consequently the search strategy is called depth first
search. We will shortly explore the above schemes of traversal in a search
space. One important issue, however, needs mention at this stage. We may
note that the order of traversal and hence search by breadth first or depth first
manner is generally fixed by their algorithms. Thus once the search space,
here the tree, is given, we know the order of traversal in the tree. Such types
of traversal are generally called ‘deterministic’. On the other hand, there exists
an alternative type of search, where we cannot definitely say which node will
be traversed next without computing the details in the algorithm. Further, we
may have transition to one of many possible states with equal likelihood at an
instance of the execution of the search algorithm. Such a type of search, where
the order of traversal in the tree is not definite, is generally termed ‘nondeterministic’
1. Most of the search problems in AI are non-deterministic. We
will explore th