MODULE 1 - INTRODUCTION

Prof Ganga D Benal

Department of
Computer Science & Engineering

www.cambridge.edu.in
What is AI?

• Homo sapiens—man the wise—because our intelligence is so important to us.

• For thousands of years, we have tried to understand how we think; that is, how a
mere handful of matter can perceive, understand, predict, and manipulate a world
far larger and more complicated than itself.
• The field of artificial intelligence, or AI, goes further still: it attempts not just to
understand but also to build intelligent entities.
• AI is one of the newest fields in science and engineering.
• Work started in earnest soon after World War II.
• The name itself was coined in 1956.

2 Jul 2024 2
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

2 Jul 2024 4
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

2 Jul 2024 5
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

2 Jul 2024 6
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

2 Jul 2024 7
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

2 Jul 2024 8
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

Concerned
with thought
processes and
reasoning

2 Jul 2024 9
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

Concerned
with thought
processes and
reasoning

2 Jul 2024 10
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

Concerned
with thought
processes and
reasoning

2 Jul 2024 11
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?
I

Concerned
with thought
processes and
reasoning

2 Jul 2024 12
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

Concerned
with thought
processes and
reasoning

2 Jul 2024 13
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

Concerned
with thought
processes and
reasoning

2 Jul 2024 14
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

Concerned
with thought
processes and
reasoning

2 Jul 2024 15
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?

Concerned
with thought
processes and
reasoning

Address
behavior

2 Jul 2024 16
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?
Measure success in terms of
fidelity to human performance

Concerned
with thought
processes and
reasoning

Address
behavior

2 Jul 2024 17
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?
Measure success in terms of Measure success against
fidelity to human performance rationality

Concerned
with thought
processes and
reasoning

Address
behavior

2 Jul 2024 18
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?
Measure success in terms of Measure success against
fidelity to human performance rationality

Concerned
with thought
processes and
reasoning

A system is rational if it
Address
does the “right thing,”
behavior
given what it knows.

2 Jul 2024 19
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
What is AI?
Measure success in terms of Measure success against
fidelity to human performance rationality

Some definitions
Concerned
of artificial
with thought
processes and intelligence,
reasoning organized into
four categories

A system is rational if it
Address
does the “right thing,”
behavior
given what it knows.

2 Jul 2024 20
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Acting humanly: The Turing Test Approach

• Proposed by Alan Turing - TURING TEST (1950),

• Designed to provide a satisfactory operational definition of intelligence.
• A computer passes the test if a human interrogator, after posing some written
questions, cannot tell whether the written responses come from a person or from a
computer.

2 Jul 2024 21
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Acting humanly: The Turing Test Approach

The computer would need to possess the following capabilities:

• natural language processing to enable it to communicate successfully in English;
• knowledge representation to store what it knows or hears;
• automated reasoning to use the stored information to answer questions and to
draw new conclusions;
• machine learning to adapt to new circumstances and to detect and extrapolate
patterns.

2 Jul 2024 23
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Acting humanly: Total Turing Test

• Turing’s test deliberately avoided direct physical interaction between the

interrogator and the computer, because physical simulation of a person is
unnecessary for intelligence.
• However, the total Turing Test includes a video signal so that the interrogator can
test the subject’s perceptual abilities, as well as the opportunity for the interrogator
to pass physical objects “through the hatch.”
• To pass the total Turing Test, the computer will need
- computer vision to perceive objects, and
- robotics to manipulate objects and move about.

2 Jul 2024 24
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Thinking humanly: The Cognitive Modeling Approach

The actual workings of human minds:

• through introspection—trying to catch our own thoughts as they go by;
• through psychological experiments—observing a person in action; and
• Through brain imaging—observing the brain in action.

2 Jul 2024 25
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Thinking humanly: The Cognitive Modeling Approach

• If the program’s input–output behavior matches corresponding human behavior,

that is evidence that some of the program’s mechanisms could also be operating in
humans.
• For example, Allen Newell and Herbert Simon, who developed GPS, the “General
Problem Solver” (Newell and Simon, 1961), were not content merely to have their
program solve problems correctly. They were more concerned with comparing the
trace of its reasoning steps to traces of human subjects solving the same problems.
• Cognitive science - The interdisciplinary field that brings together computer models
from AI and experimental techniques from psychology to construct precise and
testable theories of the human mind.

26
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Thinking rationally: The “Laws of Thought” Approach

• The Greek philosopher Aristotle was one of the first to attempt to codify “right
thinking,” that is, irrefutable reasoning processes.
• His syllogisms provided patterns for argument structures that always yielded correct
conclusions when given correct premises.
• For example, “Socrates is a man;
all men are mortal;
therefore, Socrates is mortal.”
• These laws of thought were supposed to govern the operation of the mind; their
study initiated the field called logic.

