UNIT II

Problem Solving by Searching

Problem Solving by Searching-Problem-Solving Agents, Well-defined problems and solutions, examples

Problems, searching for Solutions, Uninformed Search Strategies-Breadth-first search, Uniform-cost search,
Depth-first search, Depth-limited search, Iterative deepening depth-first search, Bidirectional search, Greedy
best-first search, A* Search, AO* search Informed (Heuristic) Search Strategies, Heuristic Functions

2.1 Problem Solving by Searching – Introduction

Problem-solving agents are intelligent systems that operate in an environment and attempt to find
solutions to problems. These agents follow a goal-oriented approach, where they analyze the current state, set
goals, and take actions to transition from the current state to a desired state.
Problem-solving is an artificial intelligence technique, including various techniques such as forming
efficient algorithms, heuristics, and performing root cause analysis to find desirable solutions.

2.1.1 Well- defined Problems and Solutions

Well-defined problems are those with clear and unambiguous goals, initial states, and possible actions.
These problems are typically represented in a way that makes it easy for an agent to understand and manipulate
the information. Here are some examples of well-defined problems and their solutions

Example Problems

In each of these examples, the problems are well-defined, and the solutions involve a systematic
approach, often leveraging algorithms to explore and evaluate possible states and actions. Problem-solving
agents can be designed to handle a wide range of problems by adapting their strategies and algorithms to the
specific characteristics of each problem domain.

Tic-Tac-Toe
Problem
The goal is to get three of your marks in a row horizontally, vertically, or diagonally on a 3x3 grid.
Tic-tac-toe is a simple game for two players, where players take turns placing their symbols in a 3x3 grid. The
player who places three of their symbols in a horizontal, vertical, or diagonal row wins.

Solution
The solution involves determining the best move at each turn based on the current state of the board.
Various algorithms, like the minimax algorithm, can be employed to find an optimal strategy.

X O O
X X O
O O X

4 Queen Problem

Problem
The goal of the 4-queen 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.)
Solution
4 Queens Problem using Backtracking Algorithm. Place each queen one by one in different rows, starting
from the topmost row. While placing a queen in a row, check for clashes with already placed queens. For any
column, if there is no clash then mark this row and column as part of the solution by placing the queen
 Q1
Q2
Q3
Q4

Sudoku
Problem
Fill a 9x9 grid with digits from 1 to 9, ensuring that each row, column, and 3x3 subgrid contains every digit
exactly once.
Solution
The solution requires logical deduction and can be found through a systematic process of elimination and
constraint satisfaction.

Some Real World Problems

Route Planning

Problem
It is a real world problem. From the given a map with locations and connections between them, we need
to find the shortest path from one location to another.
Solution
This problem can be solved using a variety of algorithms, including Dijkstra's algorithm, Bellman-Ford
algorithm, and A* search.
Dijkstra's algorithm is a greedy algorithm that works by iteratively finding the shortest path from a source
node to all other nodes in the graph. The algorithm begins by marking the source node as visited and setting its
distance to 0. It then iteratively selects the unvisited node with the smallest distance from the source node and
marks it as visited. The algorithm then updates the distances of all unvisited nodes that are adjacent to the visited
node. The algorithm terminates when all nodes have been visited.
Bellman-Ford algorithm is another greedy algorithm that works by iteratively relaxing all edges in the
graph. The algorithm begins by initializing the distances of all nodes to infinity. It then iteratively relaxes all edges
in the graph, updating the distance of each node to the minimum of its current distance and the distance of its
neighbor plus the weight of the edge between them. The algorithm terminates when no edges can be relaxed
further.
A* search is a heuristic search algorithm that works by using a heuristic function to estimate the distance
from a node to the goal node. The algorithm begins by initializing the distances of all nodes to infinity and the
heuristic function for each node. It then iteratively selects the unvisited node with the smallest estimated
distance to the goal node and marks it as visited. The algorithm then updates the distances of all unvisited nodes
that are adjacent to the visited node. The algorithm terminates when the goal node is reached.
The shortest path problem can be applied to a variety of real-world problems, such as finding the shortest
route between two cities, finding the shortest path through a maze, and finding the shortest path between two
nodes in a network.

2. 1. 2 Searching for Solutions

