ARTIFICIAL INTELLIGENCE

(6CS4-05)

UNIT-1
Introduction To AI &
Intelligent Agent

- Er. Shweta Saraswat

 Artificial Intelligence
• Artificial Intelligence is the study of building
agents that act rationally. Most of the time,
these agents perform some kind of search
algorithm in the background in order to
achieve their tasks.
 Problem solving
• In Computer science problem solving refers to
AI techniques by using various searching
algorithms, evolutionary computation,
knowledge representation etc.
 Problem solving using searching
consists of following steps:

Q Write down the steps to solve a problem?

• Define the problem
• Analyze the problem
• Identification of possible solutions
• Choosing the optimal solution
• implementation
 Properties of search algorithms
• Completeness
A search algorithm is said to be complete when it gives a solution or returns any
solution for a given random input.

• Optimality
If a solution found is best (lowest path cost) among all the solutions identified, then
that solution is said to be an optimal one.

• Time complexity
The time taken by an algorithm to complete its task is called time complexity. If the
algorithm completes a task in a lesser amount of time, then it is an efficient one.

• Space complexity
It is the maximum storage or memory taken by the algorithm at any time while
searching.
• These properties are also used to compare the efficiency of the different types of
searching algorithms.
 A search problem consists of:

– A State Space. Set of all possible states where you can

be.
– A Start State. The state from where the search begins.
– A Goal Test. A function that looks at the current state
returns whether or not it is the goal state.
• The Solution to a search problem is a sequence
of actions, called the plan that transforms the
start state to the goal state.
• This plan is achieved through search algorithms.
 Types of search algorithms:
• There are far too many powerful search
algorithms out there to fit in a single article.
Instead, this article will discuss six of the
fundamental search algorithms, divided
into two categories, as shown below.
TYPES
Uniformed Search
Algorithms
 Uninformed Search Algorithms:

• The search algorithms in this section have no

additional information on the goal node other
than the one provided in the problem
definition. The plans to reach the goal state
from the start state differ only by the order
and/or length of actions. Uninformed search is
also called Blind search.
 The following uninformed search
algorithms are:
• Breadth First Search
• Depth First Search
• Iterative deepening
• Bidirectional search
• Uniform Cost Search
 Breadth First Search:

• Breadth-first search (BFS) is an algorithm for

traversing or searching tree or graph data
structures. It starts at the tree root (or some
arbitrary node of a graph, sometimes referred
to as a ‘search key’), and explores all of the
neighbor nodes at the present depth prior to
moving on to the nodes at the next depth
level.
 Breadth First Search:
• It is of the most common search strategies. It
generally starts from the root node and
examines the neighbor nodes and then moves
to the next level. It uses First-in First-out
(FIFO) strategy as it gives the shortest path to
achieving the solution.
• BFS is used where the given problem is very
small and space complexity is not considered.
example
example
 example
• The above image depicts the end-to-end process of
Breadth-First Search Algorithm. Let me explain this in more
depth.
• Assign ‘a’ as the root node and insert it into the Queue.
• Extract node ‘a’ from the queue and insert the child nodes
of ‘a’, i.e., ‘b’ and ‘c’.
• Print node ‘a’.
• The queue is not empty and has node ‘b’ and ‘c’. Since ‘b’ is
the first node in the queue, let’s extract it and insert the
child nodes of ‘b’, i.e., node ‘d’ and ‘e’.
• Repeat these steps until the queue gets empty. Note that
the nodes that are already visited should not be added to
the queue again.
 BFS Algorithm

• Set a variable NODE to the initial state, i.e.,

the root node.
• Set a variable GOAL which contains the value of
the goal state.
• Loop each node by traversing level by level until
the goal state is not found.
• While performing the looping, start removing the
elements from the queue in FIFO order.
• If the goal state is found, return goal
state otherwise continue the search.
 Why do we need BFS Algorithm?

• There are numerous reasons to utilize the BFS Algorithm to

use as searching for your dataset. Some of the most vital
aspects that make this algorithm your first choice are:
• BFS is useful for analyzing the nodes in a graph and
constructing the shortest path of traversing through these.
• BFS can traverse through a graph in the smallest number of
iterations.
• The architecture of the BFS algorithm is simple and robust.
• The result of the BFS algorithm holds a high level of
accuracy in comparison to other algorithms.
• BFS iterations are seamless, and there is no possibility of
this algorithm getting caught up in an infinite loop problem.
 Applications of BFS Algorithm

