Solving Problems by Searching

Introduction to A* Search

The A (A-star) search algorithm* is one of the most powerful and widely used pathfinding algorithms in artificial intelligence and computer science. It is designed to find the shortest and most efficient path from a given starting point to a goal. A* combines elements of both Dijkstra’s Algorithm (which finds the shortest path) and Greedy Best-First Search (which uses heuristics to guide the search), making it both complete and optimal.

How Does A* Search Work?

A* Search evaluates paths using the following cost function: where:

• g(n): The cost from the start node to the current node n.
• h(n): The estimated cost from node n to the goal (heuristic function).
• f(n): The total estimated cost of the path through node n.

A* expands the most promising node (the one with the lowest f(n) value) and continues exploring until it reaches the goal.

Key Features of A* Search

• Optimality – Always finds the shortest path (if an admissible heuristic is used).
• Completeness – Guarantees a solution if one exists.
• Efficiency – Uses heuristics to guide the search, reducing unnecessary explorations.
• Combines Uniform-Cost and Heuristic Search – Balances cost calculations and goal estimation for better performance.

Understanding the Heuristic Function in A*

The effectiveness of A* largely depends on the choice of heuristic h(n). The heuristic should be:

• Admissible (Never overestimates the true cost to the goal).
• Consistent (The estimated cost should not exceed the actual step cost).

Common heuristics include:

• Manhattan Distance – Used for grid-based pathfinding.
• Euclidean Distance – Suitable for open spaces with diagonal movement.
• Chebyshev Distance – Used in cases where diagonal and straight moves have the same cost.

Step-by-Step Execution of A* Search

• Initialize the open list (priority queue) and add the start node.
• Select the node with the lowest f(n) value and expand it.
• Calculate the g(n), h(n), and f(n) values for neighboring nodes.
• Add neighbors to the open list (if they are not in the closed list or have a better path).
• Repeat until the goal node is reached.
• Reconstruct the path by tracing back from the goal to the start.

Example of A* Search

Consider a grid-based maze where A* is used to find the shortest path from Start (S) to Goal (G) while avoiding obstacles.

• White squares (□) represent valid paths.
• Black squares (■) represent obstacles.
• Arrows indicate the possible movement directions.

A* would navigate through the optimal path, avoiding obstacles while considering both actual cost (g) and estimated cost (h).

Advantages of A* Search

• Finds the shortest path efficiently in most cases.
• Flexible and can be customized with different heuristics.
• Optimized for real-world applications like game AI, robotics, and network routing.

Disadvantages of A* Search

• High memory usage – Stores all generated nodes, which can be inefficient for very large graphs.
• Performance depends on heuristics – Poor heuristic choice can slow down the search.
• Computationally expensive – More expensive than simpler algorithms like Greedy Best-First Search.

Applications of A* Search

• Video Game AI – NPC pathfinding in games like Pac-Man or Minecraft.
• Robotics – Used in autonomous navigation for robots.
• Navigation Systems – Google Maps and GPS routing applications.
• Network Optimization – Packet routing in computer networks.

Conclusion

A* Search is one of the most efficient and widely used pathfinding algorithms. By balancing actual path cost and heuristic estimates, it provides an optimal path while minimizing unnecessary exploration. Its real-world applications make it an indispensable tool in AI, robotics, and computer science.

Introduction to Breadth-First Search (BFS)

Breadth-First Search (BFS) is one of the most fundamental graph traversal and search algorithms. It is an uninformed search strategy that explores all possible paths level by level before moving deeper. BFS is widely used in AI, computer networks, robotics, and pathfinding applications due to its completeness and optimality in unweighted graphs.

How Does BFS Work?

BFS operates using a queue (FIFO – First In, First Out) data structure, ensuring that nodes are explored in order of their depth.

The BFS process follows these steps:

• Start with the root node (initial state) and add it to the queue.
• Dequeue the first node from the queue and explore its neighbors.
• Add all unvisited neighbors to the queue.
• Repeat steps 2 and 3 until the goal node is found or the queue is empty.
• Backtrack from the goal node to reconstruct the shortest path.

Key Characteristics of BFS

• Complete – BFS always finds a solution if one exists.
• Optimal (for unweighted graphs) – BFS finds the shortest path in terms of the number of edges.
• Time Complexity – O(V + E), where V = number of vertices, E = number of edges.
• Space Complexity – O(V), as it stores all nodes at the current level before moving to the next.

