Chapter Three

Problem solving
Department of Computer Science, Injibara University
2015 E.C

1
Outline
 Searching and constraint satisfaction problem

 Problem solving by searching

 Problem solving agents

 Search strategies, avoiding repeated states

 Constraint stratification search

 Game as a search problems

2
Problem solving
 Problem solving is a process of generating solutions from observed data.

a problem is characterized by a set of goals,

a set of objects, and

a set of operations.
Problem may have:
 A unique solution or Several solutions
Some solution are better than others (Optimal solution)
Sometimes too hard to find (Approximate solution)
Quality of solution improving with time (Anytime algorithms)

3
Searching
 Searching is the universal technique of problem solving in AI.

 Problem Space: It is the environment in which the search takes place (A set of states and set
of operators to change those states).

 Problem Instance: It is Initial state + Goal state

 Problem Space Graph: It represents problem state.

 States are shown by nodes and operators are shown by edges.

4
Cont.
 Depth of a problem: Length of a shortest path or shortest sequence of operators from Initial
state to goal state.

 Space Complexity: The maximum number of nodes that are stored in memory.

 Time Complexity: The maximum number of nodes that are created.

 Depth: Length of the shortest path from initial state to goal state.

5
Problem solving by searching
 Brute-force strategy- the most simple, it dose not need domain-specific knowledge.

 Brute-force works fine with small number of possible states. Requirements:

State description;

A set of valid operators;

Initial state;

Goal state description.

 For solving a problem it needs to be precisely defined. The definition consists,

defining the start state, goal state, other valid states and transitions.

6
Problem solving methods
 The following standard problem-solving methods are used in AI.

1) Heuristics: The heuristic method devises a solution based purely on experiments and trial and
error methods.

 However, heuristics do not often provide the best optimal solution to a specific problem.

 Instead, offers an efficient solutions to attain immediate goals.

Example: Travelling Salesman Problem

 The most common example of using heuristic is the Travelling Salesman problem. There is a
provided list of cities and their distances.

 The user has to find the optimal route for the Salesman to return to the starting city after visiting
every city on the list.

7
 Cont.
2) Searching Algorithms: Searching is one of the primary methods of solving a problem in
AI.

 Rational agents or problem-solving agents use searching algorithms to find optimal

solutions.

 The problem-solving agents are often goal-based and utilize atomic representation.

 Searching algorithms possess completeness, optimality, time complexity, and space

complexity properties based on the quality of the solution provided by them.

8
Graph search
 A large variety of problems can be represented by a graph.

 Solutions can be considered as defining specific nodes called goal.

 Solving the problem is reduced to searching the graph for goal nodes.

 Starting from an initial node,

 Each transition in the graph corresponds to a possible action,

 Ending when reaching a final node (solution).

9
Single-state graph search
 A problem is defined by:
1) An initial state,

2) A successor function S(X) = set of action-state pairs,

3) A set of specific nodes: the goals,

4) A path cost (additive).

 A solution: the sequence of actions leading from the initial state to a goal.

10
A classic problem
“A lion, a goat and a cabbage are present at one side of a river and need to cross the river.
There is only one boat available. At any point of time, the goat and the lion or the goat and
cabbage should not be at one side of the river bank. It is also known that only a person and a
goat, or cabbage or a lion can occupy the boat available at a time.”

 what would be the possible sequence of actions required to cross the river?

 The solution is the sequence of their transfer from one bank of river to other using the boat
sailing through the river satisfying the constraints.

11
Search strategies
 Uninformed search algorithms or Brute-force algorithms, search through the search
space.

 Uninformed search is used when there is no information about the cost of navigating
between states.

 Informed search algorithms uses heuristic functions that are specific to the problem.

12
Search strategy evaluation
 A search strategy is defined by the order of node expansion.

 Strategies are evaluated along the following dimensions:

 Completeness: does it always find a solution if one exists?
 Time complexity: number of nodes generated.
 Space complexity: maximum number of nodes in memory.
 Optimality: does it always find a least-cost solution?

 Time and space complexity are measured in terms of

 b: maximum branching factor of the search tree (always finite),
 d: depth of the least-cost solution,
 m: maximum depth of the state space (may be ∞).

13
Uninformed search
 Breadth-first search

 Depth-first search

 Depth-limited search

 Uniform cost search

14
Breadth-first search(BFS)
 The most common search strategy for traversing a tree or graph.

 This algorithm searches breadthwise in a tree or graph.

 The searching starts from the root node expanding successor node at the current level.

 The breadth-first search algorithm is an example of a general-graph search algorithm.

 Breadth-first search is implemented with FIFO (queue) data structure.

15
Cont.
 BFS algorithm:

1) The root node is expanded first.

2) All the nodes at a given depth are expanded before any nodes at the next level.

3) Expands shallowest unexpanded node.

4) Implementation: a FIFO queue, the nodes that are visited first will be expanded first.

5) All newly generated successors will be put at the end of the queue.