Searching for solutions is a fundamental aspect of problem-solving, and various algorithms can be
employed to explore the space of possible solutions efficiently. Based on the search problems and technique used
to solve that problem, there are two strategies, namely
 1. Uninformed (Blind) Search Strategies
2. Informed (Heuristic) Search Strategies

Search algorithms are used to resolve search problems. For example, search for the shortest path
between two given points, searching for a goal, and so on.
Suppose we want to move from point A to point B and there are more than one paths between these two
points. Obviously, we have to choose the optimal path. These types of problems can be solved using search
algorithms.

Search Algorithm Terminologies

Searching
Searching is a step by step procedure to solve a search-problem in a given search space.
Search Space
Search space represents a set of possible solutions, which a system may have.
Start State
It is a state from where agent begins the search.
Goal test
It is a function which observe the current state and returns whether the goal state is achieved or
not.
Search tree
A tree representation of search problem is called Search tree. The root of the search tree is the root
node which is corresponding to the initial state.
Actions
It gives the description of all the available actions to the agent.
Transition model
A description of what each action is doing, can be represented as a transition model.
Path Cost
It is a function which assigns a numeric cost to each path.
Solution
It is an action sequence which leads from the start node to the goal node.
Optimal Solution
If a solution has the lowest cost among all solutions.

Measuring problem-solving performance

The output of a problem-solving algorithm is either failure or a solution. (Some algorithms might get stuck
in an infinite loop and never return an output.) We will evaluate an algorithm's performance in four ways. These
four essential properties of search algorithms are used to compare the efficiency of the algorithms.

Completeness
A search algorithm is said to be complete if it guarantees to return a solution if at least any solution
exists for any random input.
Optimality
If a solution found for an algorithm is guaranteed to be the best solution (lowest path cost) among
all other solutions, then such a solution for is said to be an optimal solution.
Time Complexity
Time complexity is a measure of time for an algorithm to complete its task.
Space Complexity
It is the maximum storage space required at any point during the search, as the complexity of the
problem.

2.2 Uninformed (Blind) Search Strategies

In artificial intelligence (AI), uninformed search, also known as blind search, is a search algorithm
that explores a problem space without any specific knowledge or information about the problem.
This type of search algorithm that does not use additional information to guide the search process.
Instead, these algorithms explore the search space in a systematic, but blind manner without considering the cost
of reaching the goal.
The term uninformed refers that they have no additional information about states beyond that provided
in the problem definition. All they can do is generate successors and distinguish a goal state from a non-goal
state.
The uninformed search does not contain any domain knowledge such as closeness, the location of the
goal. It operates in a brute-force way as it only includes information about how to traverse the tree and how to
identify leaf and goal nodes. Uninformed search applies a way in which search tree is searched without any
information about the search space like initial state operators and test for the goal, so it is also called blind
search. It examines each node of the tree until it achieves the goal node.

2.2.1 Breadth-First Search (BFS)

The Breadth First Search (BFS) algorithm is used to search a graph/tree data structure for a vertex that
meets a set of criteria. It starts at the root of the graph and visits all vertices at the current depth level before
moving on to the vertices at the next depth level.
 The graph data structure may contain cycles (trees does not have) so we may come to the same vertex
again. To avoid processing a vertex more than once, we can maintain an array named visited, to represent
whether the vertex is visited or not. To process the graph, queue data structure(FIFO) is used for the
vertices/nodes. It means that the neighbors of the vertex will be displayed, beginning with the vertex that was put
first.

Starting from the root, all the vertices at a particular level are visited first and then the vertices of the
next level are traversed till all the vertices are visited. To implement this queue is used. All the adjacent
unvisited vertices of the current level are pushed into the queue and the vertices of the current level are
marked visited and popped from the queue.

Algorithm Steps
Step 1: Start with the source node.
Step 2 : Add that node to the queue (at front end) and to the visited list.
Step 3 : Make a list of the nodes as visited that are close to that vertex.
Step 4 : And dequeuer (remove) the nodes once they are visited.
Step 5 : Repeat the actions until the queue is empty.

Example
Consider the graph given below
Now, Queue becomes empty, So, terminate the process.

The above procedure is called traversing the graph. By using this procedure, we can access all the vertex
of the graph. In real applications, we can traverse/access all records available in the graph structure. And, well
known Linear search can be employed to empower the algorithm.

