A Primer on Search Problems: From DFS to A* Search

Introduction

Whether you're navigating a social network, finding the shortest path in a city, or solving complex puzzles, search algorithms are crucial. We'll explore various search algorithms, from Depth-First Search (DFS) to A* Search, breaking down their use cases and how they work. By the end, you'll have a solid understanding of these algorithms and how to apply them to solve real-world problems.

Formulating a Search Problem

To tackle a search problem, we need to define a few key components:

1. State: The initial state where the agent starts.
2. Actions: Possible actions the agent can take and their outcomes.
3. Performance Measure: Criteria to determine if the agent has reached its goal.
4. Goal: The desired state the agent aims to achieve.

A solution to a search problem is a sequence of actions that form a path to the goal state.

Dimensions for Evaluation

To evaluate search algorithms, we consider:

• Completeness: Does the algorithm always find a solution if one exists?
• Optimality: Does it find the least cost solution?
• Time Complexity: How many nodes are generated in the worst case?
• Space Complexity: How many nodes are stored in memory at the same time in the worst case?

Complexity Variables

• b: Maximum branching factor of the search tree (number of children per node).
• d: Depth of the shallowest goal node (distance from the start node in terms of edge traversals).
• m: Maximum length of any path in the state space.

Uninformed Search

Uninformed or blind search strategies rely only on the information available in the problem definition. They treat all non-goal nodes in the frontier equally and differ in their tree expansion order, implemented by different queue structures (LIFO, FIFO, priority).

1. Depth-First Search (DFS)

Depth-First Search (DFS) is a fundamental graph traversal algorithm used to explore nodes and edges of a graph. Starting from a root node, DFS explores as far as possible along each branch before backtracking, making it suitable for searching tree structures and discovering connectivity in graphs.

DFS Code

1
def dfs(start, graph):
2
    stack = [start]
3
    reached = set()
4
    reached.add(start)
5

6
    while stack:
7
        current = stack.pop()
8
        for neighbor in graph.neighbors(current):
9
            if neighbor not in reached:
10
                stack.append(neighbor)
11
                reached.add(neighbor)

DFS Complexity

• Complete? No - DFS fails with infinite-depth spaces or spaces with loops. To avoid getting stuck, check for repeated states.
• Time Complexity? - Can be very bad if (maximum depth) is much larger than (depth of the solution).
• Space Complexity? - Requires linear space for each node's siblings and children.
• Optimal? No - DFS may find a suboptimal solution if the optimal goal is at a lower depth than the path DFS takes.

DFS Use Case (For you Leetcode People!)

1. Finding the Number of Connected Components (Undirected Graph)

   • Examples: 547. Number of Provinces, 200. Number of Islands

2. Reordering Routes

   • Example: 1466. Reorder Routes to Make All Paths Lead to the City Zero

3. Finding Strongly Connected Components in Directed Graphs

   • Kosaraju's Algorithm: Perform DFS on the original graph, reverse the graph, and perform DFS on the reversed graph in the order of decreasing finish times. Each DFS run reveals a strongly connected component.

2. Breadth-First Search (BFS)

Breadth-First Search (BFS) explores nodes level by level, making it ideal for finding the shortest path in an unweighted graph. Starting from the root node, BFS expands all its neighbors before moving on to the next level.

BFS Code

1
from queue import Queue
2

3
def bfs(start, graph):
4
    frontier = Queue()
5
    frontier.put(start)
6
    reached = set()
7
    reached.add(start)
8

9
    while not frontier.empty():
10
        current = frontier.get()
11
        for neighbor in graph.neighbors(current):
12
            if neighbor not in reached:
13
                frontier.put(neighbor)
14
                reached.add(neighbor)

BFS Complexity

• Complete? Yes, if the branching factor is finite.
• Time Complexity?
• Space Complexity?
• Optimal? Yes, if all step costs are equal.

BFS Use Case

1. Shortest Path in Unweighted Graphs

   • Example: Finding the shortest path in a maze or unweighted network.

2. Finding All Nodes Within a Certain Distance

   • Example: Social network analysis to find all friends within a certain number of connections.

3. Iterative Deepening Depth-First Search (IDDFS)

**Iterative Deepening Depth-First Search (IDDFS) **combines the space efficiency of DFS with the completeness of BFS. It performs DFS with increasing depth limits until a solution is found.