• Let’s take a look at some of the real-life applications where a BFS

algorithm implementation can be highly effective.
• Un-weighted Graphs: BFS algorithm can easily create the shortest path
and a minimum spanning tree to visit all the vertices of the graph in the
shortest time possible with high accuracy.
• P2P Networks: BFS can be implemented to locate all the nearest or
neighboring nodes in a peer to peer network. This will find the required
data faster.
• Web Crawlers: Search engines or web crawlers can easily build multiple
levels of indexes by employing BFS. BFS implementation starts from the
source, which is the web page, and then it visits all the links from that
source.
• Navigation Systems: BFS can help find all the neighboring locations from
the main or source location.
• Network Broadcasting: A broadcasted packet is guided by the BFS
algorithm to find and reach all the nodes it has the address for.
Performance measures of BFS
 Depth-first search

• The depth-first search uses Last-in, First-out

(LIFO) strategy and hence it can be
implemented by using stack. DFS uses
backtracking. That is, it starts from the initial
state and explores each path to its greatest
depth before it moves to the next path.
 DFS will follow

• Now, consider the same example tree mentioned

above.
• Here, it starts from the start state A and then
travels to B and then it goes to D. After reaching
D, it backtracks to B. B is already visited, hence it
goes to the next depth E and then backtracks to
B. as it is already visited, it goes back to A. A is
already visited. So, it goes to C and then to F. F is
our goal state and it stops there.
 EXAMPLE
The path of traversal is:
A —-> B —-> D —-> E —-> C —-> F
 DFS Algorithm

• Set a variable NODE to the initial state, i.e.,

the root node.
• Set a variable GOAL which contains the value of
the goal state.
• Loop each node by traversing deeply in one
direction/path in search of the goal node.
• While performing the looping, start removing the
elements from the stack in LIFO order.
• If the goal state is found, return goal
state otherwise backtrack to expand nodes in
other direction.
 DFS
• Advantages of DFS
• It takes lesser memory as compared to BFS.
• The time complexity is lesser when compared to
BFS.
• DFS does not require much more search.
• Disadvantages of DFS
• DFS does not always guarantee to give a solution.
• As DFS goes deep down, it may get trapped in an
infinite loop.
Performance measures OF DFS
 Application of DFS Algorithm

• Application of DFS Algorithm

• For finding the path
• To test if the graph is bipartite
• For finding the strongly connected
components of a graph
• For detecting cycles in a graph
 Difference between BFS and DFS
[Link] BFS DFS
.
1. BFS stands for Breadth First Search. DFS stands for Depth First Search.
BFS(Breadth First Search) uses Queue data DFS(Depth First Search) uses Stack data
2.
structure for finding the shortest path. structure.
BFS can be used to find single source
shortest path in an unweighted graph, In DFS, we might traverse through more
3. because in BFS, we reach a vertex with edges to reach a destination vertex from a
minimum number of edges from a source source.
vertex.
BFS is more suitable for searching vertices DFS is more suitable when there are
4.
which are closer to the given source. solutions away from source.
DFS is more suitable for game or puzzle
BFS considers all neighbors first and problems. We make a decision, then
5. therefore not suitable for decision making explore all paths through this decision. And
trees used in games or puzzles. if this decision leads to win situation, we
stop.
The Time complexity of BFS is O(V + E) The Time complexity of DFS is also O(V + E)
when Adjacency List is used and O(V^2) when Adjacency List is used and O(V^2)
Why do (BFS) and (DFS) fail in the case
of an infinite search space?
• In DFS, you would recursively look at a node’s adjacent
vertex. DFS may not end in an infinite search space.
Also, DFS may not find the shortest path to the goal.
DFS needs O(d) space, where d is depth of search.
• BFS consumes too much memory. BFS needs to store
all the elements in the same level. In the case of a tree,
the last level has N / 2 leaf nodes, the second last level
has N / 4. So, BFS needs O(N) space.
• Iterative deepening depth first search (IDDFS) is a
hybrid of BFS and DFS. In IDDFS, we perform DFS up to
a certain “limited depth,” and keep increasing this
“limited depth” after every iteration.
 Iterative deepening

• What is iterative deepening in artificial

