Set your Publisher ID in src/config/ads.ts to display live ads.
Problem Formulation & Search Algorithms
Uninformed BFS/DFS vs Heuristic A* Search in State Spaces
In classical AI, problem-solving is modeled as navigating a state space graph from an initial state to a goal state using search strategies.
Uninformed vs Informed (Heuristic) Search
Uninformed (Blind) Search has no domain-specific knowledge about how close a given state is to the goal. Examples include Breadth-First Search (BFS, guarantees shortest path on unweighted graphs) and Depth-First Search (DFS, explores deeply first with lower memory footprint).
Informed (Heuristic) Search uses an evaluation function f(n) that estimates the cheapest cost from state n to the goal. The crown jewel of heuristic search is A* (A-Star).
The A* evaluation function is f(n) = g(n) + h(n), where g(n) is the exact cost from the start to node n, and h(n) is an admissible heuristic estimate of the remaining cost to the goal.
import heapq
def a_star_search(graph, start, goal, heuristic):
# Priority queue stores tuples: (estimated_total_cost, current_node, cost_so_far, path)
frontier = [(heuristic[start], start, 0, [start])]
visited = set()
while frontier:
f_cost, current, g_cost, path = heapq.heappop(frontier)
if current == goal:
return path, g_cost
if current in visited:
continue
visited.add(current)
for neighbor, edge_weight in graph.get(current, []):
if neighbor not in visited:
new_g = g_cost + edge_weight
new_f = new_g + heuristic.get(neighbor, 0)
heapq.heappush(frontier, (new_f, neighbor, new_g, path + [neighbor]))
return None, float('inf')For A* to guarantee the optimal path, the heuristic h(n) must be admissible—meaning it must never overestimate the true remaining distance to the goal.
Set your Publisher ID in src/config/ads.ts to display live ads.
Test Yourself With Exercise
In the A* search formula f(n) = g(n) + h(n), what does h(n) represent?