当前位置：首页 > news >正文

随机深度优先搜索（Randomized DFS）算法原理

news 2026/5/11 23:44:09

随机深度优先搜索是深度优先搜索的变种，通过在每一步随机选择邻接节点来增加路径的不可预测性。该算法天然适合生成或解决迷宫问题，因其倾向于生成长而曲折的路径。

核心特点：

使用栈（显式或隐式）实现回溯
随机选择邻接节点顺序
时间复杂度为O(V+E)，空间复杂度为O(V)

C++实现关键步骤

数据结构定义

#include <iostream> #include <vector> #include <stack> #include <cstdlib> #include <ctime> #include <algorithm> struct Cell { int x, y; bool visited = false; bool top_wall = true, bottom_wall = true; bool left_wall = true, right_wall = true; };

迷宫初始化

void initMaze(std::vector<std::vector<Cell>>& maze, int width, int height) { maze.resize(height); for (int y = 0; y < height; ++y) { maze[y].resize(width); for (int x = 0; x < width; ++x) { maze[y][x].x = x; maze[y][x].y = y; } } std::srand(std::time(nullptr)); }

随机DFS核心实现

void generateMaze(std::vector<std::vector<Cell>>& maze) { std::stack<Cell*> cellStack; Cell* current = &maze[0][0]; current->visited = true; cellStack.push(current); while (!cellStack.empty()) { current = cellStack.top(); auto neighbors = getUnvisitedNeighbors(current, maze); if (!neighbors.empty()) { Cell* next = neighbors[std::rand() % neighbors.size()]; removeWalls(current, next); next->visited = true; cellStack.push(next); } else { cellStack.pop(); } } }

辅助函数实现

std::vector<Cell*> getUnvisitedNeighbors(Cell* cell, const std::vector<std::vector<Cell>>& maze) { std::vector<Cell*> neighbors; int dx[] = {0, 1, 0, -1}; int dy[] = {-1, 0, 1, 0}; for (int i = 0; i < 4; ++i) { int nx = cell->x + dx[i]; int ny = cell->y + dy[i]; if (nx >= 0 && nx < maze[0].size() && ny >= 0 && ny < maze.size() && !maze[ny][nx].visited) { neighbors.push_back(const_cast<Cell*>(&maze[ny][nx])); } } return neighbors; } void removeWalls(Cell* a, Cell* b) { if (a->x == b->x) { if (a->y < b->y) { a->bottom_wall = false; b->top_wall = false; } else { a->top_wall = false; b->bottom_wall = false; } } else { if (a->x < b->x) { a->right_wall = false; b->left_wall = false; } else { a->left_wall = false; b->right_wall = false; } } }

迷宫求解实现

路径搜索算法

bool solveMaze(std::vector<std::vector<Cell>>& maze, Cell* start, Cell* end, std::vector<Cell*>& path) { std::stack<Cell*> stack; stack.push(start); start->visited = true; while (!stack.empty()) { Cell* current = stack.top(); path.push_back(current); if (current == end) return true; auto neighbors = getAccessibleNeighbors(current, maze); if (!neighbors.empty()) { Cell* next = neighbors[std::rand() % neighbors.size()]; next->visited = true; stack.push(next); } else { path.pop_back(); stack.pop(); } } return false; }

可通行邻居检测

std::vector<Cell*> getAccessibleNeighbors(Cell* cell, const std::vector<std::vector<Cell>>& maze) { std::vector<Cell*> neighbors; int dx[] = {0, 1, 0, -1}; int dy[] = {-1, 0, 1, 0}; bool walls[] = {cell->top_wall, cell->right_wall, cell->bottom_wall, cell->left_wall}; for (int i = 0; i < 4; ++i) { if (!walls[i]) { int nx = cell->x + dx[i]; int ny = cell->y + dy[i]; if (nx >= 0 && nx < maze[0].size() && ny >= 0 && ny < maze.size() && !maze[ny][nx].visited) { neighbors.push_back(const_cast<Cell*>(&maze[ny][nx])); } } } return neighbors; }

可视化输出

控制台打印迷宫

void printMaze(const std::vector<std::vector<Cell>>& maze) { for (const auto& row : maze) { // 打印顶部墙壁 for (const auto& cell : row) { std::cout << (cell.top_wall ? "+---" : "+ "); } std::cout << "+\n"; // 打印侧边墙壁 for (const auto& cell : row) { std::cout << (cell.left_wall ? "|" : " "); std::cout << " "; } std::cout << "|\n"; } // 打印底部边界 for (size_t i = 0; i < maze[0].size(); ++i) { std::cout << "+---"; } std::cout << "+\n"; }

完整示例调用

int main() { const int WIDTH = 10, HEIGHT = 10; std::vector<std::vector<Cell>> maze; initMaze(maze, WIDTH, HEIGHT); generateMaze(maze); std::vector<Cell*> path; solveMaze(maze, &maze[0][0], &maze[HEIGHT-1][WIDTH-1], path); printMaze(maze); return 0; }