intelligence?
• In computer science, iterative deepening
search or more specifically iterative deepening
depth-first search (IDS or IDDFS) is a state
space/graph search strategy in which a
depth-limited version of depth-first search is
run repeatedly with increasing depth limits
until the goal is found.
 INRODUCTION
• Iterative deepening depth-first search (IDDFS) is an
algorithm that is an important part of an Uninformed
search strategy just like BFS and DFS. We can define
IDDFS as an algorithm of an amalgam of BFS and DFS
searching techniques. In IDDFS, We have found certain
limitations in BFS and DFS so we have done
hybridization of both the procedures for eliminating
the demerits lying in them individually. We do a limited
depth-first search up to a fixed “limited depth”. Then
we keep on incrementing the depth limit by iterating
the procedure unless we have found the goal node or
have traversed the whole tree whichever is earlier.
 Working Algorithm of IDDFS

• In the uninformed searching strategy, the BFS and DFS

have not been so ideal in searching the element in
optimum time and space. The algorithms only
guarantee that the path will be found in exponential
time and space. So we found a method where we can
use the amalgamation of space competence of DFS and
optimum solution approach of BFS methods, and there
we develop a new method called iterative deepening
using the two of them. The main idea here lies in
utilizing the re-computation of entities of the boundary
instead of stocking them up. Every re-computation is
made up of DFS and thus it uses less space. Now let us
also consider using BFS in iterative deepening search.
 Working Algorithm of IDDFS

• Consider making a breadth-first search into an iterative

deepening search.
• We can do this by having aside a DFS which will search up
to a limit. It first does searching to a pre-defined limit depth
to depth and then generates a route length1.
• This is done by creating routes of length 1 in the DFS way.
Next, it makes way for routes of depth limit 2, 3 and
onwards.
• It even can delete all the preceding calculation all-time at
the beginning of the loop and iterate. Hence at some depth
eventually the solution will be found if there is any in the
tree because the enumeration takes place in order.
 Iterative deepening
• In order to implement the iterative deepening
search we have to mark differences among:
• Breakdown as the depth limit bound was
attained.
• A breakdown where depth bound was not
attained.
 Iterative deepening
• While in the case once we try the search
method multiple times by increasing the
depth limit each time and in the second case
even if we keep on searching multiple times
since no solution exists then it means simply
the waste of time. Thus we come to the
conclusion that in the first case failure is found
to be failing unnaturally, and in the second
case, the failure is failing naturally.
Example of Iterative Deepening
Depth-First Search
 Example of Iterative Deepening
Depth-First Search
• Here in the given tree, the starting node is A and
the depth initialized to 0. The goal node is R
where we have to find the depth and the path to
reach it. The depth from the figure is 4. In this
example, we consider the tree as a finite tree,
while we can consider the same procedure for
the infinite tree as well. We knew that in the
algorithm of IDDFS we first do DFS till a specified
depth and then increase the depth at each loop.
This special step forms the part of DLS or Depth
Limited Search.
the following traversal shows the
IDDFS search.
 Advantages
• IDDFS gives us the hope to find the solution if it exists in the tree.
• When the solutions are found at the lower depths say n, then the algorithm proves
to be efficient and in time.
• The great advantage of IDDFS is found in-game tree searching where the IDDFS
search operation tries to improve the depth definition, heuristics, and scores of
searching nodes so as to enable efficiency in the search algorithm.
• Another major advantage of the IDDFS algorithm is its quick responsiveness. The
early results indications are a plus point in this algorithm. This followed up with
multiple refinements after the individual iteration is completed.
• Though the work is done here is more yet the performance of IDDFS is better than
single BFS and DFS operating exclusively.
• Space and time complexities are expressed as: O(d) and here d is defined as goal
depth.
• Let us consider the run time of IDDFS. Let say b>l where b is branching factor and l
is the depth limit. Then next we search the goal node under the bound k. On the
depth k, we say there may be bknodes that are only generated once. Similarly, the
nodes at the depth limit k-1 is twice and thrice for k-2 depth. Thus the node
generated at depth l is k times.
 Disadvantages
• The time taken is exponential to reach the goal node.
• The main problem with IDDFS is the time and wasted
calculations that take place at each depth.
• The situation is not as bad as we may think of
especially when the branching factor is found to be
high.
• The IDDFS might fail when the BFS fails. When we are
to find multiple answers from the IDDFS, it gives back
the success nodes and its path once even if it needs to
be found again after multiple iterations. To stop the
depth bound is not increased further.
 Performance measures