Example of BFS Execution

Consider the following graph where BFS is used to find the shortest path from Node A to Node G:

Step-by-Step BFS Traversal:

• Start at A → Enqueue [A]
• Visit A, enqueue its neighbors → [B, C]
• Visit B, enqueue its neighbors → [C, D, E]
• Visit C, enqueue its neighbors → [D, E, F]
• Visit D, no new nodes → [E, F]
• Visit E, enqueue G → [F, G]
• Visit F, no new nodes → [G]
• Visit G, goal reached!

Shortest path found: A → B → E → G

Advantages of BFS

• Finds the shortest path in unweighted graphs.
• Systematic search method, ensuring no path is missed.
• Guarantees completeness, meaning if a solution exists, BFS will find it.
• Ideal for discovering all possible solutions in a shallow-depth environment.

Disadvantages of BFS

• High memory consumption – BFS stores all nodes at each level.
• Inefficient in deep or infinite graphs, leading to exponential space complexity.
• Not suitable for weighted graphs, as it does not consider edge costs.

Applications of BFS

• Pathfinding in AI & Games – Used in maze solvers, NPC navigation, and game AI.
• Social Network Analysis – Finds connections between users (e.g., Facebook friend suggestions).
• Web Crawling – Used by search engines to index web pages.
• Network Routing – Identifies shortest paths in communication networks.
• Artificial Intelligence Planning – Helps in AI-based decision-making.

Comparison: BFS vs. Depth-First Search (DFS)

Feature	BFS	DFS
Data Structure	Queue (FIFO)	Stack (LIFO)
Completeness	Yes, always finds a solution	No, may go into infinite loops
Optimality	Yes (for unweighted graphs)	No, does not guarantee shortest path
Memory Usage	High (stores all nodes at a level)	Lower (stores path nodes only)

Conclusion

Breadth-First Search (BFS) is a systematic, complete, and optimal search algorithm for unweighted graphs. While it can be memory-intensive, it is widely used in AI, robotics, networking, and game development for its reliability in finding the shortest path. If you’re dealing with shallow searches or unweighted paths, BFS is one of the best algorithms to use!

Introduction to Depth-First Search (DFS)

Depth-First Search (DFS) is a fundamental graph traversal algorithm used for exploring graphs and trees. Unlike Breadth-First Search (BFS), which explores level by level, DFS goes as deep as possible along each branch before backtracking. DFS is widely used in AI, game development, puzzle solving, and network analysis due to its efficiency in deep searches.

How Does DFS Work?

DFS operates using a stack (LIFO – Last In, First Out) data structure, either explicitly (using a stack) or implicitly (using recursion).

Steps for DFS Traversal:

• Start with the root node (initial state) and push it onto the stack.
• Pop the top node from the stack and explore its neighbors.
• Push all unvisited neighbors onto the stack.
• Repeat steps 2 and 3 until the goal node is found or the stack is empty.
• Backtrack when necessary.

Key Characteristics of DFS

• Completeness – DFS is not always complete; it may get stuck in infinite loops in cyclic graphs.
• Optimality – DFS does not guarantee the shortest path.
• Time Complexity – O(V + E), where V = number of vertices, E = number of edges.
• Space Complexity – O(V) (recursive depth or stack storage).

Example of DFS Execution

Consider the following graph where DFS is used to explore from Node A:

Step-by-Step DFS Traversal:

• Start at A → Push [A]
• Visit A, push its neighbors → [B, C]
• Visit C, push its neighbors → [B, F]
• Visit F, push its neighbors → [B, G]
• Visit G, push its neighbors → [B] (Goal reached!)

Variations of DFS

Iterative Deepening DFS (IDDFS)

• Combines BFS and DFS by progressively deepening the search limit.
• Used in AI search problems like game trees and puzzles.
• Example: Chess AI searching optimal moves up to a depth limit.

Bidirectional DFS

• Runs two DFS searches simultaneously, one from the start and one from the goal.
• Efficient for large graphs where the start and goal are far apart.
• Example: Route optimization in Google Maps.

Randomized DFS

• Explores nodes in a random order instead of a fixed sequence.
• Used in maze generation algorithms.
• Example: Procedural content generation in video games.

Advantages of DFS

