ARTIFICIAL INTELLIGENCE
PROBLEM SOLVING AND
SEARCH
DR. A DNA N SHA HZA D A
WHAT IS PROBLEM?
Artificial Intelligence - UMT Search [1]
WHAT IS PROBLEM
§ The disparity (perceived gap) between the existing
state and the desired state.
§ A problem is an obstacle which hinders the achievement
of a particular goal, objective or purpose.
§ A problem may have multiple solutions.
Artificial Intelligence - UMT Search [2]
SEARCH PROBLEMS
§ Many problems can be solved by searching for a good
solution in a search space
§ Where reasoning consists of exploring alternatives.
§ Declarative knowledge creates alternatives
• Which pieces of knowledge to use?
• How to use them?
§ Search is a about exploring alternatives.
• It is a major approach to exploit knowledge
§ Examples of such problems are:
• 8 puzzle problem
• Maze
• TSP
Artificial Intelligence - UMT Search [3]
EXAMPLE: TIC TAC TOE
Artificial Intelligence - UMT Search [4]
PROBLEM SOLVING
§ We model the real problem
• We magnify the parts of the problem that are important
for the solution and neglect the ones that are not
• We have to count and measure the important parts
• We need to identify the possible “operators” that can
be used to change reality
§ We solve the modelled problem
• Chose a framework that can solve the problem
• Set the model in the framework
• The framework solves the problem
• Validate the solution choice to show how good is the
method
§ With the help of the solution found in the model, we
solve the real problem
Artificial Intelligence - UMT Search [5]
PROBLEM MODELING/FORMULATION
§ A problem is defined by following items:
• A search Space
• Initial state
• Actions Or Successor function
• Goal test, can be
• explicit, e.g., x = "at Lahore"
• implicit, e.g., Checkmate(x)
• Path cost (additive)
• e.g., sum of distances, number of actions
executed, etc.
• A solution, a sequence of actions
leading from the initial state to a goal
state
Artificial Intelligence - UMT Search [6]
REPRESENTING A SEARCH SPACE
§ A convenient way of representing search spaces is as
a graph
§ A graph consists of nodes and links
• nodes represent states in a problem solving process
• links represent transitions or relationships
between nodes
§ A special case of a graph is a rooted tree
• A rooted tree has
• a unique node (the root) from which it is possible
to reach all other nodes in the graph
• at most one link between any two nodes
• no cycles
§ Trees are common in search problems
Artificial Intelligence - UMT Search [7]
REPRESENTING A PROBLEM WITH A GRAPH
§ A start state (where we are at the start, for
example the starting position of a game of chess)
§ Intermediary states (where we are now, for
example the current position of the board of
chess)
§ One or more goal states where the search for a
solution terminates (for example a check-mate
position in chess)
Artificial Intelligence - UMT Search [8]
EXAMPLE: 8 PUZZLE
§ State: Any arrangement of 8 numbered tiles and an
empty tile on a 3x3 board
Artificial Intelligence - UMT Search [9]
8 PUZZLE – PARTIAL STATE SPACE
Artificial Intelligence - UMT Search [10]
WATER JUG PROBLEM
§ We have 3 jugs of capacities 3, 5, and 8 liters,
respectively.
§ There is no scale on the jugs, so it's only their
capacities that we certainly know.
§ Initially, the 8-litre jug is full of water, the other
two are empty:
§ We can pour water from one jug to another, and the goal
is to have exactly 4 liters of water in any of the jugs.
Artificial Intelligence - UMT Search [11]
WATER JUG PROBLEM
Initial State
Possible Goal States
Artificial Intelligence - UMT Search [12]
WATER JUG PROBLEM
Artificial Intelligence - UMT Search [13]
MAN, WOLF, GOAT AND CABBAGE PROBLEM
§ A Farmer needs to bring a wolf, a goat, and a cabbage
across the river.
§ The boat is tiny and can only carry one passenger/load
at a time.
• If he leaves the wolf and the goat alone together, the
wolf will eat the goat.
• If he leaves the goat and the cabbage alone together,
the goat will eat the cabbage.
§ How can he bring all three safely across the river?
Artificial Intelligence - UMT Search [14]
MAN, WOLF, GOAT AND CABBAGE PROBLEM
Artificial Intelligence - UMT Search [15]
MAN, WOLF, GOAT AND CABBAGE PROBLEM
Artificial Intelligence - UMT Search [16]
SOLUTION TO THE SEARCH PROBLEM
§ A solution is a path connecting the initial node
to a goal node (any one)
Artificial Intelligence - UMT Search [17]
SOLUTION TO THE SEARCH PROBLEM
§ A solution is a path connecting the initial node
to a goal node (any one)
§ The cost of a path is the sum of the arc costs
along this path
§ An optimal solution is a solution path of minimum
cost
• There might be no solution !
Artificial Intelligence - UMT Search [18]
SOLUTION TO THE SEARCH PROBLEM
§ Often it is not feasible (or too expensive) to
build a complete representation of the state graph
§ A problem solver must construct a solution by
exploring a small portion of the graph
Artificial Intelligence - UMT Search [19]
SEARCH STRATEGIES
§ Uninformed (exhaustive/blind) search
§ Informed (heuristic-based) search
Artificial Intelligence - UMT Search [20]
EXHAUSTIVE SEARCH
§ A search is said to be exhaustive if the search is
guaranteed to generate all reachable states
(outcomes) before it terminates with failure.
§ Depth-first search (DFS)
§ Breadth-first search(BFS)
Artificial Intelligence - UMT Search [21]
DEPTH FIRST SEARCH
§ A search strategy that extends the current path as
far as possible before backtracking to the last
choice point and trying the next alternative path
§ Does not guarantee the optimal
§ In this strategy, search reaches a satisfactory
solution more rapidly than breadth first
• an advantage when the search space is large
Artificial Intelligence - UMT Search [22]
DEPTH FIRST SEARCH
§ Algorithm - Depth-first search
§ Put the root node on a stack;
while (stack is not empty)
{ remove a node from the stack;
if (node is a goal node) return success;
put all children of node onto the stack;}
return failure;
Artificial Intelligence - UMT Search [23]
DEPTH FIRST SEARCH
In case of graph:
Maintain the visited node
information as well !!
Artificial Intelligence - UMT Search [24]
DEPTH FIRST SEARCH
§ DFS systematically proceeds towards depth before
another path is considered.
§ If the maximum depth of search tree is reached and
if the solution has not been found, then the
search backtracks to the previous level and
explores any remaining alternatives at this
level, and so on.
§ It is this systematic backtracking procedure that
guarantees that it will systematically and
exhaustively examine all of the possibilities.
Artificial Intelligence - UMT Search [25]
BREADTH FIRST SEARCH
§ A Search strategy, in which the highest layer of a
decision tree is searched completely before
proceeding to the next layer
§ In this strategy, no viable solution is omitted
and therefore guarantee that optimal solution is
found.
§ This strategy is often not feasible when the
search space is large
Artificial Intelligence - UMT Search [26]
BREADTH FIRST SEARCH
§ Algorithm - Breadth-first search
§ Put the root node on a queue;
while (queue is not empty)
{ remove a node from the queue;
if (node is a goal node) return success;
put all children of node onto the queue;}
return failure;
Artificial Intelligence - UMT Search [27]
BREADTH FIRST SEARCH
Artificial Intelligence - UMT Search [28]
BREADTH FIRST SEARCH
§ The search generates all nodes at a particular level before
proceeding to the next level of the tree.
§ The search systematically proceeds testing each node that is
reachable from a parent node before it expands to any child of
those nodes.
§ The control regime guarantees that the space of possible moves is
systematically examined; this search requires considerable memory
resources.
§ The space that is searched is quite large and the solution may
lie a thousand steps away from the start node. It does, however,
guarantee that if we find a solution it will be the shortest
possible.
§ Search terminates when a solution is found and the test returns
true.
Artificial Intelligence - UMT Search [29]
ITERATIVE DEEPENING
Artificial Intelligence - UMT Search [30]
