Search in
Artificial Intelligence
Search plays a major role in solving many Artificial Intelligence (AI) problems. Search is a universal
problem-solving mechanism in AI. In many problems, sequence of steps required
to solve is not known in advance but must be determined by systematic
trial-and-error exploration of alternatives.
The problems that are addressed by AI search algorithms fall
into three general classes:
single-agent path-finding problems, two-players games, and
constraint-satisfaction problems
Single-agent
path-finding problems
Classic examples in the AI literature of path-finding
problems are sliding-title puzzles, Rubik’s Cube and theorem proving. The
single-title puzzles are common test beds for research in AI search algorithms
as they are very simple to represent and manipulate. Real-world problems
include the traveling salesman problem, vehicle navigation, and the wiring of
VLSI circuits. In each case, the task is to find a sequence of operations that
map an initial state to a goal state.
Two-players games
Two-players games are two-player perfect information games.
Chess, checkers, and othello are some of the two-player games.
Constraint
Satisfaction Problems
Eight Queens problem is the best example. The task is to
place eight queens on an 8*8 chessboard such that no two queens are on the same
row, column or diagonal. Real-world examples of constraint satisfaction
problems are planning and scheduling applications.
Problem
Space
Problem space is a set of states and the connections between
to represent the problem. Problem space graph is used to represent a problem
space. In the graph, the states are represented by nodes of the graph, and the
operators by edges between nodes. Although most problem spaces correspond to
graphs with more than one path between a pair of nodes, for simplicity they are
often represented as trees, where the initial state is the root of the tree.
The cost of the simplification is that any state that can be reached by two
different paths will be represented by duplicate nodes thereby increasing the
tree size. The benefit of using tree is that the absence of cycles greatly
simplifies many search algorithms.
One feature that distinguishes AI search algorithms from
other graph-searching algorithms is the size of the graph involved. For
example, the entire chess graph is estimated to contain over 10^40 nodes. Even
a simple problem like twenty-four puzzle contains almost 10^25 nodes. As a
result, the problem-space graphs of AI problems are never represented
explicitly by listing each state, but rather are implicitly represented by
specifying an initial state and a set of operators to generate new states from
existing states. Moreover the size of an AIproblem is rarely expressed as the number of nodes in its problem-space graph.
The two parameters of a search tree that determine the efficiency of various
search algorithms are its branching factor and its solution depth. The
branching factor is nothing but average number of children of a given node. For
example in eight-puzzle problem, the average branching factor is square-root(3)
or about 1.732. The solution depth of a problem instance is the length of a
shortest path from the initial state to a goal state or the length of a
shortest sequence of operators that solve the problem.