1. Efficient for deep searches.
2. Memory-efficient compared to BFS.
3. Useful in solving puzzles and mazes.
4. Works well in topological sorting and cycle detection.

Disadvantages of DFS

1. May get stuck in infinite loops in cyclic graphs.
2. Not optimal – it does not always find the shortest path.
3. Inefficient for very deep or infinite search spaces.

---

Lowest-Cost-First Search (Uniform-Cost Search – UCS)

Introduction to UCS

Lowest-Cost-First Search, also known as Uniform-Cost Search (UCS), is a search algorithm that expands the least-cost node first, rather than based on depth or order of discovery. It is used in pathfinding and AI search problems where costs vary.

How UCS Works:

• Initialize a priority queue with the start node (cost = 0).
• Expand the node with the lowest cost first.
• Update the cost of reaching neighboring nodes.
• Continue until the goal node is reached.

Key Characteristics of UCS

• Complete – Always finds a solution if one exists.
• Optimal – Guarantees the least-cost path.
• Time Complexity – O(V + E log V), where V = vertices, E = edges.
• Space Complexity – O(V), as it stores all expanded nodes.

Example of UCS Execution

Consider the following weighted graph:

UCS Traversal Steps:

• Start at A, enqueue [(A, 0)]
• Expand A, enqueue [(B,1), (C,4)]
• Expand B, enqueue [(D,3), (E,4)]
• Expand D, enqueue [(G,5)]
• Goal G reached at lowest cost 5.

Advantages of UCS

• Always finds the least-cost path.
• Ideal for weighted graphs.
• Guarantees completeness and optimality.

Disadvantages of UCS

• Can be slow in large graphs.
• Higher memory usage than DFS.
• Not ideal for unweighted graphs (BFS is better in such cases).

Conclusion

DFS is a powerful search technique for deep exploration, while UCS is optimal for cost-based pathfinding. By understanding their differences and use cases, AI developers can select the best search strategy for graph traversal, pathfinding, and problem-solving in AI and computer science.

Introduction to Genetic Algorithms

Genetic Algorithms (GA) are optimization techniques inspired by the principles of natural selection and evolution. They are widely used in AI, machine learning, robotics, and optimization problems, where finding the best solution among multiple possibilities is essential.

Genetic Algorithms work by simulating the process of evolution, where candidate solutions undergo selection, crossover, and mutation to evolve toward an optimal solution.

How Do Genetic Algorithms Work?

Genetic Algorithms follow a systematic approach based on biological evolution:

Initialization

• A population of candidate solutions (chromosomes) is generated randomly.
• Each chromosome represents a potential solution.

Fitness Function Evaluation

• Each chromosome is evaluated using a fitness function that determines how close it is to the optimal solution.
• Higher fitness scores indicate better solutions.

Selection

• The best-performing chromosomes (parents) are selected for reproduction.
• Selection methods include:
  • Roulette Wheel Selection – Probabilities based on fitness values.
  • Tournament Selection – A subset of chromosomes competes, and the best one is chosen.
  • Elitism – The top solutions automatically proceed to the next generation.

Crossover (Recombination)

• Two selected parent chromosomes exchange genetic material to create new offspring.
• Types of crossover:
  • Single-Point Crossover – One crossover point is chosen.
  • Multi-Point Crossover – Multiple crossover points are used.
  • Uniform Crossover – Random genes from both parents are combined.

Mutation

• Small random modifications are applied to offspring to maintain diversity.
• Example: Changing a bit in a binary chromosome from 0 to 1.

Replacement (Survivor Selection)

• The new generation replaces the previous population.
• The process continues until an optimal solution is found or a stopping condition is met.

Example of Genetic Algorithm in Action

Imagine using a Genetic Algorithm to solve a traveling salesman problem (TSP):

• Each chromosome represents a different city sequence.
• The fitness function calculates the total distance traveled.
• Selection chooses the shortest routes.
• Crossover swaps parts of two routes to create better paths.
• Mutation introduces small changes to explore new possibilities.
• The algorithm repeats until it finds the optimal shortest path.

Applications of Genetic Algorithms

• Machine Learning & AI – Optimizing neural networks and feature selection.
• Robotics – Evolving robotic movement strategies.
• Game Development – Generating NPC behavior dynamically.
• Finance – Portfolio optimization and algorithmic trading.
• Bioinformatics – DNA sequence analysis and drug discovery.

