算法搜索

启发式搜索与记忆化搜索的对比

字数统计: 1.4k字   |   阅读时长: 6分
, ,

摘要: 启发式搜索、记忆化搜索两套方法。自定义备忘录中状态的哈希函数。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个搜索题，用 DFS 和 BFS 两套方法都可以解决。

如果用 DFS，需要引入记忆化搜索，并且由于状态的取值很稀疏，需要用哈希表维护备忘录，而这里的状态还需要自定义哈希函数。

如果用 BFS，也需要携带状态，之后可以设计估价函数用 AStar，其中的优先级队列需要自定义比较规则。

$1 题目

一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上，你的 骑士 驻扎在坐标为 [0, 0] 的方格里。

骑士的走法和中国象棋中的马相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。

每次移动，他都可以按图示八个方向之一前进。

现在，骑士需要前去征服坐标为 [x, y] 的部落，请你为他规划路线。

最后返回所需的最小移动次数即可。本题确保答案是一定存在的。

提示：

1
|x| + |y| <= 300

示例 1：
输入：x = 2, y = 1
输出：1
解释：[0, 0] → [2, 1]

示例 2：
输入：x = 5, y = 5
输出：4
解释：[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

$2 题解

算法1: BFS

状态设计

1
2
3
4
5
6
7
struct State
{
    int x;
    int y;
    int d;
    State(int x, int y, int d):x(x),y(y),d(d){}
};

维护已经访问过的状态

x 和 y 的范围为[-300, 300]，因此设定一个 OFFSET 将 x 和 y 的所有可能取值修正为正数，然后按最大范围开出 vector<vector<bool>>。

代码 (C++)

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
34
35
36
37
38
39
40
41
42
struct State
{
    int x;
    int y;
    int d;
    State(int x, int y, int d):x(x),y(y),d(d){}
};

const int OFFSET = 305;

class Solution {
public:
    int minKnightMoves(int x, int y) {
        if(x == 0 && y == 0)
            return 0;
        queue<State> q;
        q.push(State(0, 0, 0));
        visited.assign(610, vector<bool>(610, false));
        while(!q.empty())
        {
            State cur = q.front();
            q.pop();
            for(int d = 0; d < 8; ++d)
            {
                int i = cur.x + dx[d], j = cur.y + dy[d];
                State nxt(i, j, cur.d + 1);
                if(visited[nxt.x + OFFSET][nxt.y + OFFSET])
                    continue;
                if(i == x && j == y)
                    return cur.d + 1;
                visited[nxt.x + OFFSET][nxt.y + OFFSET] = true;
                q.push(nxt);
            }
        }
        return -1;
    }

private:
    vector<vector<bool>> visited;
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
};

算法2: 启发式搜索 Astar

估价函数

马一次跳动可以走 3 长度，因此点 (x, y) 的估价函数设为该点到 (x0, y0) 的曼哈顿距离除以 3。

1
2
3
4
int h(int x, int y, int x0, int y0)
{
    return (abs(x - x0) + abs(y - y0)) / 3;
}

代码 (C++)

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int h(int x, int y, int x0, int y0)
{
    return (abs(x - x0) + abs(y - y0)) / 3;
}

struct State
{
    int x;
    int y;
    int d;
    int h;
    State(int x, int y, int d):x(x),y(y),d(d),h(0){}
    bool operator==(const State& s) const
    {
        return this -> x == s.x && this -> y == s.y;
    }
};

struct HeapCmp
{
    bool operator()(const State& s1, const State& s2) const
    {
        return s1.d + s1.h > s2.d + s2.h;
    }
};

const int OFFSET = 305;

class Solution {
public:
    int minKnightMoves(int x, int y) {
        State s(0, 0, 0);
        s.h = h(0, 0, x, y);
        priority_queue<State, vector<State>, HeapCmp> pq;
        pq.push(s);
        visited.assign(610, vector<bool>(610, false));
        while(!pq.empty())
        {
            State cur = pq.top();
            pq.pop();
            if(cur.x == x && cur.y == y)
                return cur.d;
            if(visited[cur.x + OFFSET][cur.y + OFFSET])
                continue;
            visited[cur.x + OFFSET][cur.y + OFFSET] = true;
            for(int d = 0; d < 8; ++d)
            {
                int i = cur.x + dx[d], j = cur.y + dy[d];
                State nxt(i, j, cur.d + 1);
                nxt.h = h(i, j, x, y);
                if(visited[nxt.x + OFFSET][nxt.y + OFFSET])
                    continue;
                pq.push(nxt);
            }
        }
        return -1;
    }

private:
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    vector<vector<bool>> visited;
};

算法3: 记忆化搜索

定义 solve(x, y, x0, y0) 表示 (x, y) 到 (x0, y0) 所需的步数。

如果将查找方向改为从 (x, y) 向 (0, 0) 走则可以改为　solve(x, y)，x, y 始终　>= 0，如果小于零可以去相反数后调用。

由于从 (x, y) 寻找下一步的位置时，只考虑 x, y 两维均更接近 0 的方向。即 (x - 1, y - 2), (x - 2, y - 1)。

代码 (C++)

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct State
{
    int x;
    int y;
    State(int x, int y):x(x),y(y){}
    bool operator==(const State& s) const
    {
        return this -> x == s.x && this -> y == s.y;
    }
    bool operator<(const State& s) const
    {
        return (this -> x + this -> y) < (s.y + s.x);
    }
};

struct MyHash
{
    static constexpr int OFFSET = 305;
    int operator()(const State& s) const
    {
        return ((s.x + 305) * 305) + (s.y + 305);
    }
};

class Solution {
public:
    int minKnightMoves(int x, int y) {
        return solve(abs(x), abs(y));
    }

private:
    unordered_map<State, int, MyHash> dp;
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};

    int solve(int x, int y)
    {
        if(x == 0 && y == 0)
            return 0;
        if(x + y == 2)
            return 2;
        State s(x, y);
        if(dp.count(s) > 0)
            return dp[s];
        return dp[s] = 1 + min(solve(abs(x - 1), abs(y - 2)), solve(abs(x - 2), abs(y - 1)));
    }
};
Share