为什么我的网格旅行者回忆还在粘住？

Question

我目前正在努力将记忆实施到网格旅行者问题中。看起来它应该起作用，但是它仍然坚持使用（18,18）之类的更大案例。我是否错过了一些东西，还是地图不是解决此类问题的正确选择？

PS，我仍然很陌生地使用地图。

    #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＆lt; string，uint64_t＆gt; grid作为深度优先搜索的参数。

您正在调用grid [key] = gridtravmemo（m-1，n，grid） + gridtravmemo（m，n-1，grid）;这意味着您的搜索将分成两个分支。 但是，这两个分支中的网格是不同的。这意味着可以在两个单独的分支中访问相同的状态，从而导致运行时更像o（ 2^（n*m））。

当您测试18x18网格时，这肯定不会很快运行。

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

尝试这样的事情：

    #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;
    }