Advanced Search Algorithms

Advanced search algorithms extend beyond basic DFS and BFS to include specialized techniques like A* search, bidirectional search, and iterative deepening. These algorithms are essential for solving complex pathfinding and optimization problems efficiently.

A* Search Algorithm

A* search uses heuristics to guide the search towards the goal, combining the benefits of Dijkstra's algorithm with informed search strategies.

A* Search Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cmath>
using namespace std;

struct Point {
    int x, y;
    
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
    
    // Manhattan distance heuristic
    int manhattanDistance(const Point& other) const {
        return abs(x - other.x) + abs(y - other.y);
    }
    
    // Euclidean distance heuristic
    double euclideanDistance(const Point& other) const {
        return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
    }
};

// Hash function for Point
struct PointHash {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};

struct AStarNode {
    Point pos;
    int gCost; // cost from start
    int hCost; // heuristic cost to goal
    Point parent;
    
    AStarNode(Point p, int g, int h, Point par) 
        : pos(p), gCost(g), hCost(h), parent(par) {}
    
    int fCost() const { return gCost + hCost; }
    
    bool operator>(const AStarNode& other) const {
        return fCost() > other.fCost();
    }
};

class AStar {
private:
    vector<vector<int>> grid;
    int rows, cols;
    vector<Point> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}, 
                               {1,1}, {1,-1}, {-1,1}, {-1,-1}}; // 8-directional
    
public:
    AStar(vector<vector<int>>& g) : grid(g), rows(g.size()), cols(g[0].size()) {}
    
    bool isValid(const Point& p) {
        return p.x >= 0 && p.x < rows && p.y >= 0 && p.y < cols && grid[p.x][p.y] == 0;
    }
    
    int getMoveCost(const Point& from, const Point& to) {
        // Diagonal moves cost more
        if (abs(from.x - to.x) + abs(from.y - to.y) == 2) {
            return 14; // approximately sqrt(2) * 10
        }
        return 10;
    }
    
    vector<Point> findPath(Point start, Point goal) {
        priority_queue<AStarNode, vector<AStarNode>, greater<AStarNode>> openSet;
        unordered_map<Point, int, PointHash> gScore;
        unordered_map<Point, Point, PointHash> cameFrom;
        
        openSet.push(AStarNode(start, 0, start.manhattanDistance(goal), Point(-1, -1)));
        gScore[start] = 0;
        
        while (!openSet.empty()) {
            AStarNode current = openSet.top();
            openSet.pop();
            
            if (current.pos == goal) {
                // Reconstruct path
                vector<Point> path;
                Point curr = goal;
                while (!(curr.x == -1 && curr.y == -1)) {
                    path.push_back(curr);
                    curr = cameFrom[curr];
                }
                reverse(path.begin(), path.end());
                return path;
            }
            
            // Skip if we found a better path already
            if (gScore.count(current.pos) && current.gCost > gScore[current.pos]) {
                continue;
            }
            
            for (const Point& dir : directions) {
                Point neighbor(current.pos.x + dir.x, current.pos.y + dir.y);
                
                if (!isValid(neighbor)) continue;
                
                int tentativeG = current.gCost + getMoveCost(current.pos, neighbor);
                
                if (!gScore.count(neighbor) || tentativeG < gScore[neighbor]) {
                    gScore[neighbor] = tentativeG;
                    cameFrom[neighbor] = current.pos;
                    
                    int hCost = neighbor.manhattanDistance(goal);
                    openSet.push(AStarNode(neighbor, tentativeG, hCost, current.pos));
                }
            }
        }
        
        return {}; // No path found
    }
    
    void printPath(const vector<Point>& path) {
        if (path.empty()) {
            cout << "No path found!" << endl;
            return;
        }
        
        vector<vector<char>> display(rows, vector<char>(cols, '.'));
        
        // Mark obstacles
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) display[i][j] = '#';
            }
        }
        
        // Mark path
        for (int i = 0; i < path.size(); i++) {
            if (i == 0) display[path[i].x][path[i].y] = 'S'; // Start
            else if (i == path.size() - 1) display[path[i].x][path[i].y] = 'G'; // Goal
            else display[path[i].x][path[i].y] = '*';
        }
        
        // Print grid
        for (const auto& row : display) {
            for (char c : row) {
                cout << c << " ";
            }
            cout << endl;
        }
        
        cout << "Path length: " << path.size() << endl;
    }
};

int main() {
    // Create a grid with obstacles (1 = obstacle, 0 = free)
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };
    
    AStar astar(grid);
    Point start(0, 0);
    Point goal(9, 9);
    
    cout << "Finding path from (0,0) to (9,9) using A* search:" << endl;
    cout << "Legend: S=Start, G=Goal, *=Path, #=Obstacle, .=Free" << endl << endl;
    
    vector<Point> path = astar.findPath(start, goal);
    astar.printPath(path);
    
    return 0;
}

A* search uses f(n) = g(n) + h(n) where g(n) is the actual cost from start and h(n) is the heuristic estimate to goal. The algorithm guarantees optimal paths when the heuristic is admissible (never overestimates).

Bidirectional Search

Bidirectional search runs two simultaneous searches from start and goal, meeting in the middle to reduce the search space exponentially.

Bidirectional BFS Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;

class BidirectionalBFS {
private:
    vector<vector<int>> graph;
    int n;
    
public:
    BidirectionalBFS(vector<vector<int>>& g) : graph(g), n(g.size()) {}
    