27
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Thinking rationally: Logistic

• By 1965, programs existed that could, in principle, solve any solvable problem
described in logical notation. (If no solution exists, the program might loop forever.)
• The so-called logicist tradition within artificial intelligence hopes to build on such
programs to create intelligent systems.

2 Jul 2024 28
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Thinking rationally: The “Laws of Thought” Approach

• Two main obstacles to this approach:

i. It is not easy to take informal knowledge and state it in the formal terms required
by logical notation, particularly when the knowledge is less than 100% certain.
ii. There is a big difference between solving a problem “in principle” and solving it in
practice.
• Even problems with just a few hundred facts can exhaust the computational
resources of any computer unless it has some guidance as to which reasoning steps
to try first.
• Although both of these obstacles apply to any attempt to build computational
reasoning systems, they appeared first in the logicist tradition.
2 Jul 2024 29
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Acting rationally: The rational agent Approach

• An agent is just something that acts.

• agent comes from the Latin agere, to do.
• All computer programs do something, but computer agents are expected to do
more:
operate autonomously, perceive their environment, persist over a prolonged time
period, adapt to change, and create and pursue goals.
• A rational agent is one that acts so as to achieve the best outcome or, when there is
uncertainty, the best expected outcome.

2 Jul 2024 30
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Acting rationally: The rational agent Approach

• The rational-agent approach has two advantages over the other approaches.
1. It is more general than the “laws of thought” approach because correct
inference is just one of several possible mechanisms for achieving rationality.
2. It is more amenable to scientific development than are approaches based on
human behavior or human thought.

2 Jul 2024 31
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
The Foundations of Artificial Intelligence

• Philosophy • Psychology
• Mathematics • Computer engineering
• Economics • Control theory and cybernetics
• Neuroscience • Linguistics
2 Jul 2024 32
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
The Foundations of Artificial Intelligence - Philosophy

• Rationalism - the philosophy of the power of reasoning in understanding.

- Descartes, Aristotle and Leibnitz.
• Dualism - there is a part of the human mind (or soul or spirit) that is outside of nature,
exempt from physical laws.
- Animals, on the other hand, did not possess this dual quality; they could be treated as
machines.
- Descartes was also a proponent of dualism.
• Materialism - An alternative to dualism is materialism.
- It holds that the brain’s operation according to the laws of physics constitutes the mind.
- Free will is simply the way that the perception of available choices appears to the choosing
entity.
2 Jul 2024 33
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
• Can formal rules be used to draw valid conclusions?
• How does the mind arise from a physical brain?
• Where does knowledge come from?
• How does knowledge lead to action?
2 Jul 2024 34
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Mathematics
• What are the formal rules to draw valid conclusions?
• What can be computed?
• How do we reason with uncertain information?

2 Jul 2024 36
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
The Foundations of Artificial Intelligence - Neuroscience

Parts of a nerve cell or neuron.

2 Jul 2024 39
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
History of AI
History of AI
• Gestation of AI (1943 - 1955)
Warren McCulloch and Walter Pitts.
They drew on three sources:
- knowledge of the basic physiology and function of neurons in the
brain;
- a formal analysis of propositional logic
- Turing’s theory of computation.
• In 1943, proposed a binary-based model of neurons
• Any computable function can be modeled by a set of neurons
• A serious attempt to model brain
• 1950, Turing’s “Computing Machinery and Intelligence ”: turing test,
The birth of artificial intelligence (1956):
• Dartmouth meeting to study AI
• an AI program ”Logic Theorist” to prove many theorems

Early Enthusiasm and great Expectation (1952-1969)

• General Problem Solver imitates the human way of thinking
• LISP (AI programming language) was defined
• 1965, Robinson discovered the resolution method – logical
reasoning
• A dose of reality (1966–1973)
• Computational intractability of many AI problems
• The intractability of many of the problems that AI was
attempting to solve.
• Neural Network starts to disappear
Knowledge-based systems (1969-1979)
Use domain knowledge to allow for stronger reasoning

Becomes an Industry (1980-now)

Digital Equipment Corporation selling R1 “expert system”
From few million to billions in 8 years
 Thereturn of neural network (1986-now)
 With the back-propagation algorithm

 AIadopts scientific method (1987-now)

 More common to base theorems on pervious ones or
rigorous evidence rather than intuition
 Speech recognition and HMM
Emergence of intelligent agent (1995-now)
search engines, recommender systems,….

Availability of very large data sets (2001 – now)