• Completeness: This algorithm is complete is ifthe
branching factor is finite.
• Time Complexity:Let's suppose b is the branching
factor and depth is d then the worst-case time
complexity is O(bd).
• Space Complexity:The space complexity of IDDFS
will be O(bd).
• Optimal:IDDFS algorithm is optimal if path cost is
a non- decreasing function of the depth of the
node.
 Bidirectional Search
• In normal graph search using BFS/DFS we begin
our search in one direction usually from source
vertex toward the goal vertex, but what if we
start search from both direction simultaneously.

Bidirectional search is a graph search algorithm

which find smallest path from source to goal
vertex. It runs two simultaneous search –
• Forward search from source/initial vertex toward
goal vertex
• Backward search from goal/target vertex toward
source vertex
 Bidirectional Search
• Bidirectional search replaces single search
graph(which is likely to grow exponentially)
with two smaller sub graphs – one starting
from initial vertex and other starting from goal
vertex. The search terminates when two
graphs intersect.
Consider following simple example-
 EXAMPLE
• Suppose we want to find if there exists a path
from vertex 0 to vertex 14. Here we can
execute two searches, one from vertex 0 and
other from vertex 14. When both forward and
backward search meet at vertex 7, we know
that we have found a path from node 0 to 14
and search can be terminated now. We can
clearly see that we have successfully avoided
unnecessary exploration.
 Why bidirectional approach?

• Because in many cases it is faster, it dramatically

reduce the amount of required exploration.
Suppose if branching factor of tree is b and
distance of goal vertex from source is d, then the
normal BFS/DFS searching complexity would
be O(bd). On the other hand, if we execute two
search operation then the complexity would
be O(bd/2) for each search and total complexity
would be O(bd/2 +bd/2) which is far less than O(bd).
When to use bidirectional approach?

We can consider bidirectional approach when-

• Both initial and goal states are unique and
completely defined.
• The branching factor is exactly the same in
both directions.
 Performance measures

• Completeness : Bidirectional search is

complete if BFS is used in both searches.
• Optimality : It is optimal if BFS is used for
search and paths have uniform cost.
• Time and Space Complexity : Time and space
complexity is O(bd/2).
 Advantages

Below are the advantages:

• One of the main advantages of bidirectional
searches is the speed at which we get the
desired results.
• It drastically reduces the time taken by the
search by having simultaneous searches.
• It also saves resources for users as it requires
less memory capacity to store all the searches.
 Disadvantages

Below are the disadvantages:

• The fundamental issue with bidirectional search is that the
user should be aware of the goal state to use bidirectional
search and thereby to decrease its use cases drastically.
• The implementation is another challenge as additional code
and instructions are needed to implement this algorithm,
and also care has to be taken as each node and step to
implement such searches.
• The algorithm must be robust enough to understand the
intersection when the search should come to an end or else
there’s a possibility of an infinite loop.
• It is also not possible to search backwards through all
states.
COMPARATIVE mEASURES
 What is uniform-cost search?

• Uniform-cost search is an uninformed search

algorithm that uses the lowest cumulative cost
to find a path from the source to the
destination. Nodes are expanded, starting
from the root, according to the minimum
cumulative cost. The uniform-cost search is
then implemented using a Priority Queue.
•
 Algorithm for uniform cost search:

• Insert the root node into the priority queue

• Repeat while the queue is not empty:
Remove the element with the highest priority
If the removed node is the destination, print
total cost and stop the algorithm
Else, enqueue all the children of the current
node to the priority queue, with their
cumulative cost from the root as priority
Advantages &disadvantages of UCS
Advantages:
• Uniform cost search is optimal because at every
state the path with the least cost is chosen.
Disadvantages:
• It does not care about the number of steps
involve in searching and only concerned about
path cost. Due to which this algorithm may be
stuck in an infinite loop.
 Hill Climbing Algorithm

• A hill-climbing algorithm is an Artificial

Intelligence (AI) algorithm that increases in
value continuously until it achieves a peak
solution. This algorithm is used to optimize
mathematical problems and in other real-life
applications like marketing and job scheduling.
 A hill-climbing algorithm
• A hill-climbing algorithm is a local search
algorithm that moves continuously upward
(increasing) until the best solution is attained.
This algorithm comes to an end when the
peak is reached.
 hill-climbing algorithm
