AI Notes
HubAI vs Machine Learning vs Deep LearningApplications of Artificial IntelligenceFuture of Artificial IntelligenceHistory of Artificial IntelligenceTypes of Artificial IntelligenceWhat is Artificial Intelligence?Agent-Environment InteractionAI Search Overview: Strategies and ApplicationsIntelligent Agents in AIKnowledge Representation in AIProblem-Solving in AI: Search and PlanningRational Agents: Decision-Making under UncertaintyState-Space RepresentationA* Search Algorithm - Complete AI GuideBreadth-First Search (BFS) - AI Algorithm GuideDepth-First Search (DFS) - Complete BTech GuideGreedy Best-First Search - Heuristic AI AlgorithmInformed Search Strategies - AI AlgorithmsIterative Deepening Search (IDS) - AI AlgorithmSearch Algorithms Comparison - AI TechniquesUniform Cost Search (UCS) - AI Weighted Graph AlgorithmUninformed Search Strategies - AI FundamentalsFrames - Structured Knowledge ObjectsKnowledge Bases - Structured KnowledgeOntologies - Semantic KnowledgePredicate Logic - First-Order LogicPropositional Logic - Logical ReasoningReasoning Systems - Inference EnginesSemantic Networks - Knowledge RepresentationExpert Systems ComponentsExpert Systems ApplicationsExpert Systems - Knowledge-Based AIFuzzy Logic - Approximate ReasoningInference Engine - Reasoning CoreRule-Based Systems - ProductionClassification Algorithms - Complete AI GuideClustering Algorithms - Complete AI GuideMachine Learning Fundamentals - Complete AI GuideModel Evaluation - Complete AI GuideRegression Algorithms - Complete AI GuideReinforcement Learning BasicsSupervised Learning - Complete AI GuideUnsupervised Learning - Complete AI GuideActivation Functions - Non-linearity in NetworksArtificial Neural Networks (ANN) - Complete BTech GuideBackpropagation - Learning Algorithm for NetworksForward Propagation - Inference in NetworksGradient Descent - Optimization FundamentalsNeural Network Training - Complete ProcessPerceptron Learning Algorithm - AI FundamentalsBERT - Bidirectional Encoder RepresentationsConvolutional Neural Networks (CNN) - Complete AI GuideDeep Learning Fundamentals - Complete GuideGenerative AI - Complete TutorialGPT Models - Generative Pre-trained TransformersLSTM Networks - Advanced Sequence ModelingRecurrent Neural Networks (RNN) - Sequence AI ModelsTransformers - Revolutionary Attention ArchitectureConversational AI - ChatbotsMachine Translation - Neural MTNER - Information ExtractionNLP Fundamentals - Complete GuideSentiment Analysis - Opinion MiningStemming & Lemmatization - NormalizationText Preprocessing - Cleaning & PreparationTokenization - Text ProcessingComputer Vision - Complete AI GuideCV Projects - Complete AI GuideFacial Recognition - Complete AI GuideImage Classification with Deep Learning - CNN GuideImage Processing - Complete AI GuideImage Segmentation - Complete AI GuideObject Detection - Complete AI GuideOpenCV Basics - Complete AI GuideActor-Critic Methods - Hybrid RLDeep Q-Networks - DQNMDP - RL FoundationPolicy Gradient Methods — Artificial IntelligenceQ-Learning - Value-Based RLReinforcement Learning Fundamentals — Artificial IntelligenceRL Projects - Game AI to RoboticsAI in Robotics - Intelligent AutomationAutonomous Systems - Self-Directed RobotsPath Planning - Robot NavigationRobot Navigation - Autonomous MovementRobot Perception - Sensing & VisionRobotic Applications - Real-World UseRobotics FundamentalsAI Agent ProjectBuild AI ChatbotFace Recognition System — Artificial IntelligencePersonal LLM AssistantRecommendation System — Artificial IntelligenceSentiment Analysis Project — Artificial IntelligenceSmart Home AI AssistantVoice Assistant ProjectAI Interview CheatsheetAI Interview QuestionsDeep Learning Interview Questions — Artificial IntelligenceLLM & RAG Interview QuestionsML Interview QuestionsAI Glossary - Terms & DefinitionsDatasets for PracticeImportant AI FormulasRecommended Books & CoursesEssential AI Research PapersAgentic AI ProjectsAI Agents: Architecture and ImplementationAutonomous Agents: Self-Governing SystemsLarge Language Models: Transformers at ScaleMulti-Agent Systems: Coordination and CooperationPrompt Engineering: Optimizing LLM InteractionsRAG: Retrieval-Augmented GenerationTool Calling: Extending LLMs with APIsAI Ethics: Principles and Responsible DevelopmentAI Privacy: Data Protection and ConfidentialityAI Regulations: Compliance and Legal FrameworksAI Security: Adversarial Robustness and DefenseBias in AI: Detection and MitigationExplainable AI: Interpretability and TransparencyResponsible AI: Building Trustworthy SystemsKerasLangchain BasicsNumpyPandasPython for AI Development - Complete Programming GuidePyTorch Framework - Complete AI GuideScikit - Complete AI GuideTensorFlow Framework - Complete AI GuideBackward Chaining - Goal-Driven ReasoningBayesian Networks - ProbabilisticForward Chaining - InferenceLogical Reasoning - InferenceResolution Method - Logical InferenceTheorem Proving - Automated ReasoningUncertain Reasoning - Probabilistic AI
Compare BFS, DFS, UCS, A*, and search algorithms. Learn when to use each algorithm, complexity analysis, practical applications in AI systems.
Introduction
Search algorithms are fundamental to artificial intelligence. They provide the mechanisms by which an AI agent explores possible states, plans actions, and finds solutions to problems. Choosing the right search algorithm for a given problem can mean the difference between finding an optimal solution in milliseconds and waiting hours for a suboptimal answer. This guide compares the major search algorithms across multiple dimensions to help you understand when to use each one.
Classification of Search Algorithms
Search Algorithms
├── Uninformed (Blind) Search
│ ├── Breadth-First Search (BFS)
│ ├── Depth-First Search (DFS)
│ ├── Uniform Cost Search (UCS)
│ ├── Depth-Limited Search (DLS)
│ └── Iterative Deepening DFS (IDDFS)
│
└── Informed (Heuristic) Search
├── Greedy Best-First Search
├── A* Search
├── IDA* (Iterative Deepening A*)
└── Hill Climbing (Local Search)
Comprehensive Comparison Table
| Algorithm | Complete? | Optimal? | Time | Space | Uses Heuristic? |
|---|---|---|---|---|---|
| BFS | Yes (finite) | Yes (unit cost) | O(b^d) | O(b^d) | No |
| DFS | No (infinite) | No | O(b^m) | O(bm) | No |
| UCS | Yes | Yes | O(b^(1+⌊C*/ε⌋)) | O(b^(1+⌊C*/ε⌋)) | No |
| IDDFS | Yes | Yes (unit cost) | O(b^d) | O(bd) | No |
| Greedy | No | No | O(b^m) | O(b^m) | Yes |
| A* | Yes | Yes (admissible h) | O(b^d) | O(b^d) | Yes |
Where: b = branching factor, d = solution depth, m = max depth, C* = optimal cost, ε = minimum edge cost
Detailed Algorithm Characteristics
Breadth-First Search (BFS)
| Strategy | Explore all nodes at depth k before depth k+1 |
| Data structure | FIFO Queue |
| Best for | Shortest path in unweighted graphs |
| Weakness | Enormous memory usage for deep solutions |
| Example | Finding shortest route in a maze (all moves cost 1) |
| Nodes expanded | 1 + 2 + 4 + 8 = 15 (all levels up to solution) |
| Nodes in memory | ~8 (entire frontier at depth 3) |
Depth-First Search (DFS)
| Strategy | Explore deepest unexpanded node first |
| Data structure | LIFO Stack (or recursion) |
| Best for | Memory-constrained problems, existence questions |
| Weakness | Can get stuck in infinite branches, not optimal |
| Example | Solving a Sudoku puzzle (go deep, backtrack on failure) |
| But memory | only O(bd) = O(2×3) = O(6) nodes stored! |
Uniform Cost Search (UCS)
| Strategy | Expand cheapest-total-cost node first |
| Data structure | Priority Queue (min-heap by path cost) |
| Best for | Shortest path with varying edge costs |
| Weakness | Explores in all directions (no goal guidance) |
| Example | Finding cheapest flight route between cities |
| Start | {A: cost 0} |
| Expand A | {B: 3, C: 5, D: 7} |
| Expand B | {C: 5, E: 6, D: 7} |
| Expand C | {E: 6, D: 7, F: 8} |
Iterative Deepening DFS (IDDFS)
| Strategy | Repeated DFS with increasing depth limits |
| Combines | BFS completeness + DFS memory efficiency |
| DFS(limit=0) | Check only start node |
| DFS(limit=1) | Check depth 0 and 1 |
| DFS(limit=2) | Check depth 0, 1, and 2 |
| Total nodes | (d+1)×1 + d×b + (d-1)×b² + ... + 1×b^d |
| Dominated by last level | only ~11% overhead for b=10! |
Greedy Best-First Search
| Strategy | Expand node closest to goal (by heuristic) |
| Evaluation | f(n) = h(n) only |
| Best for | Quick approximate solutions |
| Weakness | Can be misled by heuristic, not optimal |
| Example | GPS suggesting "as the crow flies" direction |
A* Search
| Strategy | Expand node with lowest f(n) = g(n) + h(n) |
| Best for | Optimal pathfinding with available heuristic |
| Weakness | Memory grows exponentially |
| Requirement | h must be admissible (never overestimates) |
| Expand Arad | Sibiu(393), Timisoara(447), Zerind(449) |
| Expand Sibiu | f = 140 + 253 = 393 |
Worked Example: Comparing All Algorithms
Consider finding a path in this graph:
| Optimal path: A | C→D→E (cost = 2+1+2 = 5) |
| Alternative: A | B→E (cost = 1+4 = 5) — tie! |
| Non-optimal: A | B→D→E (cost = 1+3+2 = 6) |
| BFS: A | B,C → D,E,D → finds B→E first (depth 2) ✓ optimal (by luck) |
| DFS: A | B → E (finds A→B→E, cost 5) — happens to be optimal here |
| UCS: A(0) | B(1),C(2) → C(2),D(4),E(5) → D(3),E(5) → E(5) ✓ optimal guaranteed |
| Greedy (h=straight line to E): May go A | B→E directly if h(B)<h(C) |
| A* | f(B)=1+h(B), f(C)=2+h(C) — guaranteed optimal with admissible h |
When to Choose Which Algorithm
| YES | BFS (simple and optimal) |
| NO | continue |
| YES | A* (optimal + efficient with good heuristic) |
| NO | UCS (optimal without heuristic) |
| YES + need optimality | IDDFS or IDA* |
| YES + approximate OK | DFS or Greedy |
| YES | Hill Climbing, Simulated Annealing, Genetic Algorithm |
| YES | Minimax with Alpha-Beta Pruning |
Heuristic Quality and Its Impact
The quality of a heuristic dramatically affects A* performance:
| Manhattan distance | expands ~100 nodes for 8-puzzle |
| Misplaced tiles | expands ~1000 nodes for 8-puzzle |
| h=0 (UCS) | expands ~100,000 nodes for 8-puzzle |
Space-Time Tradeoffs
Example
Algorithm | Time Efficient | Space Efficient | Optimal
BFS | Moderate | Poor | Yes (unit cost)
DFS | Poor (may wander) | Excellent | No
IDDFS | Moderate | Excellent | Yes (unit cost)
UCS | Moderate | Poor | Yes
Greedy | Good (often) | Poor | No
A* | Excellent | Poor | Yes
IDA* | Excellent | Excellent | Yes
Summary
No single search algorithm is best for all problems. BFS and IDDFS offer completeness and optimality for uniform-cost problems with minimal heuristic knowledge. UCS handles variable costs optimally. A* combines cost information with heuristic guidance for the most efficient optimal search, but requires admissible heuristics and substantial memory. Understanding these tradeoffs allows you to select the right algorithm based on your problem's characteristics: graph structure, available heuristics, memory constraints, and optimality requirements.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Search Algorithms Comparison - AI Techniques.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, search, algorithms, comparison, search algorithms comparison - ai techniques
Related Artificial Intelligence Topics
Continue learning this concept
Search AlgorithmsA* Search Algorithm - Complete AI GuideMaster A* pathfinding algorithm for artificial intelligence. Learn heuristic functions, admissibility, optimality, implementation with code. Technical interview preparation 2024.Search AlgorithmsBreadth-First Search (BFS) - AI Algorithm GuideComplete BFS algorithm tutorial for artificial intelligence. Learn breadth-first search implementation, shortest path, complexity analysis, and interview preparation. Essential BTech notes on graph algorithms 2024.Search AlgorithmsDepth-First Search (DFS) - Complete BTech GuideMaster DFS algorithm for artificial intelligence. Learn depth-first search implementation, backtracking, complexity analysis, and interview preparation with code examples. AI search algorithms explained for BTech students 2024.Search AlgorithmsGreedy Best-First Search - Heuristic AI AlgorithmLearn Greedy Best-First Search for AI. Understand heuristic-based search, priority queues, implementation, advantages and limitations. Technical interview guide 2024.Search AlgorithmsInformed Search Strategies - AI AlgorithmsComplete tutorial on informed search strategies in artificial intelligence. Learn greedy search, best-first, A*, heuristic functions. BTech notes 2024.Search AlgorithmsIterative Deepening Search (IDS) - AI AlgorithmMaster Iterative Deepening Search (IDS) combining benefits of BFS and DFS. Learn depth-limited search, memory efficiency, implementation. Complete BTech guide 2024.