Advantages of Genetic Algorithms

• Efficient for complex optimization problems.
• Works well in large search spaces where brute force is impractical.
• Can handle non-linear problems that traditional methods struggle with.
• Parallel processing capability speeds up optimization.

Disadvantages of Genetic Algorithms

• Can be computationally expensive.
• Does not guarantee the absolute best solution.
• Requires fine-tuning of parameters (mutation rate, population size, etc.).

Conclusion

Genetic Algorithms are a powerful AI optimization technique inspired by evolution. By using selection, crossover, and mutation, GA continuously improves solutions to complex problems. They have wide applications in AI, machine learning, robotics, and optimization, making them an essential tool for researchers and engineers.

Introduction to Greedy Best-First Search

Greedy Best-First Search is a heuristic search algorithm that prioritizes expanding nodes that appear to be closest to the goal based on a given heuristic function. Unlike A Search*, which considers both the cost so far and estimated cost to the goal, Greedy Best-First Search focuses only on the heuristic value , making it a fast but sometimes suboptimal approach.

It is called “greedy” because it chooses the most promising option at each step, hoping to reach the goal quickly.

How Does Greedy Best-First Search Work?

Greedy Best-First Search evaluates nodes using the function: where:

• h(n): Heuristic estimate of the cost to reach the goal from node n.
• The algorithm always expands the node with the smallest h(n) value first.

Key Characteristics of Greedy Best-First Search

• Fast Execution – It quickly finds a path to the goal in many cases.
• Uses a Priority Queue (Min-Heap) – Stores nodes based on their heuristic values.
• Not Guaranteed to Be Optimal – May take suboptimal paths as it ignores past cost (g(n)).
• Complete for Finite Graphs – If a solution exists, it will find one.

Step-by-Step Execution of Greedy Best-First Search

• Start at the initial node and add it to a priority queue.
• Expand the node with the lowest heuristic value (h(n)).
• Add unvisited neighboring nodes to the queue.
• Repeat until the goal node is reached or no more nodes remain.
• Trace back the path from the goal to the start to get the final solution.

Example of Greedy Best-First Search

Consider a graph where we are searching from Node A to Node G:

Suppose the heuristic values (estimated distance to G) are:

A: 6, B: 4, C: 2, D: 5, E: 3, F: 1, G: 0

Steps of Execution:

• Start at A (h=6) → Expand C (h=2) since it has the lowest heuristic.
• Expand F (h=1).
• Expand G (h=0) (Goal reached!).

Advantages of Greedy Best-First Search

• Faster than other uninformed search algorithms.
• Uses less memory than A Search* since it only stores heuristic values.
• Efficient for problems where the heuristic is highly accurate.

Disadvantages of Greedy Best-First Search

• Not always optimal – May get stuck in loops or choose a longer path.
• Can be misled by heuristics – A poor heuristic leads to inefficient searching.
• Incomplete for infinite graphs – Can get trapped in an infinite loop.

Applications of Greedy Best-First Search

• Pathfinding in Video Games – Used for NPC movement in real-time strategy games.
• Robotics Navigation – Helps robots make quick decisions in obstacle avoidance.
• AI in GPS Systems – Used in shortest route estimations with good heuristics.
• Network Routing – Helps in packet routing across networks.

Comparison: Greedy Best-First Search vs. A* Search

Feature	Greedy Best-First Search	A* Search
Cost Function	Only heuristic h(n)	g(n) + h(n)
Optimality	No	Yes (if heuristic is admissible)
Completeness	Yes (for finite graphs)	Yes
Speed	Faster but riskier	Slower but more reliable

Conclusion

Greedy Best-First Search is a fast and effective search algorithm when a good heuristic is available. However, it is not always optimal and can be misled by incorrect heuristic estimates. It is widely used in AI, pathfinding, and optimization where speed is preferred over guaranteed optimal solutions.

Introduction to Hill-Climbing Search

Hill-Climbing Search is a heuristic search algorithm used for optimization problems where the goal is to find the best possible solution based on a given evaluation function. It operates similarly to climbing a hill, always moving in the direction of increasing value (better solutions) until it reaches a peak.

Hill-climbing is widely used in artificial intelligence, machine learning, robotics, and optimization tasks due to its simplicity and efficiency.