• This algorithm has a node that comprises two
parts: state and value.
• It begins with a non-optimal state (the hill’s base)
and upgrades this state until a certain
precondition is met.
• The heuristic function is used as the basis for this
precondition.
• The process of continuous improvement of the
current state of iteration can be termed as
climbing. This explains why the algorithm is
termed as a hill-climbing algorithm.
 objective
• A hill-climbing algorithm’s objective is to
attain an optimal state that is an upgrade of
the existing state. When the current state is
improved, the algorithm will perform further
incremental changes to the improved state.
This process will continue until a peak solution
is achieved. The peak state cannot undergo
further improvements.
 Features of a hill climbing algorithm

• It employs a greedy approach: This means that it moves in a

direction in which the cost function is optimized. The greedy
approach enables the algorithm to establish local maxima or
minima.
• No Backtracking: A hill-climbing algorithm only works on the
current state and succeeding states (future). It does not look at the
previous states.
• Feedback mechanism: The algorithm has a feedback mechanism
that helps it decide on the direction of movement (whether up or
down the hill). The feedback mechanism is enhanced through
the generate-and-test technique.
• Incremental change: The algorithm improves the current solution
by incremental changes.
 Types of hill climbing algorithms

• Simple hill climbing

• Steepest – Ascent hill climbing
• Stochastic hill climbing
 Simple Hill Climbing:

• Simple hill climbing is the simplest way to

implement a hill climbing algorithm. It only
evaluates the neighbor node state at a time and
selects the first one which optimizes current cost
and set it as a current state. It only checks it's
one successor state, and if it finds better than the
current state, then move else be in the same
state. This algorithm has the following features:
• Less time consuming
• Less optimal solution and the solution is not
guaranteed
 Algorithm for Simple Hill Climbing:

• Step 1: Evaluate the initial state, if it is goal state then

return success and Stop.
• Step 2: Loop Until a solution is found or there is no new
operator left to apply.
• Step 3: Select and apply an operator to the current state.
• Step 4: Check new state:
– If it is goal state, then return success and quit.
– Else if it is better than the current state then assign new state as
a current state.
– Else if not better than the current state, then return to step2.
• Step 5: Exit.
 2. Steepest-Ascent hill climbing:

• The steepest-Ascent algorithm is a variation of simple hill climbing algorithm. This

algorithm examines all the neighboring nodes of the current state and selects one
neighbor node which is closest to the goal state. This algorithm consumes more
time as it searches for multiple neighbors
• Algorithm for Steepest-Ascent hill climbing:
• Step 1: Evaluate the initial state, if it is goal state then return success and stop, else
make current state as initial state.
• Step 2: Loop until a solution is found or the current state does not change.
– Let SUCC be a state such that any successor of the current state will be better than it.
– For each operator that applies to the current state:
• Apply the new operator and generate a new state.
• Evaluate the new state.
• If it is goal state, then return it and quit, else compare it to the SUCC.
• If it is better than SUCC, then set new state as SUCC.
• If the SUCC is better than the current state, then set current state to SUCC.
• Step 5: Exit.
 3. Stochastic hill climbing:

• Stochastic hill climbing does not examine for

all its neighbor before moving. Rather, this
search algorithm selects one neighbor node at
random and decides whether to choose it as a
current state or examine another state.
 State-space Diagram for Hill Climbing:

• The state-space landscape is a graphical representation

of the hill-climbing algorithm which is showing a graph
between various states of algorithm and Objective
function/Cost.
• On Y-axis we have taken the function which can be an
objective function or cost function, and state-space on
the x-axis. If the function on Y-axis is cost then, the
goal of search is to find the global minimum and local
minimum. If the function of Y-axis is Objective
function, then the goal of the search is to find the
global maximum and local maximum.
State-space Diagram for Hill Climbing
 Different regions in the state space
landscape:
• Local Maximum: Local maximum is a state which is better
than its neighbor states, but there is also another state
which is higher than it.
• Global Maximum: Global maximum is the best possible
state of state space landscape. It has the highest value of
objective function.
• Current state: It is a state in a landscape diagram where an
agent is currently present.
• Flat local maximum: It is a flat space in the landscape
where all the neighbor states of current states have the
same value.
• Shoulder: It is a plateau region which has an uphill edge.
 Problems in Hill Climbing Algorithm:

