-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path02-search-algorithms.html
More file actions
104 lines (93 loc) · 5.76 KB
/
Copy path02-search-algorithms.html
File metadata and controls
104 lines (93 loc) · 5.76 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<link rel="stylesheet" href="shared.css">
<title>Search Algorithms Comparison | Mastering A*</title>
</head>
<body>
<header class="nav-bar">
<span>Mastering A*</span>
<nav>
<a href="index.html">Home</a>
<a href="demo.html">Visualizer</a>
</nav>
</header>
<main class="container">
<h1>Search Algorithms Comparison</h1>
<section>
<h2>Uninformed vs Informed Search</h2>
<h3>Uninformed Search (Blind Search)</h3>
<p>Algorithms that explore without knowledge of the goal location. Examples include Breadth-First Search (BFS) and Depth-First Search (DFS).</p>
<ul>
<li><strong>Breadth-First Search (BFS):</strong> Explores all neighbors at the current depth before moving to the next depth. Guarantees the shortest path in unweighted graphs but explores extensively in all directions.</li>
<li><strong>Depth-First Search (DFS):</strong> Explores as deep as possible along each branch before backtracking. Does not guarantee the shortest path and may get stuck in infinite loops on infinite graphs.</li>
</ul>
</section>
<section>
<h2>Deep Dive: Algorithmic Characteristics</h2>
<p>Choosing the right algorithm depends on the requirements: Do you need the absolute shortest path? Is memory a constraint?</p>
<h3>The Trade-off: BFS vs. DFS</h3>
<p>BFS uses significant memory to store all nodes at the current depth (frontier). In a grid with branching factor <em>b</em> and depth <em>d</em>, BFS stores <em>O(b^d)</em> nodes. This is often impractical for large maps.</p>
<p>DFS is memory efficient, storing only the current path and unexplored neighbors of nodes on that path <em>O(d)</em>. However, it may wander down an infinite path or return a path far from the shortest, making it unsuitable for most shortest-path problems.</p>
</section>
<section>
<h3>Informed Search (Heuristic Search)</h3>
<p>Algorithms that use domain knowledge (a heuristic) to guide the search towards the goal. Examples include Greedy Best-First Search, Dijkstra's Algorithm, and A*.</p>
<ul>
<li><strong>Greedy Best-First Search:</strong> Expands the node that appears closest to the goal based on the heuristic. Fast, but not optimal.</li>
<li><strong>Dijkstra's Algorithm:</strong> Explores nodes in order of their cost from the start node. Guarantees optimality but explores uniformly in all directions.</li>
</ul>
</section>
<section>
<h2>A* Algorithm: The Best of Both Worlds</h2>
<p>A* combines the cost-optimality of Dijkstra's algorithm with the goal-oriented focus of Greedy Best-First Search.</p>
<p>The core formula is:</p>
<p style="text-align: center; font-weight: bold;">f(n) = g(n) + h(n)</p>
<ul>
<li><strong>g(n):</strong> The actual cost from the start node to node <em>n</em>.</li>
<li><strong>h(n):</strong> The heuristic estimate from node <em>n</em> to the goal.</li>
<li><strong>f(n):</strong> The total estimated cost of the path through node <em>n</em>.</li>
</ul>
<p>A* is efficient because it prioritizes nodes with lower <em>f(n)</em>. If the heuristic <em>h(n)</em> is admissible (never overestimates the cost), A* is guaranteed to find the shortest path.</p>
</section>
<section>
<h2>Step-by-Step Visualization Example</h2>
<p>Consider a simple 3x3 grid. A* expands nodes based on the lowest f(n) value. Below is a conceptual state table during the search:</p>
<table border="1" style="width: 100%; border-collapse: collapse; margin-top: 1rem;">
<tr style="background: #f4f4f4;"><th>Step</th><th>Open Set</th><th>Closed Set</th><th>Focus (Lowest f)</th></tr>
<tr><td>1</td><td>{Start}</td><td>{}</td><td>Start</td></tr>
<tr><td>2</td><td>{N1, N2}</td><td>{Start}</td><td>N1</td></tr>
<tr><td>3</td><td>{N2, N3, N4}</td><td>{Start, N1}</td><td>N2</td></tr>
</table>
<p>The <em>Open Set</em> holds candidates for exploration, while the <em>Closed Set</em> contains nodes already evaluated. A* iteratively picks the best candidate from the Open Set until the goal is reached.</p>
</section>
<section>
<h2>Performance Comparison</h2>
<table border="1" style="width: 100%; border-collapse: collapse; margin-top: 1rem;">
<thead>
<tr style="background: #f4f4f4;">
<th>Algorithm</th>
<th>Optimal</th>
<th>Complete</th>
</tr>
</thead>
<tbody>
<tr><td>BFS</td><td>✓</td><td>✓</td></tr>
<tr><td>DFS</td><td>✗</td><td>✗</td></tr>
<tr><td>DFS</td><td>✗</td><td>✗</td></tr>
<tr><td>Greedy</td><td>✗</td><td>✗</td></tr>
<tr><td>Dijkstra</td><td>✓</td><td>✓</td></tr>
<tr><td>A*</td><td>✓</td><td>✓</td></tr>
</tbody>
</table>
</section>
<div class="nav-links">
<a href="03-heuristic-mathematics.html" class="next-button">Next Page →</a>
</div>
</main>
<footer class="container" style="text-align: center; margin-top: 2rem; font-size: 0.8rem; color: #777;">
<p>© 2026 Mastering A* Pathfinding Algorithm</p>
</footer>
</body>
</html>