Search
• Artificial Intelligence and Rational Agents: AI is the field focused on
creating rational agents that act to achieve goals using algorithms,
particularly search algorithms, as a key underlying mechanism.
• Role of Search Algorithms: These algorithms help agents explore
possible scenarios to identify solutions, commonly seen in games that
require logical deduction or problem-solving.
• such as those encountered in single-player games like tile games,
Sudoku, and crosswords.
Components of a Search Problem
• State Space: The set of all possible states (configurations) that can be
produced by the agent. This is the "universe" of possibilities. In
games, it includes every valid board or grid layout.
Example in Sudoku:
Every possible 9x9 grid where numbers 1-9 appear in rows, columns,
and 3x3 subgrids without repetition (though invalid partial grids may be
explored during search)
• Start State: The start state is where the search begins—it's the initial
condition or configuration from which the agent starts exploring
solutions.
• Goal Test: A function that checks whether a given state is a goal state
(i.e., solves the problem). This determines when to stop searching.
• The goal test is a function used to determine whether the current
state is the desired goal state in the problem-solving process.
• Example in 8-puzzle: Check if the tiles are in sorted order (1-8 from
left-to-right, top-to-bottom) with the blank in the bottom-right.
• Solution
The solution to a search problem refers to a sequence of actions, also
called a plan, which transforms the start state into the goal state. This
sequence is developed using search algorithms.
Types of Search Algorithm
The diagram shows a classification of search algorithms used in
artificial intelligence, dividing them into two main types:
uninformed search and informed search.
• Types of Search Algorithms
• Uninformed Search: These algorithms do not use any domain-specific information and
include:
• Depth first search
• Breadth first search
• Uniform cost search
• Informed Search: These utilize additional information about the problem to guide the
search and include:
• Greedy search
• A* search
• Graph search
• This structure helps in choosing the appropriate search strategy based on the
problem's requirements and available information.
Properties of Search Algorithms
• Completeness: Determines whether the algorithm is guaranteed
to find a solution if one exists.
• Optimality: Checks if the algorithm always finds the best
(minimum cost or shortest) solution.
• Time Complexity: Measures how much time (in terms of number
of steps or nodes explored) the algorithm takes to find a solution.
• Space Complexity: Refers to the amount of memory the algorithm
requires during execution.
These properties help in selecting the most suitable algorithm for a
given problem by considering practical constraints such as resource
availability and the importance of finding an optimal solution.
Uninformed Search
• The text explains that uninformed search algorithms, also called blind
search algorithms, operate without extra information about the goal
state except what is given in the problem description.
Characteristics of Uninformed Search Algorithms
• No Additional Information: These algorithms only know how to traverse
the tree or graph and lack extra knowledge about which nodes might be
closer to the goal.
• Blind Technique: The approach is followed mechanically, regardless of
efficiency. The algorithm does not evaluate which path might be better
or cheaper.
• Multiple Plans Possible: There can be different paths to reach the goal,
DFS
Advantages
Breadth First Search (BFS)
Uniform Cost Search (UCS)
• Uniform Cost Search is a pathfinding algorithm that expands the least cost node first, ensuring
that the path to the goal node has the minimum cost
• Key Concepts of Uniform Cost Search
• Priority Queue: UCS uses a priority queue to store nodes. The node with the lowest cumulative
cost is expanded first. This ensures that the search explores the most promising paths first.
• Path Cost: The cost associated with reaching a particular node from the start node. UCS
calculates the cumulative cost from the start node to the current node and prioritizes nodes
with lower costs.
• Exploration: UCS explores nodes by expanding the least costly node first, continuing this
process until the goal node is reached. The path to the goal node is guaranteed to be the least
costly one.
• Termination: The algorithm terminates when the goal node is expanded, ensuring that the first
time the goal node is reached, the path is the optimal one.
Working Uniform Cost Search
• UCS operates under a simple principle: among all possible expansions, pick the path that
has the smallest total cost from the start node. This is implemented using a priority queue
to keep the partial paths in order, based on the total cost from the root node.
• Here’s the step-by-step process of how UCS works:
• Initialization: UCS starts with the root node. It is added to the priority queue with a
cumulative cost of zero since no steps have been taken yet.
• Node Expansion: The node with the lowest path cost is removed from the priority queue.
This node is then expanded, and its neighbors are explored.
• Exploring Neighbors: For each neighbor of the expanded node, the algorithm calculates
the total cost from the start node to the neighbor through the current node. If a neighbor
node is not in the priority queue, it is added to the queue with the calculated cost. If the
neighbor is already in the queue but a lower cost path to this neighbor is found, the cost is
updated in the queue.
• Goal Check: After expanding a node, the algorithm checks if it has reached the goal node.
If the goal is reached, the algorithm returns the total cost to reach this node and the path
taken.
• Repetition: This process repeats until the priority queue is empty or the goal is reached.
Applications of UCS
• Uniform Cost Search is widely applicable in various fields within AI:
• Pathfinding in Maps: Determining the shortest route between two
locations on a map, considering different costs for different paths.
• Network Routing: Finding the least-cost route in a communication or
data network.
• Puzzle Solving: Solving puzzles where each move has a cost
associated with it, such as the sliding tiles puzzle.
• Resource Allocation: Tasks that involve distributing resources
efficiently, where costs are associated with different allocation
strategies.
Advantages of Uniform Cost
Search
• Optimality: UCS is guaranteed to find the least cost path to the goal
state if the cost of each step exceeds zero.
• Completeness: This algorithm is complete; it will find a solution if one
exists.
Challenges with UCS
• Space Complexity: The main drawback of UCS is its space complexity.
The priority queue can grow significantly, especially if many nodes are
being expanded.
• Time Complexity: The time it takes to find the least cost path can be
considerable, especially if the state space is large.
Bidirectional Search
• 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
• 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
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.
Greedy Best-First Search
• 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.
• It prioritizes paths that appear to be the most promising, regardless of
whether or not they are actually the shortest path.
• 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.
• Advantage: Efficient at quickly finding a solution by following the most
promising paths.
• Limitation: Can get stuck in local optima; does not guarantee finding
the shortest (optimal) path.
• The algorithm works by using a heuristic function to determine which
path is the most promising.
• The heuristic function takes into account the cost of the current path
and the estimated cost of the remaining paths. If the cost of the
current path is lower than the estimated cost of the remaining paths,
then the current path is chosen.
• This process is repeated until the goal is reached.
How Greedy Best-First Search
Works?
• Greedy Best-First Search 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.
• The algorithm uses a heuristic function to determine which path is the
most promising.
• The heuristic function takes into account the cost of the current path
and the estimated cost of the remaining paths.
• If the cost of the current path is lower than the estimated cost of the
remaining paths, then the current path is chosen. This process is
repeated until the goal is reached.
Advantages of Greedy Best-First
Search:
• Simple and Easy to Implement: Greedy Best-First Search is a relatively
straightforward algorithm, making it easy to implement.
• Fast and Efficient: Greedy Best-First Search is a very fast algorithm,
making it ideal for applications where speed is essential.
• Low Memory Requirements: Greedy Best-First Search requires only a
small amount of memory, making it suitable for applications with limited
memory.
• Flexible: Greedy Best-First Search can be adapted to different types of
problems and can be easily extended to more complex problems.
• Efficiency: If the heuristic function used in Greedy Best-First Search is
good to estimate, how close a node is to the solution, this algorithm can
be a very efficient and find a solution quickly, even in large search
spaces.
Disadvantages of Greedy Best-
First Search:
• Inaccurate Results: Greedy Best-First Search is not always guaranteed
to find the optimal solution, as it is only concerned with finding the
most promising path.
• Local Optima: Greedy Best-First Search can get stuck in local optima,
meaning that the path chosen may not be the best possible path.
• Heuristic Function: Greedy Best-First Search requires a heuristic
function in order to work, which adds complexity to the algorithm.
• Lack of Completeness: Greedy Best-First Search is not a complete
algorithm, meaning it may not always find a solution if one is exists.
This can happen if the algorithm gets stuck in a cycle or if the search
space is a too much complex.
Applications
• Pathfinding: Greedy Best-First Search is used to find the shortest path between two points in
a graph. It is used in many applications such as video games, robotics, and navigation
systems.
• Machine Learning: Greedy Best-First Search can be used in machine learning algorithms to
find the most promising path through a search space.
• Optimization: Greedy Best-First Search can be used to optimize the parameters of a system
in order to achieve the desired result.
• Game AI: Greedy Best-First Search can be used in game AI to evaluate potential moves and
chose the best one.
• Navigation: Greedy Best-First Search can be use to navigate to find the shortest path
between two locations.
• Natural Language Processing: Greedy Best-First Search can be use in natural language
processing tasks such as language translation or speech recognisation to generate the most
likely sequence of words.
• Image Processing: Greedy Best-First Search can be use in image processing to segment
image into regions of interest.