Advantages
 The BFS algorithm has a simple and reliable architecture.
 The BFS algorithm helps evaluate nodes in a graph and determines the shortest path to traverse nodes.
 The BFS algorithm can traverse a graph in the fewest number of iterations possible.
 The iterations in the BFS algorithm are smooth, and there is no way for this method to get stuck in an
infinite loop.
 In comparison to other algorithms, the BFS algorithm's result has a high level of accuracy.

Application of Breadth-First Search Algorithm

 BFS is used to construct Minimum Spanning Tree, which is useful in other applications
 BFS is used to discover all neighbor nodes in peer-to-peer networks
 Crawlers create indexes based on breadth-first. The goal is to start at the original page and follow all of
the links there, then repeat.
 In Social Networking Websites BFS is used to identify persons within a certain distance 'd' from a
person in social networks up to 'd's levels.
  In GPS Navigation System, BFS is used to find all nearby locations

2.2.2 Uniform Cost Search (UCS)

Uniform Cost Search (UCS) is a type of uninformed search that performs a search based on the lowest
path cost. UCS helps us to find the path from the starting node to the goal node with the minimum path cost
UCS is a search algorithm used in artificial intelligence to find the path with the lowest cumulative cost
from a start node to one of the ending nodes. It's a best-first search algorithm that expands the node with the
lowest path cost first.

A uniform-cost search algorithm is implemented by the priority queue. It gives maximum priority to the
lowest cumulative cost. Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the
same. For example,

The path cost of going from node A to node B is calculated by their edge weight. Here path A B is 5 and
path A  C  B is 2+2=4 . Second path would be selected in terms of uniform cost search for maximum
throughput.

The time complexity for Uniform-Cost Search is O( m ^ (1+floor(l/e)))

m is the maximum number of neighbours a node has
l is the length of the shortest path to the goal state
e is the least cost of an edge

Consider the Example below, Finding the path A  G using Uniform Cost Search

Frontier List Expand List Explored List

1. { (A,0) } A NULL
2. { (AD,3) , (AB, 5) } D {A}
3. { (AB,5) , (ADE,5) , (ADF , 5) } B {A,D}
4. { (ADE,5) , ( ADF , 5), (ABC, 6)} E {A,D,B}
5. { (ADF,5), (ABC ,6), (ADEB , 9) }(B is F {A,D,B,E}
already explored)
6. { (ABC , 6) , (ADFG ,8) C { A , D , B , E, F }
7. { (ADFG ,8), (ABCE,12) , G { A , D , B , E, F , C }
(ABCG,14) } (E is already explored)
8. { (ADFG,8) } NULL { A , D , B , E, F , C , G }
#GOAL Found!
Hence we get
Actual Path : A  D  F  G , with Path Cost = 8.
Traversed Path : A  D  B  E  F  C  G

Advantages of UCS
 Uniform cost search is optimal because at every state the path with the least cost is chosen.
Disadvantages of UCS
 It does not care about the number of steps involve in searching and only concerned about path cost. Due
to this algorithm may be stuck in an infinite loop.

2.2.3 Depth-First Search (DFS)

Depth-First Search or DFS algorithm is a recursive algorithm that uses the backtracking principle.
(Backtracking is an algorithm technique for finding all possible solutions using recursion). It requires conducting
exhaustive searches of all nodes by moving forward if possible and backtracking if necessary. To visit the next
node, pop the top node from the stack and push all of its nearby nodes into a stack.

It is called the depth-first search because it starts from the root node and follows each path to its greatest
depth node before moving to the next path.

The algorithm starts at the root node and explores each branch as far as possible before backtracking.
This technique is useful when the solution may be deep in the search space, but it may not guarantee finding the
optimal solution.

ALGORITHM

1. First, initiate a stack with the starting vertex for the traversal.
2. Pop from the stack and set this vertex as the “current” element or node.
3. Now, find the neighboring vertexes (of the current node), and if they haven’t been visited push them into
the stack.
4. If no unvisited vertexes remain, go back and pop a vertex from the stack.
5. Repeat steps 2, 3, and 4 until the stack is empty.

Example

Consider the graph given below:

A C
E

B D
Solution
Initially the stack is empty. We should push the starting vertex into the stack.

Step 1: Select A as starting vertex and mark it as visited. To mark it as visited, push it into the stack.

Step 2: Check for nearby vertices of A and mark them as visited and put them into the stack. So
B and C are marked and pushed into the stack.

Step 3: Check for nearby vertices of C and mark them as visited and put them into the stack. So D and E are
marked and pushed into the stack.

Step 4: Check for nearby vertices of E. Nearby vertices of C and D already marked as visited and pushed into the
stack. So pop the top element of Stack ie E.
Step 5: Now the top of the stack is D. Nearby vertices of D, that is B and C already marked as visited and pushed
into the stack. So pop the top element of Stack ie D.

Step 6: Similarly, now the top of the stack is C. Nearby vertices of C are already marked as visited and pushed
into the stack. So pop the top element of Stack ie C.

Step 7: Now, the top of the stack is B, and its nearby vertices are marked, so pop it.

Step 8: Now, the top of the stack is A, and its nearby vertices are marked, so pop it.

Advantages of DFS

 DFS requires very less memory as it only needs to store a stack of the nodes on the path from root node
to the current node.
 It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path).