How Does Hill-Climbing Work?

Hill-Climbing follows these steps:

• Start with an initial state (randomly chosen or predefined).
• Evaluate the current state using a heuristic function.
• Generate neighboring states and compare their heuristic values.
• Move to the neighbor with the best heuristic value.
• Repeat until no better neighbors exist (i.e., a local maximum is reached).

Key Characteristics of Hill-Climbing Search

• Greedy Algorithm – Only moves to better states, ignoring previous paths.
• Heuristic-Based – Uses a heuristic function to evaluate states.
• Fast and Memory Efficient – Only stores the current state and its neighbors.
• Prone to Local Maxima – May get stuck at suboptimal solutions.

Example of Hill-Climbing Search

Imagine trying to climb a mountain where you can only see your immediate surroundings. If you always move uphill, you might reach a peak but not necessarily the highest peak.

Problem: If you reach a lower peak, you might think it’s the highest point, leading to suboptimal solutions.

Problems with Basic Hill-Climbing

• Local Maxima – The algorithm may get stuck at a suboptimal peak.
• Plateau – A flat region where all neighboring states have the same value.
• Ridges – Narrow paths where small moves don’t improve the solution.

Variations of Hill-Climbing to Overcome Limitations

Several variations of Hill-Climbing help resolve these issues:

Steepest-Ascent Hill-Climbing

• Evaluates all neighbors and chooses the one with the highest value.
• Advantage: More informed decision-making.
• Disadvantage: Computationally expensive for large state spaces.

Stochastic Hill-Climbing

• Selects a random neighbor with a probability proportional to its value.
• Advantage: Helps escape local maxima.
• Disadvantage: Can take longer to converge.

First-Choice Hill-Climbing

• Randomly selects a neighboring state and moves if it’s better.
• Advantage: Faster than evaluating all neighbors.
• Disadvantage: Can miss the best solution.

Simulated Annealing

• Allows downward moves with a probability that decreases over time.
• Advantage: Escapes local maxima by sometimes accepting worse solutions.
• Disadvantage: Requires tuning of the temperature schedule.

Genetic Algorithms (GA)

• Uses mutation and crossover to explore multiple paths simultaneously.
• Advantage: Finds global optima better than hill-climbing alone.
• Disadvantage: Computationally expensive.

Applications of Hill-Climbing Search

• Machine Learning – Optimizing hyperparameters in neural networks.
• Robotics – Fine-tuning robotic movement strategies.
• Game AI – Enhancing decision-making strategies in games.
• Scheduling Problems – Optimizing job scheduling in manufacturing.

Comparison: Hill-Climbing vs. Other Search Methods

Feature	Hill-Climbing	Simulated Annealing	Genetic Algorithm
Heuristic-Based	Yes	Yes	Yes
Handles Local Maxima	No	Yes	Yes
Optimality Guarantee	No	No	No (but better than HC)
Efficiency	High	Medium	Low

Conclusion

Hill-Climbing Search is a powerful but simple optimization technique used in AI. While it is fast and memory-efficient, it can get stuck in local maxima. Variations like Simulated Annealing and Genetic Algorithms help overcome these limitations by introducing randomness and broader search strategies.

Introduction to Local Search Algorithms

Local search algorithms are optimization techniques that aim to find optimal or near-optimal solutions by iteratively improving an initial candidate solution. Unlike global search methods, local search focuses only on neighboring solutions, making it efficient for large or complex problems.

Local search is widely used in artificial intelligence, operations research, robotics, and optimization problems where exploring all possibilities is computationally expensive.

How Do Local Search Algorithms Work?

• Start with an initial solution (randomly selected or predefined).
• Evaluate its quality using an objective function (cost function or heuristic evaluation).
• Generate neighboring solutions by making small modifications.
• Move to the best neighboring solution based on a selection criterion.
• Repeat until a stopping condition is met (e.g., no better solutions are found).

Key Characteristics of Local Search Algorithms

• Memory Efficient – Only a few states are stored at a time.
• Doesn’t Require Full Path Exploration – Works well in large, complex spaces.
• Can Get Stuck in Local Optima – May not always find the best global solution.
• Works Best for Optimization Problems – Applied in AI, scheduling, and logistics.

Common Local Search Algorithms

Hill-Climbing Algorithm