IDDFS Code

1
def iddfs(start, goal, graph):
2
    def dls(node, depth):
3
        if depth == 0 and node == goal:
4
            return [node]
5
        if depth > 0:
6
            for neighbor in graph.neighbors(node):
7
                path = dls(neighbor, depth - 1)
8
                if path:
9
                    return [node] + path
10
        return None
11

12
    depth = 0
13
    while True:
14
        path = dls(start, depth)
15
        if path:
16
            return path
17
        depth += 1

IDDFS Complexity

• Complete? Yes, if no infinite paths.
• Time Complexity?
• Space Complexity?
• Optimal? Yes, if all step costs are equal.

Informed Search

Informed search algorithms use additional information (heuristics) to guide the search process more efficiently towards the goal. By incorporating heuristics, these algorithms can significantly reduce the search space and find optimal solutions more quickly than uninformed methods. Key examples include Dijkstra's Algorithm, Greedy Best-First Search, and A* Search.

1. Uniform Cost Search (Dijkstra's Algorithm)

Dijkstra's algorithm is used for finding the shortest paths between nodes in a weighted graph. It expands the least-cost node first, making it optimal for graphs with varying edge weights.

Dijkstra's Code

1
from queue import PriorityQueue
2

3
def dijkstra(start, goal, graph):
4
    frontier = PriorityQueue()
5
    frontier.put((0, start))
6
    came_from = {}
7
    cost_so_far = {}
8
    came_from[start] = None
9
    cost_so_far[start] = 0
10

11
    while not frontier.empty():
12
        current_priority, current = frontier.get()
13

14
        if current == goal:
15
            break
16

17
        for next in graph.neighbors(current):
18
            new_cost = cost_so_far[current] + graph.cost(current, next)
19
            if next not in cost_so_far or new_cost < cost_so_far[next]:
20
                cost_so_far[next] = new_cost
21
                priority = new_cost
22
                frontier.put((priority, next))
23
                came_from[next] = current

Dijkstra's Complexity

• Complete? Yes.
• Time Complexity?
• Space Complexity?
• Optimal? Yes, for graphs with non-negative weights.

2. Greedy Best-First Search

Greedy Best-First Introduction

Greedy Best-First Search uses heuristics to guide its search, prioritizing nodes that appear closest to the goal. It is faster than other methods but may not always find the optimal path.

Greedy Best-First Code

1
from queue import PriorityQueue
2

3
def greedy_best_first_search(start, goal, graph, heuristic):
4
    frontier = PriorityQueue()
5
    frontier.put((0, start))
6
    came_from = {}
7
    came_from[start] = None
8

9
    while not frontier.empty():
10
        current_priority, current = frontier.get()
11

12
        if current == goal:
13
            break
14

15
        for next in graph.neighbors(current):
16
            if next not in came_from:
17
                priority = heuristic(goal, next)
18
                frontier.put((priority, next))
19
                came_from[next] = current

Greedy Best-First Complexity

• Complete? No, unless a 'seen' set is used.
• Time Complexity?
• Space Complexity?
• **Optimal?

** No, it may not find the shortest path.

3. A* Search

A* search combines the strengths of Dijkstra's algorithm and Greedy Best-First Search by using both the cost so far () and a heuristic ().

A* Code

1
from queue import PriorityQueue
2

3
def a_star_search(start, goal, graph, heuristic):
4
    frontier = PriorityQueue()
5
    frontier.put((0, start))
6
    came_from = {}
7
    cost_so_far = {}
8
    came_from[start] = None
9
    cost_so_far[start] = 0
10

11
    while not frontier.empty():
12
        current_priority, current = frontier.get()
13

14
        if current == goal:
15
            break
16

17
        for next in graph.neighbors(current):
18
            new_cost = cost_so_far[current] + graph.cost(current, next)
19
            if next not in cost_so_far or new_cost < cost_so_far[next]:
20
                cost_so_far[next] = new_cost
21
                priority = new_cost + heuristic(goal, next)
22
                frontier.put((priority, next))
23
                came_from[next] = current

A* Complexity

• Complete? Yes, if the heuristic is admissible (never overestimates the true cost).
• Time Complexity?
• Space Complexity?
• Optimal? Yes, if the heuristic is admissible.