Disadvantages of DFS

 There is the possibility that many states keep re-occurring, and there is no guarantee of finding the
solution.
 DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.

Difference between BFS and DFS

 BFS works better when a user searches for the vertices that stay closer to any given source. DFS works
better when a user can find the solutions away from any given source. The amount of memory required for BFS is
more than that of DFS. The amount of memory required for DFS is less than that of BFS.

2.2.4 Depth-limited search

A depth-limited search algorithm is similar to depth-first search with a predetermined limit. Depth-limited
search can solve the drawback of the infinite path in the Depth-first search. In this algorithm, the node at the
depth limit will treat as it has no successor nodes further.

Depth-limited search can be terminated with two Conditions of

1. Standard failure value
It indicates that problem does not have any solution.
2. Cutoff failure value
It defines no solution for the problem within a given depth limit. But really target exists, but it is
too deep for us to traverse.

ALGORITHM
This algorithm essentially follows a similar set of steps as in the DFS algorithm.

Step 1: The start node or vertex is added to the beginning of the stack.
Step 2: Then it is marked as visited, and if the current is not the goal node in the search, then we push next node
on top of the stack.
Step 3: repeat the step 2 in the same depth limit and move along depth-wise to check for the goal nodes.
Step 4 :If goal node is not found and depth limit is found to be reached, then we retrace back to nearest nodes
that remain unvisited or unexplored.
Step 5: Repeat the steps 2 -3

We continue to perform these steps in iterative ways unless the goal node is reached or until all nodes within
depth limit have been explored for the goal.

We follow normal DFS and start with the root node S at level 0. While searching, after the level 2, we are
exploring right-sub-tree, because our depth limit is 2.

Advantages
  Depth-limited search is Memory efficient.

Disadvantages

 Depth-limited search also has a disadvantage of incompleteness.

 It may not be optimal if the problem has more than one solution.

2.2.5 Iterative Deepening Depth-First Search (IDDFS)

The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds
out the best depth limit and does it by gradually increasing the limit until a goal is found.
This algorithm performs depth-first search up to a certain "depth limit", and it keeps increasing the depth limit
after each iteration until the goal node is found.
The iterative deepening search algorithm, which repeatedly applies depth limited search with increasing
limits. It terminates when a solution is found or if the depth limited search returns failure, meaning that no
solution exists.
This Search algorithm combines the benefits of Breadth-first search's fast search and depth-first search's
memory efficiency. IDDFS is useful uninformed search when search space is large, and depth of goal node is
unknown. IDDFS combines depth-first search’s space-efficiency and breadth-first search’s fast search (for nodes
closer to root).

ALGORITHM

Step 1: Start with a depth limit of 0.

Step 2: Perform DFS with the current depth limit.
Step 3: If the goal is found during the DFS, return the solution.
Step 4: If the goal is not found, increment the depth limit and repeat steps 2-3.

Consider the tree given below.

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. In this example, the depth is 4. We consider the tree as a finite
tree, while we can consider the same procedure for the infinite tree as well. 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.

Depth Limits IDDFS

0 A
1 ABCD
2 ABEFCGDH
3 ABEIFJKCGLDHMN
4 ABEIFJKOPCGLRDHMNS
 Node Found

Advantages
 It combines the benefits of BFS and DFS search algorithm in terms of fast search and memory efficiency.