6) Shallow nodes are expanded before deeper nodes.

16
BFS example
 Consider the following search tree or graph:

BFS search the tree in the following order: ABCDEFG

17
Properties of BFS example
 Time complexity: 𝑂 𝑏 𝑑 ,

 Space complexity: 𝑂 𝑏 𝑑 ,

 Optimality: yes
 b=branching factor(maximum no of successors of any node),
 d – Depth of the shallowest goal node,

 It is complete, provided the branching factor b is finite.

 The shallowest goal node is not necessarily optimal.

 It is optimal when all step costs are equal.

18
Depth first search (DFS)
 It always expands the deepest node in the tree.

 After reaching the deepest level, it backs up the next deepest node that still has unexplored
successors.

 It can be implemented by TREE-SEARCH with a last-in-first-out (LIFO) stack.

 The DFS algorithm performs deep searching and may occasionally enter an infinite cycle.

19
Properties of DFS
 Completeness: Within a finite state space, the DFS search algorithm is complete.

 Space complexity: 𝑂 𝑏𝑚 ,

 Optimality: no

DFS: ABDECFG

20
Uniform path cost search
 Uninform-path cost search explores nodes based on their path cost.

 It expands a node n having the lowest path cost g(n), where g(n) is the total cost from a root
node to node n.

 Uniform-cost search is significantly different from the breadth-first search because of the
following two reasons:

 First, the goal test is applied to a node only when it is selected for expansion because the
first goal node which is generated may be on a suboptimal path.

 Secondly, a goal test is added to a node, only when a better/ optimal path is found.

21
Example
 Determine the order in which the tree is traversed using uniform-path cost for the following
search graph.

 In the above figure, the goal-state is F and initial or the root node is A.

 There are three paths available to reach the goal node. An optimal path which may give the
lowest total cost g(n) is selected. Thus, A->B->E->F is the optimal path cost
i.e., 0+1+3+4=8.

22
Depth limited search
 Depth limited search strategy is similar to DFS with a little difference.

 The difference is that in depth-limited search, the depth limit l to the depth of the search
tree is employed.

 It does not need to explore till infinity.

 As a result, the depth-limited search is a special case of depth-first search.

23
Depth limited search

 Completeness: Depth-limited search does not guarantee to reach the goal node.

 Optimality: It does not give an optimal solution as it expands the nodes till the depth-limit.

 Space Complexity: The space complexity of the depth-limited search is O(bl). Time

 Complexity: The time complexity of the depth-limited search is O(bl).

24
Constraint satisfaction problem (CSP)
 States and goal test conform to a standard, structured and simple representation

 CSP is defined by three components (X, D, C):

1) state: a set of variables X, each Xi , with values from domain Di

2) goal test: a set of constraints C, each Ci involves some subset of the variables and specifies the
allowable combinations of values for that subset

3) Each constraint Ci consists of a pair , where scope is a tuple of variables and the relation, either
represented explicitly or abstractly.

25
Map coloring

 Color each of the country on the map with different colors, where no the similar color is used to colored
adjacent country on the map.
 Variables: X = {WA, NT, Q, NSW, V, SA, T }
 Domains: Di = {red, green, blue}
 Constraints: adjacent regions must have different colors

26
Solution

 Variables: X = {WA, NT, Q, NSW, V, SA, T }

 Domains: Di = {red, green, blue}
 Constraints: adjacent regions must have different colors.
 Solution? {WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = red}.
 Real-world problem: Class time tabling.
27
Game as search problem (Reading assignment)
 State-space search assumes single agent searching in a fixed environment.

 Game search introduces one or more additional agents.

 Actions of all agents affect the environment.

 For our discussions, we will assume only two players.

 Search – no adversary – Solution is a path from start to goal, or a series of actions from
start to goal.

 Heuristics and search techniques can find optimal solution – Evaluation function: estimate
of cost from start to goal through given node – Actions have cost – Examples: path
planning, scheduling activities.
28
Game vs search problem
 “Unpredictable” opponent means solution is a “contingency plan.”

 Time limits restrict ability to search for goal prior to play need to approximate.

 Games – adversary

 Solution is strategy: strategy specifies move for every possible opponent reply.

 Time limits force an approximate solution.

 Evaluation function: evaluate “goodness” of game position

 Board configurations have utility.

 Examples: chess, checkers, Othello, backgammon

29
Types of games
 “Perfect information games

 Examples: chess, checkers, othello.

 Imperfect information games

 Ambiguity in state description.

 Non-determinism in actions

 Presence of chance player

 Examples: poker, backgammon

30
Review questions
1) What is searching?

2) Explain state space search?

3) Describe different types of search strategies.

4) How does search strategies defined?

5) What is the difference between heuristic and uninformed search?

6) What are the challenges of solving problems with brute-force strategy?

7) What are the performance measures used to evaluate the performance of different searching strategies?

8) Describe constraint stratification problems by giving real world examples.

9) Compare and contrast search strategies by using different performance measures.

31