    vector<int> findPath(int start, int goal) {
        if (start == goal) return {start};
        
        // Two queues for forward and backward search
        queue<int> forwardQueue, backwardQueue;
        unordered_set<int> forwardVisited, backwardVisited;
        unordered_map<int, int> forwardParent, backwardParent;
        
        forwardQueue.push(start);
        backwardQueue.push(goal);
        forwardVisited.insert(start);
        backwardVisited.insert(goal);
        forwardParent[start] = -1;
        backwardParent[goal] = -1;
        
        while (!forwardQueue.empty() || !backwardQueue.empty()) {
            // Expand forward search
            if (!forwardQueue.empty()) {
                int meetingPoint = expandLevel(forwardQueue, forwardVisited, backwardVisited, 
                                             forwardParent, true);
                if (meetingPoint != -1) {
                    return constructPath(meetingPoint, forwardParent, backwardParent);
                }
            }
            
            // Expand backward search
            if (!backwardQueue.empty()) {
                int meetingPoint = expandLevel(backwardQueue, backwardVisited, forwardVisited, 
                                             backwardParent, false);
                if (meetingPoint != -1) {
                    return constructPath(meetingPoint, forwardParent, backwardParent);
                }
            }
        }
        
        return {}; // No path found
    }
    
private:
    int expandLevel(queue<int>& q, unordered_set<int>& visited, 
                   unordered_set<int>& otherVisited, unordered_map<int, int>& parent, 
                   bool isForward) {
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; i++) {
            int current = q.front();
            q.pop();
            
            for (int neighbor : graph[current]) {
                if (otherVisited.count(neighbor)) {
                    // Found intersection!
                    parent[neighbor] = current;
                    return neighbor;
                }
                
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    parent[neighbor] = current;
                    q.push(neighbor);
                }
            }
        }
        
        return -1; // No intersection found in this level
    }
    
    vector<int> constructPath(int meetingPoint, unordered_map<int, int>& forwardParent, 
                             unordered_map<int, int>& backwardParent) {
        vector<int> path;
        
        // Build path from start to meeting point
        vector<int> forwardPath;
        int current = meetingPoint;
        while (current != -1) {
            forwardPath.push_back(current);
            current = forwardParent[current];
        }
        reverse(forwardPath.begin(), forwardPath.end());
        
        // Build path from meeting point to goal
        vector<int> backwardPath;
        current = backwardParent[meetingPoint];
        while (current != -1) {
            backwardPath.push_back(current);
            current = backwardParent[current];
        }
        
        // Combine paths
        path = forwardPath;
        path.insert(path.end(), backwardPath.begin(), backwardPath.end());
        
        return path;
    }
};

// Iterative Deepening DFS
class IterativeDeepeningDFS {
private:
    vector<vector<int>> graph;
    int n;
    
public:
    IterativeDeepeningDFS(vector<vector<int>>& g) : graph(g), n(g.size()) {}
    
    vector<int> findPath(int start, int goal, int maxDepth = 20) {
        for (int depth = 0; depth <= maxDepth; depth++) {
            vector<bool> visited(n, false);
            vector<int> path;
            
            if (dfsLimited(start, goal, depth, visited, path)) {
                return path;
            }
        }
        
        return {}; // No path found within depth limit
    }
    
private:
    bool dfsLimited(int current, int goal, int depth, vector<bool>& visited, vector<int>& path) {
        path.push_back(current);
        
        if (current == goal) {
            return true;
        }
        
        if (depth == 0) {
            path.pop_back();
            return false;
        }
        
        visited[current] = true;
        
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                if (dfsLimited(neighbor, goal, depth - 1, visited, path)) {
                    return true;
                }
            }
        }
        
        visited[current] = false;
        path.pop_back();
        return false;
    }
};

int main() {
    // Create a sample graph
    vector<vector<int>> graph = {
        {1, 2},       // 0 -> 1, 2
        {0, 3, 4},    // 1 -> 0, 3, 4
        {0, 5, 6},    // 2 -> 0, 5, 6
        {1, 7},       // 3 -> 1, 7
        {1, 7},       // 4 -> 1, 7
        {2, 8},       // 5 -> 2, 8
        {2, 8},       // 6 -> 2, 8
        {3, 4, 9},    // 7 -> 3, 4, 9
        {5, 6, 9},    // 8 -> 5, 6, 9
        {7, 8}        // 9 -> 7, 8
    };
    
    BidirectionalBFS bidiBFS(graph);
    IterativeDeepeningDFS iddfs(graph);
    
    int start = 0, goal = 9;
    
    // Test bidirectional BFS
    cout << "Bidirectional BFS path from " << start << " to " << goal << ": ";
    vector<int> bidiPath = bidiBFS.findPath(start, goal);
    if (!bidiPath.empty()) {
        for (int i = 0; i < bidiPath.size(); i++) {
            if (i > 0) cout << " -> ";
            cout << bidiPath[i];
        }
        cout << " (length: " << bidiPath.size() << ")" << endl;
    } else {
        cout << "No path found" << endl;
    }
    
    // Test iterative deepening DFS
    cout << "Iterative Deepening DFS path from " << start << " to " << goal << ": ";
    vector<int> iddfsPath = iddfs.findPath(start, goal);
    if (!iddfsPath.empty()) {
        for (int i = 0; i < iddfsPath.size(); i++) {
            if (i > 0) cout << " -> ";
            cout << iddfsPath[i];
        }
        cout << " (length: " << iddfsPath.size() << ")" << endl;
    } else {
        cout << "No path found" << endl;
    }
    
    return 0;
}

Bidirectional search reduces time complexity from O(b^d) to O(b^(d/2)) where b is branching factor and d is depth. Iterative deepening combines DFS space efficiency with BFS optimality.

Key Takeaways

A* search uses heuristics to guide search efficiently, guaranteeing optimal paths with admissible heuristics
Bidirectional search reduces exponential search space by meeting in the middle
Iterative deepening combines DFS memory efficiency with BFS completeness and optimality
Choose search algorithm based on problem constraints: memory, optimality requirements, and heuristic availability