Disadvantages
 The main drawback of IDDFS is that it repeats all the work of the previous phase.
 Repeatedly perform depth-first searches with increasing depth limits until the solution is found.
 Combines advantages of BFS and DFS, ensuring optimality while using memory efficiently.

2.2.5 Bidirectional search

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.

Unlike traditional search algorithms that operate in a unidirectional manner (from the start node to the
goal node), bidirectional search explores the solution space from both the start and goal nodes simultaneously.
This approach can be particularly effective in reducing the time complexity of certain search problems.

In bidirectional search, the goal is known from the outset, and the objective is to find a path from the
start node to the goal node. The reason for using bidirectional search despite knowing the goal is to potentially
reduce the search space and computational effort required to find the path.

The advantage of bidirectional search lies in its ability to effectively prune the search space. By searching
from both the start and goal nodes simultaneously, it can potentially reduce the number of nodes explored
compared to a unidirectional search. This is particularly useful in large search spaces where exploring every
possible path from the start node to the goal node would be computationally expensive.

ALGORITHM
Step 1: Initialization
Begin with both a start node and a goal node.
Step 2: Search from both directions
Conduct simultaneous searches from the start node and the goal node. Essentially, you're working
towards each other.
Step 3: Intersection
During the search process, if the search paths from both directions intersect, it indicates that a path has
been found from the start node to the goal node.

Example
Consider the example below
Step 1: Let A is the initial node and O is the goal node, and H is the intersection node.
Step 2: We will start searching simultaneously from start to goal node and backward from goal to start
node.
Step 3: Whenever the forward search and backward search intersect at one node, then the searching
stops.

Advantages
 Bidirectional search is fast
 Bidirectional search requires less memory

Disadvantages
 Implementation of the bidirectional search tree is difficult.
 In bidirectional search, one should know the goal state in advance.

Comparing uninformed search strategies

These algorithms vary in their efficiency, optimality, and applicability to different types of problems. The
choice of algorithm depends on the nature of the problem, available resources, and the specific requirements of
the application. Additionally, heuristics play a crucial role in guiding search algorithms towards promising areas of
the solution space, improving their efficiency.

Criteria BFS – UCS – DFS – Depth DLS- IDS - BDS -

Breadth First Uniform Cost First Search Depth Iterative Bidirectional
Search Search Limited Deepening search
Search Depth-First
Search
Completeness Yesa Yes a,b No No Yesa Yesa,d
Time O(bd+l) O(bl+[C*/£]) O(bm) O(bl) O(bd) O(bd/2)
complexity
Space O(bd+l) O(bl+[C*/£]) O(bm) O(bl) O(bd) O(bd/2)
Complexity
Optimality Yesc Yes No No Yesc Yesc,d

Evaluation of search strategies

b  branching factor
d  depth of the shallowest solution
 m  maximum depth of the search tree
l  depth limit
Superscript caveats are as follows
a complete if b is finite
b complete if step costs >= £ for positive £
c optimal if step costs are all identical
d if both directions use breadth-first search

Informed (Heuristic) Search Strategies

Informed search algorithms are using domain knowledge to search. In an informed search, problem
information is available and it will guide the algorithm to complete the task.
The uninformed search algorithms looked through the search space for all possible solutions of the
problem without having any additional knowledge about search space. But informed search algorithm contains an
array of knowledge such as how far we are from the goal, path cost, how to reach to goal node, etc. This
knowledge helps agents to explore less to the search space and find more efficiently the goal node. Informed
search strategies can find a solution more efficiently than an uninformed search strategy.
The informed search algorithm is more useful for large search space. Informed search algorithm uses the
idea of heuristic, so it is also called Heuristic search. A heuristic is a way which might not always be guaranteed for
best solutions but guaranteed to find a good solution in reasonable time.

Informed search can solve much complex problem which could not be solved in another way.

2.3.1 Greedy Best-First Search (GBFS)

Greedy Best-First Search (GBFS) is a graph search algorithm that extends the idea of the standard best-
first search. In GBFS, nodes are expanded based on a heuristic evaluation function that estimates the cost from
the current node to the goal node. It only focuses on the estimated cost from the current node to the goal.

Greedy Best-First Search is an AI search algorithm that attempts to find the most promising path from a
given starting point to a goal. The algorithm works by evaluating the cost of each possible path and then
expanding the path with the lowest cost. This process is repeated until the goal is reached.

