Uninformed & Informed Search

Before running any search, you must formulate the problem. The state-space model is the standard framework used in AIMA (Russell & Norvig) and MIT 6.034:

• State: A representation of a configuration of the world. For the 8-puzzle, a state is the 3×3 grid arrangement. For route-finding, a state is the current city.
• Initial state: Where the agent starts.
• Actions (operators): A function ACTIONS(s) returning the set of actions available in state s.
• Transition model: RESULT(s, a) — the state reached by applying action a in state s.
• Goal test: A predicate IS-GOAL(s) — true if s is a solution.
• Path cost: A function assigning a numeric cost to a path. Typically the sum of step costs c(s, a, s').

The state space is the graph implicitly defined by all reachable states and the transitions between them. For a real map this graph is explicit; for the 8-puzzle it has 9!/2 ≈ 181,440 nodes. For chess it has ~10^44 nodes — far too large to enumerate, but the same framework applies.

Why formulation matters: Choosing the right state representation determines everything. A bad representation can make a solvable problem intractable or lead to redundant states. The rule is: include in the state exactly the information needed to determine which actions are legal and what they lead to — no more.

from dataclasses import dataclass, field
from typing import Any, List, Tuple, Optional

@dataclass
class Problem:
    initial_state: Any
    goal_state: Any  # or a callable for complex goals

    def actions(self, state) -> List[Any]:
        raise NotImplementedError

    def result(self, state, action) -> Any:
        raise NotImplementedError

    def is_goal(self, state) -> bool:
        return state == self.goal_state

    def step_cost(self, state, action, next_state) -> float:
        return 1.0  # uniform by default

# Example: Romania route-finding
class RomaniaProblem(Problem):
    GRAPH = {
        'Arad':    [('Zerind', 75), ('Sibiu', 140), ('Timisoara', 118)],
        'Zerind':  [('Arad', 75),   ('Oradea', 71)],
        'Sibiu':   [('Arad', 140),  ('Fagaras', 99), ('RimnicuVilcea', 80)],
        # ... (full Romania graph from AIMA)
    }
    def actions(self, state):
        return [city for city, _ in self.GRAPH.get(state, [])]
    def result(self, state, action):
        return action
    def step_cost(self, state, action, next_state):
        for city, cost in self.GRAPH[state]:
            if city == next_state:
                return cost
        return float('inf')

All search algorithms share the same skeleton. Understanding the skeleton first makes BFS, DFS, UCS, and A* feel like minor variations on a single theme rather than four unrelated algorithms.

A node in the search tree is not the same as a state. A node records:

• The state it corresponds to
• The parent node (to reconstruct the path)
• The action that generated it
• The path cost g(n) from the initial state
• The depth in the search tree

Note: the same state can appear in multiple nodes (when reached by different paths). This is why the distinction matters.

TREE-SEARCH keeps a frontier (also called the open list or fringe) — the set of nodes generated but not yet expanded. It never checks whether a state has been visited, so it can loop forever on graphs.

GRAPH-SEARCH adds an explored set (closed list) that remembers every state that has been expanded. Before expanding a node, it checks whether the state was already explored. This prevents re-expansion and guarantees that on a finite graph, the search terminates.

The choice of data structure for the frontier is what distinguishes the algorithms:

• Queue (FIFO) → BFS
• Stack (LIFO) → DFS
• Priority queue ordered by g(n) → Uniform-Cost Search
• Priority queue ordered by h(n) → Greedy Best-First
• Priority queue ordered by f(n) = g(n) + h(n) → A*

# Generic GRAPH-SEARCH skeleton (Python)
from collections import deque
import heapq

def graph_search(problem, frontier_type='bfs'):
    # Node: (path_cost, state, path)
    start = (0, problem.initial_state, [problem.initial_state])

    if frontier_type == 'bfs':
        frontier = deque([start])          # O(1) append/popleft
        pop_fn = lambda f: f.popleft()
        push_fn = lambda f, item: f.append(item)
    elif frontier_type == 'dfs':
        frontier = [start]                 # stack
        pop_fn = lambda f: f.pop()
        push_fn = lambda f, item: f.append(item)
    # (priority queue variants handled differently)

    explored = set()

    while frontier:
        cost, state, path = pop_fn(frontier)
        if problem.is_goal(state):
            return path
        if state in explored:
            continue
        explored.add(state)
        for action in problem.actions(state):
            child = problem.result(state, action)
            if child not in explored:
                new_cost = cost + problem.step_cost(state, action, child)
                push_fn(frontier, (new_cost, child, path + [child]))
    return None  # no solution

BFS expands nodes level by level — all depth-1 nodes before depth-2, all depth-2 before depth-3, and so on. The frontier is a FIFO queue.

Completeness: BFS is complete — if a solution exists, BFS will find it. On an infinite tree with a finite branching factor, BFS reaches every node at depth d before moving to depth d+1.

Optimality: BFS finds the shallowest goal node first. If all step costs are equal (say, 1), the shallowest is also the cheapest, so BFS is optimal in that case. If step costs differ, BFS is not guaranteed to find the lowest-cost path.

Complexity: Let b be the branching factor and d be the depth of the shallowest solution.

• Time: O(b^d) — BFS must generate all nodes up to depth d.
• Space: O(b^d) — the frontier holds all unexpanded nodes at the shallowest frontier level, which can be b^d nodes.

The memory problem: Space is BFS's Achilles heel. For b=10 and d=10, the frontier can hold 10^10 = 10 billion nodes. For b=35 (a typical branching factor in chess), even d=4 gives 1.5 million nodes. This is why BFS is rarely used on large problems.

Analogy: Imagine dropping a stone in still water. The ripples expand outward in concentric rings — every point at radius r is reached before any point at radius r+1. That is BFS.

from collections import deque

def bfs(problem):
    """Returns optimal path (fewest steps) or None."""
    if problem.is_goal(problem.initial_state):
        return [problem.initial_state]

    frontier = deque([(problem.initial_state, [problem.initial_state])])
    explored = set([problem.initial_state])

    while frontier:
        state, path = frontier.popleft()
        for action in problem.actions(state):
            child = problem.result(state, action)
            if problem.is_goal(child):
                return path + [child]   # found!
            if child not in explored:
                explored.add(child)
                frontier.append((child, path + [child]))
    return None

# Time: O(b^d)   Space: O(b^d)
# Complete: YES   Optimal: YES (uniform costs only)

DFS expands the deepest node in the frontier first. The frontier is a LIFO stack (or equivalently, DFS is implemented recursively using the call stack).

Completeness: DFS is not complete in general. On infinite-depth spaces or graphs with cycles, DFS can get lost down an infinite path and never return. GRAPH-SEARCH with an explored set prevents cycles, but DFS is still not complete if the state space has infinite depth.

Optimality: DFS is not optimal — it may find a deep solution when a shallower one exists.

Complexity:

• Time: O(b^m) where m is the maximum depth. This can be far worse than BFS if m >> d.
• Space: O(b·m) — this is DFS's great advantage. At any point, DFS only needs to store the nodes on the current path (depth m) plus the unexpanded siblings at each level (at most b per level). This is linear in the depth.

When is DFS useful?: When memory is tight and you just need a solution (not the optimal one). DFS is the basis for backtracking search in constraint satisfaction.

Depth-Limited Search (DLS): To prevent DFS from diving infinitely deep, impose a depth limit l. DLS returns failure if no solution within depth l, and cutoff if a solution may exist deeper. This is still incomplete (unless l is large enough), but it is finite.

Key insight: DFS trades time for space compared to BFS. It can use exponentially less memory, but it may also waste exponentially more time exploring useless deep branches.

def dfs_recursive(problem, state, path, explored):
    """Recursive DFS. Not complete on infinite graphs."""
    if problem.is_goal(state):
        return path
    explored.add(state)
    for action in problem.actions(state):
        child = problem.result(state, action)
        if child not in explored:
            result = dfs_recursive(problem, child, path + [child], explored)
            if result is not None:
                return result
    return None

def depth_limited_search(problem, limit):
    """DFS with a depth cutoff. Returns path or None."""
    def dls(state, path, depth):
        if problem.is_goal(state):
            return path
        if depth == 0:
            return 'cutoff'
        cutoff_occurred = False
        for action in problem.actions(state):
            child = problem.result(state, action)
            if child not in set(path):  # avoid cycles on this path
                result = dls(child, path + [child], depth - 1)
                if result == 'cutoff':
                    cutoff_occurred = True
                elif result is not None:
                    return result
        return 'cutoff' if cutoff_occurred else None

    return dls(problem.initial_state, [problem.initial_state], limit)

# Space: O(b*m)   Complete: NO (infinite spaces)   Optimal: NO

Iterative Deepening Depth-First Search (IDDFS) is one of the most elegant results in search theory. It answers the question: can we get BFS's completeness and optimality with DFS's memory usage?

The idea is simple: run DLS with limit 0, then limit 1, then limit 2, ... until a solution is found or the space is exhausted. Each iteration is a complete DFS from the root.

Does re-expanding nodes waste too much work? Intuition says yes, but the analysis says no. In a tree with branching factor b, the shallowest level dominates. The number of nodes at depth d is b^d. All previous levels together contribute only b^(d-1) + b^(d-2) + ... + 1 = O(b^d). The overhead ratio is b/(b-1) — for b=10, that's just 11% extra work.

Properties of IDDFS:

• Complete: Yes (like BFS)
• Optimal: Yes for uniform costs (finds shallowest goal first)
• Time: O(b^d) — same asymptotic as BFS
• Space: O(b·d) — same as DFS! This is the miracle.

IDDFS is the preferred uninformed search algorithm when the search depth is unknown and memory is a concern. It is used in practice in chess engines (iterative deepening alpha-beta) and IDA* (the heuristic variant).

def iddfs(problem):
    """Iterative Deepening DFS.
    Complete + Optimal (uniform costs) + Space O(b*d)."""
    depth = 0
    while True:
        result = depth_limited_search(problem, depth)
        if result != 'cutoff' and result is not None:
            return result   # found a solution
        if result is None:
            return None     # exhausted entire space, no solution
        depth += 1          # try one level deeper

# The repeated work analysis:
# Nodes generated at depth d in IDDFS:
#   N = d*b^0 + (d-1)*b^1 + ... + 1*b^(d-1) + b^d
# ≈ b^d * (b / (b-1))   -- so overhead factor is b/(b-1)
# For b=10: overhead = 1.11 (11%). Totally worth the memory savings!

BFS finds the shallowest goal, but what if edges have different costs? UCS (also called Dijkstra's algorithm in the graph-algorithms literature) is the uninformed algorithm that finds the minimum-cost path.

UCS orders the frontier by path cost g(n) — the total cost from the initial state to node n. It uses a min-priority queue. At every step, it expands the node with the lowest accumulated path cost.

Optimality proof (the key invariant): When UCS expands a node n, the path to n recorded in g(n) is the optimal path. Why? Because UCS always expands the cheapest unexpanded node. If there were a cheaper path to n, that path would have been explored first (its cost would be lower, so it would have a higher priority). This argument requires that step costs are non-negative — a crucial assumption.

Completeness: UCS is complete provided the step costs are ≥ ε > 0 for some positive constant ε. If step costs can be zero, UCS might loop forever.

Complexity: Let C* be the cost of the optimal solution and ε be the smallest step cost. UCS explores all nodes with cost < C*, so:

• Time/Space: O(b^(1 + floor(C*/ε))) — potentially much worse than BFS if costs vary greatly.

Connection to Dijkstra's: UCS and Dijkstra's algorithm are essentially the same. The difference is presentation: Dijkstra's finds shortest paths to all nodes; UCS stops as soon as the goal is reached.

import heapq

def uniform_cost_search(problem):
    """UCS: finds minimum-cost path. Optimal for non-negative costs."""
    # heap entries: (path_cost, counter, state, path)
    # counter breaks ties (avoids comparing states)
    counter = 0
    frontier = [(0, counter, problem.initial_state, [problem.initial_state])]
    explored = {}  # state -> best cost seen

    while frontier:
        cost, _, state, path = heapq.heappop(frontier)

        if problem.is_goal(state):
            return path, cost

        # If we already expanded this state with lower cost, skip
        if state in explored and explored[state] <= cost:
            continue
        explored[state] = cost

        for action in problem.actions(state):
            child = problem.result(state, action)
            new_cost = cost + problem.step_cost(state, action, child)
            counter += 1
            heapq.heappush(frontier, (new_cost, counter, child, path + [child]))

    return None, float('inf')

# Complete: YES (step costs >= epsilon > 0)
# Optimal:  YES
# Time/Space: O(b^(1 + C*/epsilon))

A heuristic function h(n) estimates the cost of reaching the goal from node n. It is the bridge between uninformed and informed search — a way to inject problem-specific knowledge into the generic search framework.

Example heuristics for the 8-puzzle:

• h1: Number of misplaced tiles. If 5 tiles are out of place, we need at least 5 moves.
• h2: Manhattan distance — for each tile, its horizontal + vertical distance from its goal position. Stronger than h1 because it accounts for how far each tile needs to move.

How good is a heuristic? The effective branching factor b* measures this in practice. If A* finds a solution at depth d by generating N nodes, then b* satisfies N = 1 + b* + (b*)^2 + ... + (b*)^d. A perfect heuristic gives b* = 1 (the algorithm follows the optimal path directly). A useless heuristic gives b* ≈ b (same as uninformed search).

Heuristic design strategies:

1. Relaxed problems: Remove constraints from the original problem. The optimal cost of the relaxed problem is admissible for the original. For example, if tiles can slide through each other (remove the blocking constraint), the cost is Manhattan distance — a valid relaxation of the 8-puzzle.
2. Pattern databases: Precompute the exact cost of solving a subproblem (e.g., just 4 tiles out of 8) and store as a lookup table. These are often much stronger than Manhattan distance.
3. Learned heuristics: Train a neural network to estimate h from features of the state — this is active research.

The dominance relation: If h2(n) ≥ h1(n) for all n, and both are admissible, then h2 dominates h1. A* with h2 will always expand at most as many nodes as with h1. You should always prefer the dominating heuristic.

# 8-puzzle heuristics
def h1_misplaced(state, goal):
    """Number of misplaced tiles (excluding blank)."""
    return sum(1 for s, g in zip(state, goal)
               if s != 0 and s != g)

def h2_manhattan(state, goal, n=3):
    """Sum of Manhattan distances of tiles from goal positions."""
    goal_pos = {val: (i // n, i % n)
                for i, val in enumerate(goal) if val != 0}
    total = 0
    for i, val in enumerate(state):
        if val != 0:
            r, c = i // n, i % n
            gr, gc = goal_pos[val]
            total += abs(r - gr) + abs(c - gc)
    return total

# h2 dominates h1:
# For any state, manhattan >= misplaced
# (each misplaced tile contributes at least 1 to manhattan)
# Proof: if tile t is misplaced, its manhattan dist >= 1
#        so sum of manhattans >= count of misplaced.

# Relaxation argument for h2:
# Original rule: a tile can move to an adjacent blank.
# Relaxation: a tile can move to any adjacent square
#             (no blank needed).
# Optimal cost of relaxed problem = sum of Manhattan distances.

Greedy best-first search (GBFS) orders the frontier by h(n) alone — it always expands the node that looks closest to the goal according to the heuristic.

Intuition: It's like navigating by always walking in the direction that feels closest to your destination, without considering how far you've already walked. This can work brilliantly or catastrophically depending on the heuristic quality.

Properties:

• Complete: Not in general. GBFS can get trapped in loops (without an explored set) or go down dead-end paths that look promising but aren't.
• Optimal: No. GBFS ignores path cost completely. It can find a long suboptimal solution if the heuristic misleads it.
• Time/Space: O(b^m) in the worst case, but with good heuristics can be much faster in practice.

When is GBFS useful?: When you need an answer quickly and optimality doesn't matter. In real-time systems (game AI, navigation with tight time budgets), GBFS can find good-enough solutions fast.

The fundamental flaw: By ignoring g(n), GBFS can go far in a direction that looks good by h but has very high path cost. A* fixes this by combining both.

import heapq

def greedy_best_first(problem, h):
    """Expand nodes with smallest h(n) first.
    Not optimal, not complete in general."""
    counter = 0
    start = problem.initial_state
    frontier = [(h(start), counter, start, [start])]
    explored = set()

    while frontier:
        _, _, state, path = heapq.heappop(frontier)
        if problem.is_goal(state):
            return path
        if state in explored:
            continue
        explored.add(state)
        for action in problem.actions(state):
            child = problem.result(state, action)
            if child not in explored:
                counter += 1
                heapq.heappush(
                    frontier,
                    (h(child), counter, child, path + [child])
                )
    return None

# f(n) = h(n)   [ignores g(n)]
# Complete: NO   Optimal: NO
# Can be very fast with a good heuristic

A* is the crown jewel of heuristic search. It combines the actual path cost g(n) with the heuristic estimate h(n) into a single evaluation function:

f(n) = g(n) + h(n)

f(n) estimates the total cost of the cheapest solution that goes through node n: g(n) is the exact cost paid so far, and h(n) is the estimated cost remaining.

A* expands nodes in order of increasing f(n). It uses a min-priority queue on f(n).

Why does this work? Consider the contours of f. A* expands all nodes where f(n) < C* (the true optimal cost) before it expands any node where f(n) > C*. When it first expands the goal, the g value must equal C* — no cheaper path can exist, because all cheaper-looking nodes have already been expanded.

Optimality theorem: A* with GRAPH-SEARCH is optimal if the heuristic is consistent (see next concept). A* with TREE-SEARCH is optimal if the heuristic is merely admissible.

Completeness: A* is complete on finite graphs (or infinite graphs where the optimal solution exists and step costs are positive).

Complexity: The key question is how many nodes A* expands. In the best case (perfect heuristic), A* expands only nodes on the optimal path. In the worst case (h=0), it degenerates to UCS. The sweet spot is between these extremes, and a good heuristic can reduce the number of expansions from exponential to nearly linear.

A versus Dijkstra's*: Dijkstra's is UCS — it finds shortest paths to all nodes. A* is Dijkstra's guided toward the goal by a heuristic. Both are optimal; A* is faster when you only need the path to one goal.

import heapq

def astar(problem, h):
    """
    A* search. Optimal if h is consistent (for graph search).
    f(n) = g(n) + h(n)
    """
    counter = 0
    start = problem.initial_state
    g = {start: 0}
    # heap: (f, counter, state, path)
    frontier = [(h(start), counter, start, [start])]
    explored = set()

    while frontier:
        f, _, state, path = heapq.heappop(frontier)

        if problem.is_goal(state):
            return path, g[state]

        if state in explored:
            continue
        explored.add(state)

        for action in problem.actions(state):
            child = problem.result(state, action)
            new_g = g[state] + problem.step_cost(state, action, child)

            if child not in explored and (
               child not in g or new_g < g[child]):
                g[child] = new_g
                f_child = new_g + h(child)
                counter += 1
                heapq.heappush(
                    frontier,
                    (f_child, counter, child, path + [child])
                )
    return None, float('inf')

# Complete: YES   Optimal: YES (consistent h)
# f(n) = g(n) + h(n) -- combines cost-so-far + estimated-remaining

The correctness of A* hinges on two mathematical properties of h.

Admissibility: h(n) is admissible if it never overestimates the true cost to reach the goal:

h(n) ≤ h*(n) for all nodes n, where h*(n) is the true optimal cost from n to the goal.

Admissibility is the condition you need for TREE-SEARCH A* to be optimal. The intuition: if h never overcounts, then A* never prematurely passes over the optimal path (because the path always looks cheaper than or equal to its true cost).

Consistency (monotonicity): h is consistent if for every node n and every successor n' via action a:

h(n) ≤ c(n, a, n') + h(n')

This is the triangle inequality for heuristics: the estimated cost from n must be at most the edge cost to n' plus the estimated cost from n'. In other words, moving one step closer to the goal reduces h by at most the cost of that step.

Consistency implies admissibility: Every consistent heuristic is admissible. (Proof by induction: the chain of triangle inequalities from n to the goal gives h(n) ≤ h*(n).)

Why consistency matters for GRAPH-SEARCH: With a consistent heuristic, the f-values along any path are non-decreasing. This means: the first time A* expands a node n, it has found the optimal path to n. Therefore, the explored set optimization is safe — we never need to re-expand a node.

With a merely admissible (but inconsistent) heuristic in GRAPH-SEARCH, it is possible to add a node to the explored set via a suboptimal path, blocking the optimal path later. The fix is to check whether a newly found path to an explored state is cheaper and re-add it to the frontier if so (this is more expensive but correct).

Practical consequence: In virtually all real applications, heuristics derived from relaxed problems are consistent. Manhattan distance is consistent for the 8-puzzle. Straight-line distance is consistent for road routing.

# Verifying admissibility and consistency (unit test framework)
import math

def verify_admissibility(problem, h, all_states, true_h):
    """Check h(n) <= h*(n) for all states (requires knowing true_h)."""
    for state in all_states:
        assert h(state) <= true_h[state], (
            f"Inadmissible: h({state})={h(state)} > h*={true_h[state]}"
        )
    print("Admissibility verified.")

def verify_consistency(problem, h, all_states):
    """Check triangle inequality: h(n) <= c(n,a,n') + h(n')."""
    for state in all_states:
        for action in problem.actions(state):
            n_prime = problem.result(state, action)
            cost = problem.step_cost(state, action, n_prime)
            lhs = h(state)
            rhs = cost + h(n_prime)
            assert lhs <= rhs + 1e-9, (
                f"Inconsistent: h({state})={lhs} > "
                f"c={cost} + h({n_prime})={h(n_prime)}"
            )
    print("Consistency verified.")

# Key theorem:
# Consistent => Admissible (but not vice versa)
# Consistent => f-values non-decreasing along any path
# Consistent => GRAPH-SEARCH A* is optimal
#
# Proof of f non-decreasing:
# f(n') = g(n') + h(n')
#       = g(n) + c(n,a,n') + h(n')
#       >= g(n) + h(n)        [by consistency]
#       = f(n)

A* is optimal and complete, but it stores all generated nodes in memory. For large problems this is prohibitive — A*'s space complexity is O(b^d), same as BFS. Can we achieve A*'s optimality with DFS's memory usage?

IDA (Iterative Deepening A)** applies the IDDFS idea to A*. Instead of iterating on depth, IDA* iterates on the f-cost threshold:

1. Start with threshold f_0 = h(initial_state).
2. Run a depth-first search, pruning any node n with f(n) > threshold.
3. If the goal is found, return it. Otherwise, set threshold = min f-value that was pruned and repeat.

Properties:

• Complete and optimal (same conditions as A*)
• Space: O(b·d) — linear, like IDDFS
• Time: Similar to A* in practice; may re-expand nodes

When to use IDA vs A**: For problems where memory is the bottleneck (the 15-puzzle, the sliding tiles problem), IDA* is preferred. For route planning on graphs with good heuristics (navigation), A* with a priority queue is usually faster because it doesn't re-expand nodes.

IDA* is used in production-grade chess engines (iterative deepening alpha-beta is conceptually similar) and combinatorial puzzle solvers.

def idastar(problem, h):
    """IDA*: optimal + complete + space O(b*d)."""
    threshold = h(problem.initial_state)

    def search(state, g, threshold, path):
        f = g + h(state)
        if f > threshold:
            return f, None          # pruned; return f for next threshold
        if problem.is_goal(state):
            return -1, path         # -1 signals success
        min_threshold = float('inf')
        for action in problem.actions(state):
            child = problem.result(state, action)
            if child not in set(path):  # avoid cycles
                new_g = g + problem.step_cost(state, action, child)
                t, result = search(child, new_g, threshold, path + [child])
                if t == -1:
                    return -1, result   # found!
                min_threshold = min(min_threshold, t)
        return min_threshold, None

    path = [problem.initial_state]
    while True:
        t, result = search(problem.initial_state, 0, threshold, path)
        if t == -1:
            return result
        if t == float('inf'):
            return None         # no solution
        threshold = t           # jump to next f-contour

Now we can see all the algorithms as a single family, varying along two axes: what they optimize (depth/cost/estimate) and how much they remember.

The special cases:

• UCS is A* with h(n) = 0 (uninformed, so no heuristic savings).
• BFS is UCS with all step costs equal to 1.
• Greedy BF is A* with g(n) = 0 (ignores cost so far, not optimal).
• A* gracefully degrades: with a perfect heuristic it's linear; with h=0 it's UCS.

Practical rule of thumb for real problems:

1. If costs are uniform and space permits: BFS or IDDFS.
2. If costs are non-uniform: UCS or A*.
3. If you have a good heuristic: A* (memory available) or IDA* (memory tight).
4. If you just need any solution fast: Greedy best-first or DFS with backtracking.

# Summary: algorithm selection guide
def choose_algorithm(uniform_costs, have_heuristic, memory_tight):
    if not have_heuristic:
        if uniform_costs:
            return 'IDDFS'  # complete, optimal, low memory
        else:
            return 'UCS'    # optimal for non-uniform costs
    else:
        if memory_tight:
            return 'IDA*'   # optimal, heuristic-guided, low memory
        else:
            return 'A*'     # optimal, heuristic-guided, fast in practice

# Relationships:
# BFS   = UCS with c(s,a,s') = 1
# UCS   = A* with h(n) = 0
# DFS   = BFS with LIFO instead of FIFO frontier
# IDDFS = DFS iterated over depth limit
# IDA*  = IDDFS with f-cost threshold instead of depth
# A*    = UCS + admissible/consistent heuristic