• 1. Local Maximum: A local maximum is a peak

state in the landscape which is better than each
of its neighboring states, but there is another
state also present which is higher than the local
maximum.
• Solution: Backtracking technique can be a
solution of the local maximum in state space
landscape. Create a list of the promising path so
that the algorithm can backtrack the search space
and explore other paths as well.
Problems in Hill Climbing Algorithm
Problems in Hill Climbing Algorithm
• 2. Plateau: A plateau is the flat area of the search
space in which all the neighbor states of the
current state contains the same value, because of
this algorithm does not find any best direction to
move. A hill-climbing search might be lost in the
plateau area.
• Solution: The solution for the plateau is to take
big steps or very little steps while searching, to
solve the problem. Randomly select a state which
is far away from the current state so it is possible
that the algorithm could find non-plateau region.
Problems in Hill Climbing Algorithm
Problems in Hill Climbing Algorithm
• 3. Ridges: A ridge is a special form of the local
maximum. It has an area which is higher than
its surrounding areas, but itself has a slope,
and cannot be reached in a single move.
• Solution: With the use of bidirectional search,
or by moving in different directions, we can
improve this problem.
Problems in Hill Climbing Algorithm
Informed search
algorithms
 informed search algorithm
• The informed search algorithm is also called
heuristic search or directed search. In contrast to
uninformed search algorithms, informed search
algorithms require details such as distance to
reach the goal, steps to reach the goal, cost of the
paths which makes this algorithm more efficient.
• Here, the goal state can be achieved by using the
heuristic function.
• The heuristic function is used to achieve the goal
state with the lowest cost possible. This function
estimates how close a state is to the goal.
 heuristic function
• The heuristic function is used in Informed Search, and it finds the
most promising path. It takes the current state of the agent as its
input and produces the estimation of how close the agent is from
the goal. The heuristic method, however, might not always give the
best solution, but it guaranteed to find a good solution in a
reasonable time. Heuristic function estimates how close a state is to
the goal. It is represented by h(n), and it calculates the cost of an
optimal path between the pair of states. The value of the heuristic
function is always positive.
• Admissibility of the heuristic function is given as:
• h(n) <= h*(n)
• Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence
heuristic cost should be less than or equal to the estimated cost.
 1. Greedy best-first search algorithm

• Greedy best-first search uses the properties of

both depth-first search and breadth-first search.
Greedy best-first search traverses the node by
selecting the path which appears best at the
moment. The closest path is selected by using the
heuristic function.
• Consider the below
graph with the heuristic values.
•
Greedy best-first search algorithm
 Greedy best-first search algorithm

• Here, A is the start node and H is the goal node.

• Greedy best-first search first starts with A and
then examines the next neighbour B and C. Here,
the heuristics of B is 12 and C is 4. The best path
at the moment is C and hence it goes to C. From
C, it explores the neighbours F and G. the
heuristics of F is 8 and G is 2. Hence it goes to G.
From G, it goes to H whose heuristic is 0 which is
also our goal state.
•
 Greedy best-first search algorithm

Advantages of Greedy best-first search

• Greedy best-first search is more efficient compared
with breadth-first search and depth-first search.
Disadvantages of Greedy best-first search
• In the worst-case scenario, the greedy best-first search
algorithm may behave like an unguided DFS.
• There are some possibilities for greedy best-first to get
trapped in an infinite loop.
• The algorithm is not
an optimal one.
 2. A* search algorithm

• A* search algorithm is a combination of both

uniform cost search and greedy best-first
search algorithms. It uses the advantages of
both with better memory usage. It uses a
heuristic function to find the shortest path. A*
search algorithm uses the sum of both the
cost and heuristic of the node to find the best
path.
 EXAMPLE
• Consider the
following graph with the heuristics values as
follows.
 EXAMPLE
