Topic 6:
Solving Problems by
Searching
Term 2-ARTI 106
Computer Track
2024-2025
Learning outcomes
The main learning objectives of this topic are:
❑Identify the Problem-solving agent.
❑Discuss goal and problem formulation
❑ Explain search algorithm.
❑ Create and explore Binary search tree.
❑Measure the problem-solving performance.
Outlines
❑Problem-solving agent
❑Goal and Problem formulation
❑Search algorithm
❑Binary Search tree
❑Measuring problem-solving performance
Problem-solving agent
❑In artificial intelligence, a problem-solving agent
refers to a type of intelligent agent designed to
address and solve complex problems or tasks in its
environment.
❑These agents are a fundamental concept in AI and
are used in various applications, from game-playing
algorithms to robotics and decision-making systems.
Problem-solving agent
❑ It’s a goal-based agent.
❑ Decides what to do by finding sequences of actions that
lead to desirable states.
❑ They are expected to adopt a goal and work to achieve it
to maximize the performance measure.
❑ Problem-solving agent solves problem by finding
sequences of actions that lead to desirable states (goals).
❑ The first step solve a problem is the goal formulation
based on the current situation.
Steps of problem-solving
Goal formulation
❑ It organize finite steps to formulate goals which require
some action to achieve the goal.
❑ The goal is formulated as a set of world states, in which
the goal is satisfied.
❑ Actions are operators causing transitions between world
states (from initial state → goal state)
❑ Actions should be abstract enough at a certain degree,
instead of very detailed (e.g., turn left VS turn left 30
degree, etc.…)
Problem formulation
❑ It is one of the core steps of problem-solving
which decides what action should be taken to
achieve the formulated goal.
❑ This steps consist of five components to
formulate the associated problem (1) initial state,
(2)action, (3) goal test, (4) transition, (5) path
costing.
Example: Romania
❑On holiday in Romania; currently in Arad.
❑Formulate goal: to be in Bucharest
❑Formulate problem:
❖ states: various cities
❖ action: drive between cities
❑Find solution: sequence of cities: e.g., Arad, Sibiu, Fagaras,
Bucharest
Example: Romania
Problem formulation
A problem is defined by five components:
❑ Initial state: The starting city where the car is located, e.g., “at Arad”
❑ Actions: are the roads or routes you can take to travel to in between cities. (s) -> {a1,
a2, a3, … }
e.g., {Go(Sibiu), Go(Timisoara), Go(Zerind)}
❑ Transition: describes how the current state changes after taking an action.
Result (s,a) -> s’
e.g., Result(In(Arad), Go(Timisoara)) = In(Timisoara)
❑ Goal test: Checks if you have reached the destination city
(s) ->T/F e.g., “is the current state is Bucharest?”
❑ Path cost: The total cost of the journey, such as the distance traveled, time taken, or
fuel consumed.
(s -> s -> s) -> n (additive) : sum of cost of individual steps, e.g., number of miles
traveled, number of minutes to get to destination.
Search algorithm (1)
❑There are many ways to achieve the same goal. When all
ways (paths) joined together , they are considered as a tree.
❑An agent can examine different possible sequences of
actions and choose the best.
❑This process of looking for the best sequence is called
search.
❑The best sequence is then a list of actions, called solution.
Search algorithm (2)
❑ After goal formulation and problem formulation, the agent has to
look for a sequence of actions that reaches the goal. This process is
called Search.
❑ A search algorithm takes a problem as input and returns a sequence
of actions as output.
❑ After the search phase, the agent has to carry out the actions that
are recommended by the search algorithm.
❑ This final phase is called execution phase.
❑ Thus, the agent follows a design that involves:
“Formulate-search-execute”
Formulate, search, execute
❑ The complete process of an agent to solve the problems can be
expressed as “formulate, search, execute”.
❑ A simple problem-solving agent :
1. formulate a goal and a problem
2. search for a sequence of actions to solve the problem
3. Execute the actions one at a time
❑ When those steps are completed, start formulate another goal and
continue the process.
Problem-Solving agent
algorithm
Search Tree: terminology
❑ In a Search tree:
❖ Initial state is the root,
❖ Branches are actions
❖ Nodes are states.
❑ Parent node: the node that is the predecessor of any node.
❑ Child nodes: a descendant of any node.
❑ Leaf node: a node with no children.
❑ Search strategy: how to choose which state to expand next.
❑ A repeated state: when same state is encountered multiple times
during the search process.
Binary Search Trees
❑Binary tree is a tree in which no node can have more than two
children.
Binary Search Trees
❑ Stores keys in the nodes in a way so that searching, insertion and
deletion can be done efficiently.
❑ Property of Binary search tree: For every node X, all the keys in its
left subtree are smaller than the key value in X, and all the keys in
its right subtree are larger than or equal the key value in X.
❑ This rule will be recursively applied to all the left and right sub-trees
of the root.
Binary Search Trees
A binary search tree Not a binary search tree
Is this tree a BST?
Exercise…
Create the binary search tree using the following data
elements:43, 10, 79, 12, 90, 11, 54, 9, 50 .
Let’s consider that 43 is the root of the tree
Solution:
Searching Binary Tree
Suppose T is the tree being searched:
❑If we are searching for 15,then we are
done.
❑If we are searching for a key <15, then
we should search in the left subtree
❑If we are searching for a key >15, then
we should search in the right subtree
Example: Search for 9…
Measuring problem-solving
performance
Measure the performance of a search strategy by:
❑ Completeness:
is the strategy guaranteed to find a solution when there is
one?
❑ Optimality:
does the strategy find the highest-quality solution when
there are several different solutions?
❑ Time complexity:
how long does it take to find a solution?
❑ Space complexity:
how much memory is needed to perform the search?
Measuring problem-solving
performance
❑ For effectiveness of a search algorithm, we can just
consider the total cost.
❖ The total cost = path cost (g) of the solution
found + search cost.
o search cost = time necessary to find the solution
❑ Tradeoff:
❖ Long time, optimal solution with least g.
vs.
❖ shorter time, solution with slightly larger path cost g.
Thank you for you attention