GBFS is efficient in terms of memory usage because it does not store the entire path from the start node
to the current node. GBFS does not guarantee optimality, because it may get stuck where the heuristic leads the
search away from the optimal path.

GBFS is a heuristic search algorithm that prioritizes nodes based solely on the estimated cost to the goal,
without considering the total path cost. It is often used in scenarios where memory is limited or when a quick but
not necessarily optimal solution is acceptable.

In the GBFS algorithm, we expand the node which is closest to the goal node and the closest cost is
estimated by heuristic function, i.e.
h(n)= g(n)
where,
n current node
g(n)  estimated cost from node n to the immediate goal
h(n) heuristic function used to find the successor node
ALGORITHM

Step 1: Start with the initial node as the current node.

Step 2: Expand the current node by generating its successors.
Step 3: Evaluate each successor node using a heuristic function, which estimates the cost from the
successor node to the goal node.
Step 4: Select the successor node with the lowest heuristic value as the new current node.
Step 5: Repeat steps 2-4 until either the goal node is found or there are no more nodes to expand.

Example
Consider the example, to find the path from A to G

As in the diagram, Node A is assigned as a starting node

Therefore, the Goal Node can be reached by using the path

ACFG

Advantages

 Greedy Best-First Search is a relatively straightforward algorithm, making it easy to implement.

 It doesn't require maintaining the full cost of the path from the start node to the current node.
 If the heuristic function used in Greedy Best-First Search is good to estimate (how close a current node to
the solution/goal) this algorithm can be a very efficient and find a solution quickly, even in large search
spaces.
Disadvantages
 GBFS does not guarantee an optimal solution. Since it only considers heuristic information to guide the
search, it may choose paths that seem promising based on the heuristic but end up being suboptimal in
terms of total cost.
 Greedy Best-First Search requires a heuristic function in order to work, which adds complexity to the
algorithm.

2.3.2 A* Search

A* search algorithm that is used to find the shortest path between an initial and a final point. It combines
the benefits of UCS with an admissible heuristic to guide the search.

It searches for shorter paths first, thus making it an optimal and complete algorithm. An optimal
algorithm will find the least cost outcome for a problem, while a complete algorithm finds all the possible
outcomes of a problem.

A* is powerful in weighted graphs and its implementation. A weighted graph uses numbers to represent
the cost of each path or course of action. This means that the algorithms can take the path with the least cost,
and find the best route in terms of distance and time.

In A* search algorithm, we use search heuristic as well as the cost to reach the node. Hence we can
combine both costs as following, and this sum is called as a fitness number.

f(n)=g(n) +h(n)
where
n current node
f(n)  The actual cost of traversal
g(n)  estimated cost from node n to the immediate node
h(n) heuristic function value associated with current node

EXAMPLE
Consider the example below, here we will traverse the given graph using the A* algorithm. The heuristic value of
all states is given in the below table so we will calculate the f(n) of each state using the formula f(n)= g(n) + h(n),
where g(n) is the cost associated with that node.

node h(n)
S 5
A 3
B 4
C 2
D 9
E 7
G 7
So, SG path can be obtained by SACG with the total cost of 16. (4+3+9)

Advantages
 A* is complete, it will always find a solution if one exists
 It is guaranteed to find the shortest path from the start node to the goal node.

Disadvantages

 Highly depends on heuristic function quality

 A* algorithm maintains lists of nodes, which can consume a significant amount of memory, especially in
large search spaces. Additionally, storing the entire search tree may not be feasible for memory-intensive
applications.
 It is not suitable for negative edge costs

2.3.3 AO* Search

The AO* algorithm, short for "Anytime Optimistic" algorithm, is a search algorithm used in artificial
intelligence and computer science to find the optimal path or solution in a graph or state space. It is an extension
of the A* algorithm that allows for anytime computation. It is designed to find approximate solutions quickly and
improve the solution incrementally as more time becomes available.

The AO* method first divides the given complex problem into a smaller group of problems. Then resolve
these smaller problems using the AND-OR graph concept.

The nodes of the graph represent states or goals, and the successors are labeled as either AND or OR
branches. The AND successors are sub goals that must all be achieved to satisfy the parent goal, while the OR
branches indicate alternative sub goals, any one of which could satisfy the parent goal.
 In the above figure, eating food may be broken down into smaller problems or tasks such as