• Let A be the start node and H be the goal node.
• First, the algorithm will start with A. From A, it can go to B, C, H.
• Note the point that A* search uses the sum of path cost and heuristics value to determine the path.
• Here, from A to B, the sum of cost and heuristics is 1 + 3 = 4.
• From A to C, it is 2 + 4 = 6.
• From A to H, it is 7 + 0 = 7.
• Here, the lowest cost is 4 and the path A to B is chosen. The other paths will be on hold.
• Now, from B, it can go to D or E.
• From A to B to D, the cost is 1 + 4 + 2 = 7.
• From A to B to E, it is 1 + 6 + 6 = 13.
• The lowest cost is 7. Path A to B to D is chosen and compared with other paths which are on hold.
• Here, path A to C is of less cost. That is 6.
• Hence, A to C is chosen and other paths are kept on hold.
• From C, it can now go to F or G.
• From A to C to F, the cost is 2 + 3 + 3 = 8.
• From A to C to G, the cost is 2 + 2 + 1 = 5.
• The lowest cost is 5 which is also lesser than other paths which are on hold. Hence, path A to G is chosen.
• From G, it can go to H whose cost is 2 + 2 + 2 + 0 = 6.
• Here, 6 is lesser than other paths cost which is on hold.
• Also, H is our goal state. The algorithm will terminate here.
 A* search algorithm
Advantages of A* search algorithm
• This algorithm is best when compared with other
algorithms.
• This algorithm can be used to solve very complex
problems also it is an optimal one.
Disadvantages of A* search algorithm
• The A* search is based on heuristics and cost. It
may not produce the shortest path.
• The usage of memory is more as it keeps all the
nodes in the memory.
 AO* Algorithm

• AO* Algorithm basically based on problem

decompositon (Breakdown problem into small
pieces)
• When a problem can be divided into a set of sub
problems, where each sub problem can be solved
separately and a combination of these will be a
solution, AND-OR graphs or AND - OR trees are
used for representing the solution.
• The decomposition of the problem or problem
reduction generates AND arcs.
AO* Algorithm
 AO* Algorithm

• The figure shows an AND-OR graph

• To pass any exam, we have two options, either cheating or
hard work.
• In this graph we are given two choices, first do cheating or
(The red line) work hard and (The arc) pass.
• When we have more than one choice and we have to pick
one, we apply OR condition to choose one.(That's what we
did here).
• Basically the ARC here denote AND condition.
• Here we have replicated the arc between the work hard
and the pass because by doing the hard work possibility of
passing an exam is more than cheating.
 How AO* works

• Let's try to understand it with the following

diagram
 How AO* works
• The algorithm always moves towards a lower cost value.
• Basically, We will calculate the cost function here (F(n)= G
(n) + H (n))
• H: heuristic/ estimated value of the nodes. and G: actual
cost or edge value (here unit value).
• Here we have taken the edges value 1 , meaning we have
to focus solely on the heuristic value.
• The Purple color values are edge values (here all are same
that is one).
• The Red color values are Heuristic values for nodes.
• The Green color values are New Heuristic values for nodes.
 How AO* works
• Procedure:
• In the above diagram we have two ways from A to D or A to B-C (because
of and condition). calculate cost to select a path
• F(A-D)= 1+10 = 11 and F(A-BC) = 1 + 1 + 6 +12 = 20
• As we can see F(A-D) is less than F(A-BC) then the algorithm choose the
path F(A-D).
• Form D we have one choice that is F-E.
• F(A-D-FE) = 1+1+ 4 +4 =10
• Basically 10 is the cost of reaching FE from D. And Heuristic value of node
D also denote the cost of reaching FE from D. So, the new Heuristic value
of D is 10.
• And the Cost from A-D remain same that is 11.
• Suppose we have searched this path and we have got the Goal State, then
we will never explore the other path. (this is what AO* says but here we
are going to explore other path as well to see what happen)
 How AO* works
• Let's Explore the other path:
• In the above diagram we have two ways from A to D or A to B-C (because of and condition). calculate cost to
select a path
• F(A-D)= 1+10 = 11 and F(A-BC) = 1 + 1 + 6 +12 = 20
• As we know the cost is more of F(A-BC) but let's take a look
• Now from B we have two path G and H , let's calculate the cost
• F(B-G)= 5+1 =6 and F(B-H)= 7 + 1 = 8
• So, cost from F(B-H) is more than F(B-G) we will take the path B-G.
• The Heuristic value from G to I is 1 but let's calculate the cost form G to I.
• F(G-I) = 1 +1 = 2. which is less than Heuristic value 5. So, the new Heuristic value form G to I is 2.
• If it is a new value, then the cost from G to B must also have changed. Let's see the new cost form (B to G)
• F(B-G)= 1+2 =3 . Mean the New Heuristic value of B is 3.
• But A is associated with both B and C .
• As we can see from the diagram C only have one choice or one node to explore that is J. The Heuristic value of C
is 12.
• Cost form C to J= F(C-J) = 1+1= 2 Which is less than Heuristic value
• Now the New Heuristic value of C is 2.
• And the New Cost from A- BC that is F(A-BC) = 1+1+2+3 = 7 which is less than F(A-D)=11.
• In this case Choosing path A-BC is more cost effective and good than that of A-D.
• But this will only happen when the algorithm explores this path as well. But according to the algorithm, algorithm
will not accelerate this path (here we have just did it to see how the other path can also be correct).
• But it is not the case in all the cases that it will happen in some cases that the algorithm will get optimal solution.
 A* Vs AO*