Worry more about the data
Problem Solving Agent.

Problem Solving Agent. An agent that tries to come up

with a sequence of actions that will bring the environment
into a desired state. Search. The process of looking for such
a sequence, involving a systematic exploration of
alternative actions.
• Problem-solving agent
• A kind of goal-based agent
• It solves problem by
• finding sequences of actions that lead to desirable
states (goals)
• To solve a problem,
• the first step is the goal formulation and it is based
on the current situation and the agent’s
performance Measure.
• first step in the problem solving
 The goal is formulated
 as a set of world states, in which the goal is satisfied
 Reaching from initial state  goal state
 Actions are required
 Actions are the operators
 causing transitions between world states
 Actions should be abstract enough at a certain degree,
instead of very detailed
Problem formulation
It is the process of deciding what actions and states to
consider, given a goal.

in-between states and actions defined

States: Some places( reach from A –B)
Actions: Turn left, Turn right, go straight, accelerate &
brake, etc.
Search
 Because there are many ways to achieve the same
goal
 Those ways are together expressed as a tree
 Multiple options of unknown value at a point,
 the 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
Together, the initial state, actions, and transition model
implicitly define the state space of the problem—the set of
all states reachable from the initial state by any sequence of
action
The state space forms a directed network or graph in which
the nodes are states and the links between nodes are
actions.

A path in the state space is a sequence of states

connected by a sequence of actions.
The goal test, which determines whether a given state
is a goal state. Sometimes there is an explicit set of
possible goal states, and the test simply checks
whether the given state is one of them. The agent’s
goal in Romania is the singleton set {In(Bucharest)}.
• A path cost function that assigns a numeric cost to each path.
The step cost of taking action a in state s to reach state s is
denoted by c(s, a, s )

. A solution to a problem is an action sequence that leads from

the initial state to a goal state.

Solution quality is measured by the path cost function, and an

optimal solution has the lowest path cost among all solutions.
3.1.2 Formulating problems The process of defining the specific problem
being addressed
Compare the simple state description we have chosen, In(Arad), to an
actual cross country trip, where the state of the world includes so
many things: the traveling companions, the current radio program,
the scenery out of the window, the proximity of law enforcement
officers, the distance to the next rest stop, the condition of the road,
the weather, and so on. All these considerations are left out of our
state descriptions because they are irrelevant to the problem of
finding a route to Bucharest.
The process of removing detail from a representation is
called abstraction.
Problem-solving Agents

• We assume that
- the environment is observable, so the agent always knows the current state.
- the environment is discrete, so at any given state there are only finitely many
actions to choose from.
- the environment is known, so the agent knows which states are reached by
each action.
- the environment is deterministic, so each action has exactly one outcome.
• Under these assumptions, the solution to any problem is a fixed sequence of
actions. 73
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Problem-solving Agents

function SIMPLE-PROBLEM-SOLVING-AGENT(percept ) returns an action

persistent: seq, an action sequence, initially empty
state, some description of the current world state
goal , a goal, initially null
problem, a problem formulation
state ← UPDATE-STATE(state, percept )
if seq is empty then
goal ← FORMULATE-GOAL(state)
problem ← FORMULATE-PROBLEM(state, goal )
seq ← SEARCH(problem)
if seq = failure then return a null action
action ← FIRST(seq)
seq ← REST(seq)
return action
2 Jul 2024 74
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Example: Vaccum world
Example : 8 PUZZLE Problem

???

The 8-puzzle belongs to the family of sliding-

block puzzles
• States: A state description specifies the location of each of the eight
tiles and the blankin one of the nine squares.
• Initial state: Any state can be designated as the initial state. Note
that any given goal can be reached from exactly half of the possible
initial states
• Actions: The simplest formulation defines the actions as movements
of the blank space Left, Right, Up, or Down. Different subsets of
these are possible depending on where the blank is.
Transition model: Given a state and action, this returns the
resulting state; for example, if we apply Left to the start state ,
the resulting state has the 5 and the blank switched.
• Goal test: This checks whether the state matches the goal
configuration (Other goal configurations are possible.)
• Path cost: Each step costs 1, so the path cost is the number of
steps in the path.
8-Queens Problem

82
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
8-Queens Problem

Incremental formulation:
• States: Any arrangement of 0 to 8 queens on the board is a state.
• Initial state: No queens on the board.
• Actions: Add a queen to any empty square.
• Transition model: Returns the board with a queen added to the specified square.
• Goal test: 8 queens are on the board, none attacked.
In this formulation, we have 64 ・ 63 ・ ・ ・ 57 ≈ 1.8×1014 possible sequences to
investigate.