i) Order food through online or
ii) Prepare a food and have it

which is an example of a simple AND-OR graph. Here the goal eating food can be achieved by either first choice
or second choice. The first choice is to order the food through online. The second choice is, prepare a food and
have it, consists of two sub problems should be accomplished together.
The AND symbol is used to indicate the AND part of the graphs, which refers to the need that all sub
problems containing the AND to be resolved before the preceding node.

The start state and the target state are already known in the knowledge-based search strategy known as
the AO* algorithm, and the best path is identified by heuristics. The informed search technique considerably
reduces the algorithm’s time complexity. The AO* algorithm is far more effective in searching AND-OR trees than
the A* algorithm. The evaluation function in AO* is similar to A* as follows,

f(n)=g(n) +h(n)
where
n current node
f(n)  The actual cost of traversal
g(n)  estimated cost from node n to the immediate node
h(n) heuristic function value associated with current node

Advantages of AO*
 It is an optimal algorithm, if traverse according to the ordering of nodes.
 It can be used for both OR and AND graph.

Disadvantages of AO*
 Sometimes for unsolvable nodes, it can’t find the optimal path.
 It is more complex than other algorithms.

Difference between A* search and AO* search

A* AO*
It uses Greedy best first search strategy It uses Greedy best first search strategy
Always gives optimal solution Does not guarantee to give the optimal
solution
It uses more memory compared to AO* It uses less memory
It represents an OR graph algorithm that is It represents an AND-OR graph algorithm
used to find a single solution (either this or that
that). is used to find more than one solution by
ANDing more than one branch.
It is a computer algorithm which is used in In this algorithm you follow a similar
path-finding and graph traversal. It is used procedure but there are constraints
in the process of plotting an efficiently traversing specific paths.
directed path between a number of points
called nodes.
2.4 Heuristic Functions

A heuristic function in artificial intelligence, also known as a heuristic or simply a heuristic, is an

evaluation function used to estimate the cost or potential of reaching a goal state from a given state in a problem-
solving domain.
Heuristic functions, also known as heuristics, play a critical role in guiding search algorithms by providing
an estimate of the cost or desirability of reaching a goal from a given state.
Heuristics are approximate strategies that guide the search for a solution. They provide a way to assess
the desirability of different options without exhaustively exploring every possibility.
These functions help search algorithms make informed decisions about which paths to explore, allowing for more
efficient and focused exploration of the solution space.

2.4.1 Heuristic values calculation

The heuristic value, often denoted as h(n), is an estimate of the cost from a given node n to the goal node
in a search problem. It is used in informed search algorithms like A* and AO* to guide the search towards the goal
efficiently. The heuristic function is problem-specific and should be admissible (never overestimates the true cost)
for A* to guarantee finding the optimal solution.

Here are a few examples of heuristic values for different types of problems.
Euclidean Distance (Straight-Line Distance)
If we are working with a pathfinding problem on a 2D grid where movement is unrestricted (can move in
any direction), we might use the Euclidean distance between the current node and the goal node as the heuristic.
For two points (x1,y1) and (x2,y2), the Euclidean distance is calculated as

Manhattan Distance

In a grid-based pathfinding problem where movement is restricted to four directions (up, down, left,
right), we can use the Manhattan distance as the heuristic. It is the sum of the absolute differences in the x and y
coordinates. For two points (x1,y1) and (x2,y2), the Manhattan distance is calculated as

Diagonal Distance
In grid-based pathfinding where diagonal movement is allowed, we can use the diagonal distance
heuristic, which is the maximum of the absolute differences in x and y coordinates. For two points (x1,y1) and
(x2,y2), the diagonal distance is calculated as

Traveling Salesman Problem (TSP)

In TSP, we are trying to find the shortest route that visits each city exactly once and returns to the origin
city, a heuristic could be the minimum spanning tree (MST) distance. We calculate the MST for the remaining
unvisited cities and sum up their distances. Other heuristics for TSP include nearest neighbor or minimum
insertion methods.
Rubik's Cube
For solving Rubik's Cube, a heuristic could be the number of misplaced cubes (often called the "hamming
distance") or the number of moves needed to solve a certain subset of the cube (e.g., a layer or a face).