• Moves in the direction of the steepest ascent to improve the solution.
• Limitation: Can get stuck in local maxima, plateaus, or ridges.

Simulated Annealing

• Introduces randomness by sometimes accepting worse solutions.
• Uses a “temperature” parameter to gradually reduce randomness.
• Advantage: Escapes local maxima and finds better solutions.

Tabu Search

• Maintains a list of previously visited solutions to avoid cycles.
• Helps escape local optima by preventing immediate backtracking.
• Used in: Scheduling, vehicle routing, and logistics.

Genetic Algorithms

• Mimics natural selection using crossover, mutation, and selection.
• Advantage: Finds globally optimal solutions over multiple generations.
• Used in: AI optimization, machine learning, and game AI.

Beam Search

• Expands multiple candidates simultaneously instead of one.
• Uses heuristics to guide the search while keeping memory usage low.
• Common in: Speech recognition and machine translation.

Optimization Problems Solved by Local Search

• Pathfinding Problems – Finding the shortest route in navigation.
• Scheduling Problems – Optimizing employee work schedules or exam timetables.
• Logistics and Transportation – Optimizing delivery routes and supply chain processes.
• Game AI – Enhancing decision-making for non-player characters (NPCs).
• Neural Network Training – Tuning hyperparameters for deep learning models.

Advantages of Local Search Algorithms

• Scalable for large problems – Works well in high-dimensional spaces.
• Faster than exhaustive search methods – Efficient in optimization scenarios.
• Can be applied to real-world problems – Used in AI, business, and engineering.

Disadvantages of Local Search Algorithms

• May not find the global optimum – Can get stuck in local maxima.
• Performance depends on heuristic quality – Poor heuristics lead to bad solutions.
• Doesn’t guarantee completeness – Might fail to find a solution if poorly initialized.

Conclusion

Local search algorithms are powerful optimization techniques used in AI and real-world decision-making. While they are efficient and scalable, they require strategies to escape local optima, such as Simulated Annealing, Tabu Search, and Genetic Algorithms. Understanding their strengths and weaknesses helps in choosing the best algorithm for optimization problems.

Introduction to Problem-Solving Agents

A problem-solving agent is an intelligent system that identifies a goal, formulates a plan, and executes actions to achieve the goal. These agents are widely used in Artificial Intelligence (AI) to perform automated reasoning, decision-making, and problem-solving tasks.

Problem-solving agents operate in well-defined environments where they can take actions, observe changes, and reach an optimal solution.

How Do Problem-Solving Agents Work?

A problem-solving agent follows these steps:

• Problem Formulation – Defines the problem, including the start state and goal state.
• Search for Solutions – Explores possible paths to reach the goal.
• Execute Actions – Takes steps based on the chosen solution.
• Evaluate and Optimize – Ensures the best possible outcome.

Characteristics of Problem-Solving Agents

• Goal-Oriented – Focuses on achieving a specific target.
• Systematic Search – Uses algorithms to explore different possibilities.
• Autonomous Decision-Making – Takes actions without human intervention.
• Optimized for Efficiency – Finds the best or most efficient solution.

Example Problems Solved by AI Agents

AI problem-solving agents are used in various domains. Here are some classic examples:

Pathfinding Problem (e.g., GPS Navigation)

• Objective: Find the shortest route between two locations.
• Solution: Uses search algorithms like A or Dijkstra’s Algorithm*.

8-Puzzle Problem

• Objective: Arrange tiles in a 3×3 grid to match the goal state.
• Solution: Uses Uninformed Search (BFS, DFS) or *Heuristic Search (A)**.

Chess AI

• Objective: Determine the best possible move in a chess game.
• Solution: Uses Minimax Algorithm and Alpha-Beta Pruning.

Robot Navigation

• Objective: Guide a robot from start to destination while avoiding obstacles.
• Solution: Uses Pathfinding and Reinforcement Learning.

Scheduling Problem (e.g., Exam Timetable Scheduling)

• Objective: Assign time slots for exams while minimizing conflicts.
• Solution: Uses Genetic Algorithms or Constraint Satisfaction.

Searching for Solutions in AI

To solve problems efficiently, AI agents use different search strategies:

Uninformed (Blind) Search Strategies

• Breadth-First Search (BFS) – Explores level by level; guarantees the shortest path.
• Depth-First Search (DFS) – Explores deeply before backtracking; memory efficient.
• Uniform-Cost Search (UCS) – Expands the lowest-cost node first; optimal for weighted graphs.