83
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
8-Queens Problem
Incremental formulation prohibiting placing a queen in any square that is already
attacked:
• States: All possible arrangements of n queens (0 ≤ n ≤ 8), one per column in the
leftmost n columns, with no queen attacking another.
• Initial state: No queens on the board.
• Actions: Add a queen to any square in the leftmost empty column such that it is not
attacked by any other queen.
• Transition model: Returns the board with a queen added to the specified square.
• Goal test: 8 queens are on the board, none attacked.
This formulation reduces the 8-queens state space from 1.8×1014 to just 2,057, and
solutions are easy to find.
2 Jul 2024 84
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
8-QUEENS PROBLEM

The goal of the 8-queens problem is to place eight

queens on a chessboard such that no queen attacks any
other. (A queen attacks any piece in the same row,
column or diagonal.)
The 8-queens
• There are two ways to formulate the problem
• All of them have the common followings:
• Goal test: 8 queens on board, not attacking to
each other
• Path cost: zero
The 8-queens

• (1) Incremental formulation

• involves operators that augment the state description
starting from an empty state
• Each action adds a queen to the state
• States:
• any arrangement of 0 to 8 queens on board
• Successor function:
• add a queen to any empty square
The 8-queens

• (2) Complete-state formulation

• starts with all 8 queens on the board
• move the queens individually around
• States:
• any arrangement of 8 queens, one per column
in the leftmost columns
• Operators: move an attacked queen to a row,
not attacked by any other
Real-world problems
 route-finding problem
Route-finding algorithms are used in a variety
of applications. Some, such as Web sites and in-car systems
that provide driving directions, are relatively straightforward
extensions of the Romania example.
 Consider the airline travel problems that must be solved by
a travel-planning Web site
States: Each state obviously includes a location (e.g., an airport) and the current
time. Furthermore, because the cost of an action (a flight segment) may depend
on previous segments, their fare bases, and their status as domestic or
international, the state must record extra information about these “historical”
aspects.
• Initial state: This is specified by the user’s query.
• Actions: Take any flight from the current location, in any seat class, leaving after
the current time, leaving enough time for within-airport transfer if needed.
• Transition model: The state resulting from taking a flight will
have the flight’s destination as the current location and the
flight’s arrival time as the current time.
• Goal test: Are we at the final destination specified by the user?
• Path cost: This depends on monetary cost, waiting time, flight
time, customs and immigration procedures, seat quality, time of
day, type of airplane, frequent-flyer mileage awards, and so on
• The traveling salesperson problem (TSP) is a touring problem in
which each city must be visited exactly once. The aim is to find the
shortest tour.

• A VLSI layout problem requires positioning millions of components

and connections on a chip to minimize area, minimize circuit delays,
minimize stray capacitances, and maximize manufacturing yield.
The layout problem comes after the logical design phase and is
usually split into two parts: cell layout and channel routing.
• Robot navigation is a generalization of the route-finding problem
Robot navigation is a generalization of the route-finding problem
When the robot has arms and legs or wheels that must also be
controlled, the search space becomes many-dimensional.

• In assembly problems, the aim is to find an order in which to

assemble the parts of some object. If the wrong order is chosen,
there will be no way to add some part later in the sequence
without undoing some of the work already done
Searching for solutions
• Together a problem is defined by
- Initial state
- Actions
- Transition model
- Goal test
- Path cost
• The solution of a problem is then
a path from the initial state to a state satisfying the goal test.
• Optimal solution
the solution with lowest path cost among all solutions.
2 Jul 2024 98
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Searching for solutions
• Search tree – the possible action sequences starting at the initial state form a search
tree with the initial state at the root; the branches are actions and the nodes
correspond to states in the state space of the problem.
• The first step is to test whether this is a goal state. (Clearly it is not, but it is important
to check so that we can solve trick problems like “starting in Arad, get to Arad.”)
• Expanding the current state - applying each legal action to the current state, thereby
generating a new set of states.
• Add branches from the parent node to new child nodes.
• AIM of search , This is the essence of search—following up one option now and
putting the others aside for later, in case the first choice does not lead to a solution

2 Jul 2024 99
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
A simplified road map of Romania

101
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Search trees

a) The initial state

b) After expanding Arad

2 Jul 2024 102
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Search trees

c) After expanding Sibiu

Partial search trees for finding a route from Arad to Bucharest.
Nodes that have been expanded are shaded; nodes that have been generated but not yet
expanded are outlined in bold; nodes that have not yet been generated are shown in faint
dashed lines.
2 Jul 2024 103
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Search Tree
• Leaf node - a node with no children in the tree.

