路径搜索

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

辅助代码（全局变量）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef pair<int, int> node;
vector<vector<int>> G = {
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,2,1,1,1,1,1},
    {1,1,1,1,2,3,2,1,1,1,1},
    {1,1,1,2,3,4,3,2,1,1,1},
    {1,1,2,3,4,5,4,3,2,1,1},
    {1,1,1,2,3,4,3,2,1,1,1},
    {1,1,1,1,2,3,2,1,1,1,1},
    {1,1,1,1,1,2,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1}
};
int row = (int)G.size();
int col = (int)G[0].size();
node S = { 5,0 };
node E = { 5,10 };
int dir[] = { -1, 0, 1, 0, -1 };

DFS

  • DFS是无法找到最优路径的（理论上可以，但是复杂度巨高，如果是四个方向搜索的话，那么就是四叉树，高度是图中结点数，也就是说如果是10x10的图，那就是大约4^100复杂度）
  • 下面代码只表示找到任意一条路后直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<bool>> visited(row, vector<bool>(col, false));
vector<node> path;
bool END = false;
void dfs(node cur) {
    if (cur == E) 
        END = true;
    visited[cur.first][cur.second] = true;
    path.push_back(cur);
    for (int i = 0; i < 4 && !END; ++i) {
        int ix = cur.first + dir[i];
        int iy = cur.second + dir[i + 1];
        if (ix < 0 || ix >= row || iy < 0 || iy >= col || visited[ix][iy]) continue;
        dfs({ ix, iy });
    }
    if (END) return; // 保留路径
    path.pop_back();
    visited[cur.first][cur.second] = false;
}

BFS

  • BFS是可以找到最优路径的，每次到某点的距离变小时就将其加入队列
  • 不可以提前结束，无法确定是否能够通过后面的点来缩短到终点的距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bfs() {
    queue<node> qe;
    qe.push(S);
    vector<vector<int>> dist(row, vector<int>(col, 10000));
    dist[S.first][S.second] = 0;
    while (!qe.empty()) {
        node cur = qe.front(); qe.pop();
        for (int i = 0; i < 4; ++i) {
            int ix = cur.first + dir[i];
            int iy = cur.second + dir[i + 1];
            if (ix < 0 || ix >= row || iy < 0 || iy >= col) continue;
            if (dist[ix][iy] > dist[cur.first][cur.second] + G[ix][iy]) {
                dist[ix][iy] = dist[cur.first][cur.second] + G[ix][iy];
                qe.emplace(ix, iy);
            }
        }
    }
}

Dijkstra

  • 每次弹出优先队列的都是确定下来的最优解，因此可以接触终点时直接break提前结束
  • 也不需要visited数组，因为遇到重复的x和y时，优先队列会依照priority排列，大的自动排到后面，由于接触到终点直接break，那些非最优的都没机会弹出队列。
  • 你可能会想到有没有这种可能绕一个大圈然后使得到达终点的距离进一步降低？其实不可能的，因为优先队列的贪心思想，反证法：如果之前已经将E弹出，后面又经过X到达E使得dist(E)降低；但是既然后面再弹出的X，那证明X的dist比之前第一次弹出的E的dist要大(优先队列先弹出dist小的)，那如何能使得经过X后让E的dist减小呢？矛盾！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct item{ // 存放在优先队列的结构体
    int x;
    int y;
    int priority;
    bool operator>(const item& ano) const {
        return this->priority > ano.priority;
    }
};

void dijkstra() {
    priority_queue<item, vector<item>, greater<item>> qe;
    vector<vector<int>> dist(row, vector<int>(col, 1000)); // dist二维数组
    qe.push({ S.first, S.second, 0 }); // 初始化
    dist[S.first][S.second] = 0; // 初始化
    while (!qe.empty()) {
        item cur = qe.top(); qe.pop();
        // 找到后可以直接返回，这里贪心算法，确保是最优解
        if (cur.x == E.first && cur.y == E.second) break;
        for (int i = 0; i < 4; ++i) {
            int ix = cur.x + dir[i];
            int iy = cur.y + dir[i + 1];
            if (ix < 0 || ix >= row || iy < 0 || iy >= col) continue;
            if (dist[ix][iy] > cur.priority + G[ix][iy]) {
                dist[ix][iy] = cur.priority + G[ix][iy];
                qe.push({ ix, iy, dist[ix][iy] });
            }
        }
    }
}

A星

  • A星的思想是对Dijkstra的一点改进。首先BFS是没有方向的，Dijkstra是在BFS之上加入了贪心思想，但是同样没有方向，A星则是增加了终点方向的属性，并入到Dijkstra的优先级中，参与优先队列的弹出选择，对于能明确表明与终点距离的图问题来说，效果相当不错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct item{ // 存放在优先队列的结构体
    int x;
    int y;
    int p1; // 从起点到该点的 dist (与实际图权值相关，如果无权图则退化为曼哈顿距离)
    int p2; // 从该点到终点的 [曼哈顿距离] 
    bool operator>(const item& ano) const {
        return p1 + p2 > ano.p1 + ano.p2;
    }
};

// 获取曼哈顿距离的函数
auto getP2 = [&](int x, int y) {return abs(E.first - x) + abs(E.second - y); };

void aStar() {
    priority_queue<item, vector<item>, greater<item>> qe;
    vector<vector<int>> dist(row, vector<int>(col, 1000)); // dist二维数组
    qe.push({ S.first, S.second, 0, getP2(S.first, S.second)}); // 初始化
    dist[S.first][S.second] = 0; // 初始化
    while (!qe.empty()) {
        item cur = qe.top(); qe.pop();
        // 找到后可以直接返回，这里贪心算法，确保是最优解
        if (cur.x == E.first && cur.y == E.second) break;
        for (int i = 0; i < 4; ++i) {
            int ix = cur.x + dir[i];
            int iy = cur.y + dir[i + 1];
            if (ix < 0 || ix >= row || iy < 0 || iy >= col) continue;
            if (dist[ix][iy] > cur.p1 + G[ix][iy]) {
                dist[ix][iy] = cur.p1 + G[ix][iy];
                qe.push({ ix, iy, dist[ix][iy], getP2(ix, iy) });
            }
        }
    }
}