为什么我的 Grid Traveler Memoization 仍然存在？

Question

我目前正致力于在 Grid Traveler 问题中实现记忆化。看起来它应该可以工作，但它仍然坚持在更大的情况下，如 (18,18)。我是不是漏掉了什么，或者地图不是解决此类问题的正确选择？

P.S。我在使用地图方面还是个新手。

    #include <iostream>
    #include <unordered_map>
    #include <string>
    using namespace std;

    uint64_t gridTravMemo(int m, int n, unordered_map<string, uint64_t>grid)
    {
        string key;

        key = to_string(m) + "," + to_string(n);
        if (grid.count(key) > 0)
            return grid.at(key);
        if (m == 1 && n == 1)
            return 1;
        if (m == 0 || n == 0)
            return 0;

        grid[key] = gridTravMemo(m-1, n, grid) + gridTravMemo(m, n-1, grid);
        return grid.at(key);
    }

    int main()
    {
        unordered_map<string, uint64_t> gridMap;

        cout << gridTravMemo(1, 1, gridMap) << endl;
        cout << gridTravMemo(2, 2, gridMap) << endl;
        cout << gridTravMemo(3, 2, gridMap) << endl;
        cout << gridTravMemo(3, 3, gridMap) << endl;
        cout << gridTravMemo(18, 18, gridMap) << endl;

        return 0;
    }

Answer 1

记忆搜索的要点是通过返回您之前计算的任何值来优化运行宁时间。这样，您可以达到 O(N*M).

的运行时间，而不是蛮力算法

但是，您将 unordered_map<string, uint64_t>grid 作为参数传递给 depth-first 搜索。

您正在呼叫 grid[key] = gridTravMemo(m-1, n, grid) + gridTravMemo(m, n-1, grid); 这意味着您的搜索正分成两个分支。 然而，这两个分支中的grid是不同的。这意味着可以在两个不同的分支中访问相同的状态，从而导致运行时间更像O(2^(N*M)).

当您测试 18x18 网格时，这绝对运行不够快。

这相对容易修复。只需将 grid 声明为全局变量即可。这样它的值就可以在不同的分支之间使用。

尝试这样的事情：

    #include <iostream>
    #include <unordered_map>
    #include <string>
    using namespace std;

    unordered_map<string, uint64_t> grid;

    uint64_t gridTravMemo(int m, int n)
    {
        string key;

        key = to_string(m) + "," + to_string(n);
        if (grid.count(key) > 0)
            return grid.at(key);
        if (m == 1 && n == 1)
            return 1;
        if (m == 0 || n == 0)
            return 0;

        grid[key] = gridTravMemo(m-1, n) + gridTravMemo(m, n-1);
        return grid.at(key);
    }

    int main()
    {

        cout << gridTravMemo(1, 1) << endl;
        grid.clear()
        cout << gridTravMemo(2, 2) << endl;
        grid.clear()
        cout << gridTravMemo(3, 2) << endl;
        grid.clear()
        cout << gridTravMemo(3, 3) << endl;
        grid.clear()
        cout << gridTravMemo(18, 18) << endl;

        return 0;
    }

为什么我的 Grid Traveler Memoization 仍然存在？

Why is my Grid Traveler Memoization still sticking?

c++11

runtime

dynamic-programming

unordered-map

memoization