• Frontier or open list - the set of all leaf nodes available for expansion at any given
point.
• The process of expanding nodes on the frontier continues until either a solution is
found or there are no more states to expand.
2 Jul 2024 104
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Search Tree

• Repeated state.
• Loopy path.
• Redundant paths.

2 Jul 2024 105

Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
The general Tree-Search Algorithm

function TREE-SEARCH(problem) returns a solution, or failure

initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution
expand the chosen node, adding the resulting nodes to the frontier

2 Jul 2024 106

Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
The general Graph-Search Algorithm
function GRAPH-SEARCH(problem) returns a solution, or failure
initialize the frontier using the initial state of problem
initialize the explored set to be empty
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution
add the node to the explored set
expand the chosen node, adding the resulting nodes to the frontier
only if not in the frontier or explored set
2 Jul 2024 107
Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
A simplified road map of Romania

2 Jul 2024 108

Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
Infrastructure for search algorithms
Search algorithms require a data structure to keep track of the
search tree that is being constructed. For each node n of the tree,
we have a structure that contains four components:
• n.STATE: the state in the state space to which the node
corresponds;
• n.PARENT: the node in the search tree that generated this node;
• n.ACTION: the action that was applied to the parent to generate
the node;
• n.PATH-COST: the cost, traditionally denoted by g(n), of the path
from the initial state
to the node, as indicated by the parent pointers
The function CHILD-NODE takes a parent node and an action
and returns the resulting child node:
A node is a bookkeeping data structure used to represent
the search tree. ( complete configuration parent , action
and path cost g(n)- stored in a data structure called node)

A state corresponds to a configuration of the world.

The frontier needs to be stored in such a way that
the search algorithm can easily choose the next node
to expand according to its preferred strategy.
The appropriate data structure for this is a queue.
Queues are characterized by the order in which they
store the inserted nodes.
Three common
 FIFO QUEUE variants are the first-in, first-out or FIFO
queue, which pops the oldest element of the queue;
 LIFO QUEUE the last-in, first-out or LIFO queue (also
known as a stack), which pops the newest element
 PRIORITY QUEUE of the queue; and the priority
queue, which pops the element of the queue with the
highest priority according to some ordering function
Measuring problem-solving performance
evaluate an algorithm’s performance infour ways:
 COMPLETENESS : Is the algorithm guaranteed to find a solution
when there is one?
 OPTIMALITY : Does the strategy find the optimal solution,
 TIME COMPLEXITY : How long does it take to find a solution?
 SPACE COMPLEXITY : How much memory is needed to perform the
search?
the typical measure is the size of the state space
graph, |V | + |E|,
where V is the set of vertices (nodes) of the graph and
E is the set of edges (links)
complexity is expressed in terms of three quantities:
b, the BRANCHING FACTOR or maximum number of
successors of any node;
d, the depth of the shallowest goal (i.e., the number of
steps along the path from the root); and
m, the maximum length of any path in the state space.
 Time is often measured in terms of the number of nodes generated
during the search, and
 space in terms of the maximum number of nodes stored in memory.
 To assess the effectiveness of a search algorithm, we can consider
search cost— which typically depends on the time complexity but
can also include a term for memory
 Total Cost usage—or we can use the total cost, which combines the
search cost and the path cost of the solution found.
A simplified road map of Romania

2 Jul 2024 123

Dr. Josephine Prem Kumar, Prof.-CSE www.cambridge.edu.i
function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
node ←a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
frontier ← a FIFO queue with node as the only element
explored ← an empty set
loop do
if EMPTY?(frontier ) then return failure
node ← POP(frontier ) /* chooses the shallowest node in frontier */
add node.STATE to explored
for each action in problem.ACTIONS(node.STATE) do
child ← CHILD-NODE(problem, node, action)
if child.STATE is not in explored or frontier then
if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)
frontier ← INSERT(child,frontier )
Depth-first search always expands the deepest node
in the current frontier of the search tree
The depth-first search algorithm is an instance of the graph-
search algorithm , whereas breadth-first-search uses a FIFO
queue, depth-first search uses a LIFO queue. A LIFO queue
means that the most recently generated node is chosen for
expansion.
As an alternative to the GRAPH-SEARCH-style implementation, it is common
to implement depth-first search with a recursive function that calls itself on
each of its children in turn.
The time complexity of depth-first graph search is
bounded by the size of the state space (which may be
infinite, of course). A depth-first tree search, on the other
hand, may generate all of the O(bm) nodes in the search
tree, where m is the maximum depth of any node; this
can be much greater than the size of the state space
depth-first search seems to have no clear advantage over
breadth-first search

A variant of depth-first search called backtracking search uses

still less memory