Informed (Heuristic) Search Strategies

• Greedy Best-First Search – Expands the node closest to the goal based on a heuristic.
• A Search* – Combines UCS and heuristics for optimal and efficient pathfinding.
• Hill Climbing – Moves towards increasing heuristic values; used in optimization.

Local Search Strategies

• Simulated Annealing – Allows random downward moves to escape local optima.
• Genetic Algorithms – Uses evolution-based techniques for optimization.

Choosing the Right Search Algorithm

Problem Type	Best Search Algorithm
Finding the shortest path	A* Search, Dijkstra’s Algorithm
Decision-making in games	Minimax with Alpha-Beta Pruning
Optimization Problems	Genetic Algorithms, Hill Climbing
Unstructured Search Space	BFS, DFS, Simulated Annealing

Conclusion

Problem-solving agents are at the core of AI, enabling intelligent decision-making in various applications. Searching for solutions using appropriate algorithms is crucial for achieving efficiency and accuracy. By choosing the right strategy—whether uninformed, informed, or local search—AI agents can solve complex problems effectively.

9. Introduction to Recursive Best-First Search (RBFS)

Recursive Best-First Search (RBFS) is an informed search algorithm designed to overcome the memory limitations of A* search. It is a recursive, depth-first approach that uses heuristics to guide the search while limiting memory usage.

RBFS is widely used in pathfinding, game AI, and problem-solving domains where storing all nodes (as done in A*) is impractical due to space constraints.

How Does RBFS Work?

1. Uses a depth-first approach but backtracks when necessary.
2. Stores only a limited number of nodes in memory, unlike A*.
3. Expands the best node first, like A*, but in a recursive manner.
4. Uses a threshold to determine whether to backtrack.
5. Backtracks when needed and replaces node values with better alternatives.

Key Characteristics of RBFS

1. Memory-Efficient – Uses space proportional to depth rather than storing all nodes.
2. Complete – Guarantees a solution if one exists.
3. Optimal – Finds the best path when using an admissible heuristic.
4. Adaptive – Adjusts search based on available resources.

Example of RBFS Execution

Consider a simple maze-solving problem where RBFS finds the shortest path from start to goal. It:

• Expands the most promising path based on heuristic cost.
• Backtracks if the path exceeds a threshold.
• Continues searching efficiently until the goal is reached.

Advantages of RBFS

1. Uses less memory than A*.
2. Performs better in deep search spaces.
3. Guarantees optimality with an admissible heuristic.

Disadvantages of RBFS

1. Can be slower than A* due to recursive backtracking.
2. May re-expand nodes multiple times, increasing computational cost.
3. Not always practical for large state spaces with complex branching.

Heuristic Functions in AI Search

What is a Heuristic Function?

A heuristic function (h(n)) is an estimate of the cost from a given node to the goal. Heuristics help AI make intelligent decisions faster by prioritizing promising paths.

Types of Heuristic Functions

1. Admissible Heuristics

• Never overestimates the actual cost to the goal.
• Example: Manhattan Distance for grid-based pathfinding.

2. Consistent (Monotonic) Heuristics

• The estimated cost is always less than or equal to the step cost + heuristic of the next node.
• Ensures optimality and efficiency in A* search.

Common Heuristics in AI

1. Manhattan Distance – Used in grid-based problems where diagonal moves are not allowed.
2. Euclidean Distance – Used when movement can occur in any direction.
3. Hamming Distance – Used in string matching and puzzle solving.
4. Misplaced Tile Heuristic – Used in 8-puzzle and tile-based games.
5. Straight-Line Distance (SLD) – Used in navigation problems (e.g., Google Maps).

Applications of Heuristic Functions

1. Pathfinding in GPS and Games – A* and Greedy Best-First Search use heuristics to find optimal routes.
2. Medical Diagnosis AI – Heuristics help AI suggest potential diseases based on symptoms.
3. Robotics Navigation – AI robots use heuristics to determine efficient movement paths.

Conclusion

RBFS is an efficient, memory-optimized search algorithm that balances depth-first exploration with heuristic-driven decision-making. Heuristic functions play a crucial role in AI search, enabling faster and smarter decision-making in pathfinding, game AI, and real-world problem-solvi