• Both are part of informed search technique

and use heuristic values to solve the problem.
• The solution is guaranteed in both algorithm.
• A* always gives an optimal solution (shortest
path with low cost) But It is not guaranteed to
that AO* always provide an optimal
solutions.
• Reason: Because AO* does not explore all the
solution path once it got solution.
 Comparison of uninformed and
informed search algorithms
• Uninformed search is also known as blind
search whereas informed search is also called
heuristics search. Uniformed search does not
require much information. Informed search
requires domain-specific details. Compared to
uninformed search, informed search strategies
are more efficient and the time complexity of
uninformed search strategies is more.
Informed search handles the problem better
than blind search.
Constraint Satisfaction
Problems
 INTRODUCTION
• In this section, we will discuss another type of
problem-solving technique known as
Constraint satisfaction technique. By the
name, it is understood that constraint
satisfaction means solving a problem under
certain constraints or rules.
 Constraint satisfaction
• Constraint satisfaction is a technique where a
problem is solved when its values satisfy
certain constraints or rules of the
problem. Such type of technique leads to a
deeper understanding of the problem
structure as well as its complexity.
 Constraint satisfaction depends on
three components, namely:
• X: It is a set of variables.
• D: It is a set of domains where the variables
reside. There is a specific domain for each
variable.
• C: It is a set of constraints which are followed
by the set of variables.
 Solving Constraint Satisfaction
Problems
• The requirements to solve a constraint
satisfaction problem (CSP) is:
• A state-space
• The notion of the solution.
• A state in state-space is defined by assigning
values to some or all variables such as
• {X1=v1, X2=v2, and so on…}.
An assignment of values to a variable
can be done in three ways:
• Consistent or Legal Assignment: An assignment
which does not violate any constraint or rule is
called Consistent or legal assignment.
• Complete Assignment: An assignment where
every variable is assigned with a value, and the
solution to the CSP remains consistent. Such
assignment is known as Complete assignment.
• Partial Assignment: An assignment which assigns
values to some of the variables only. Such type of
assignments are called Partial assignments.
 Types of Domains in CSP

• There are following two types of domains which

are used by the variables :
• Discrete Domain: It is an infinite domain which
can have one state for multiple variables. For
example, a start state can be allocated infinite
times for each variable.
• Finite Domain: It is a finite domain which can
have continuous states describing one domain for
one specific variable. It is also called a continuous
domain.
 Constraint Types in CSP

• With respect to the variables, basically there are

following types of constraints:
• Unary Constraints: It is the simplest type of
constraints that restricts the value of a single
variable.
• Binary Constraints: It is the constraint type which
relates two variables. A value x2 will contain a
value which lies between x1 and x3.
• Global Constraints: It is the constraint type which
involves an arbitrary number of variables.
Some special types of solution algorithms
are used to solve the following types of
constraints:
• Linear Constraints: These type of constraints are
commonly used in linear programming where
each variable containing an integer value exists in
linear form only.
• Non-linear Constraints: These type of constraints
are used in non-linear programming where each
variable (an integer value) exists in a non-linear
form.
• Note: A special constraint which works in real-
world is known as Preference constraint.
 CSP Problems

• Constraint satisfaction includes those

problems which contains some constraints
while solving the problem. CSP includes the
following problems:
 Graph Coloring:
• Graph Coloring: The problem where the
constraint is that no adjacent sides can have
the same color.
 Sudoku Playing:
• The gameplay where the constraint is that no
number from 0-9 can be repeated in the same
row or column.
 Crossword:
• Crossword: In crossword problem, the
constraint is that there should be the correct
formation of the words, and it should be
meaningful.
N queen problem
Thanks…!!