广度优先搜索根据否决插入位置花费过多时间

Question

正在解决的问题是LeetCode #752 "Open the Lock"。总结：

您有一个带有四个一位数轮子的密码锁，从 0、0、0、0 开始。您想要确定更改锁以显示 a、b、c、d 所需的最少移动次数。在每个动作中，您可以向前或向后旋转一个轮子，例如第一个轮子从 0 到 1 或 0 到 9.

存在“死胡同”组合。如果您在一系列动作中遇到死胡同，锁就会卡住。所以一定要达到目标组合，不要遇到死胡同。

例如：

 deadends = ["0201","0101","0102","1212","2002"], target = "0202"

有效着法顺序为“0000”->“1000”->“1100”->“1200”->“1201”->“1202”->“0202”。请注意，像“0000”->“0001”->“0002”->“0102”->“0202”这样的序列是无效的，因为在显示屏变成死胡同“0102”后，锁的轮子卡住了。（从问题描述中复制）

我设计了一个使用队列和两个集合的广度优先搜索。一组包含死角，一组包含已经考虑过的组合。

如果我在从队列中弹出后将一个组合插入到“已考虑”集合中，我的解决方案将花费太多时间来执行。如果我在组合生成后 立即插入它 ，那么我的解决方案执行得更快。

为什么？我认为它们实际上是一样的！对于“接近”0、0、0、0 的组合，“慢”解仍然设法收敛。对于距离较远的组合，在限定时间内不收敛。

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        // "minimum total number of turns" suggests BFS (queue)
        
        // time complexity is O(C^N) where C is constant (number of choices for each digit, e.g. ten, or 24 if a...z) and N is the length of the combo
        // other terms are N^2 and + N_deadends
        // string operations are N^2: for each of the N digits, we need to construct a string of length N (itself an O(N) operation) -> O(N*N*2) (twice for +1 and -1)
        int nMoves = 0;
        
        std::queue<std::string> toConsider;
        toConsider.push("0000");
        std::set<std::string> considered;
        
        std::set<std::string> de;
        for (auto d : deadends) de.insert(d); // converting the deadends vector to a set improves speed significantly

        while (!toConsider.empty()) {
            int const nStatesInLevel = toConsider.size();
            
            for (int i = 1; i <= nStatesInLevel; ++i) {
                std::string state = toConsider.front();
                toConsider.pop();
                // considered.insert(state); // IF WE PUT THIS HERE INSTEAD OF BELOW, THE SOLUTION IS TOO SLOW!
                if (de.find(state) != de.end()) continue; // veto if dead-end
                if (state == target) return nMoves;
                
                for (int i : {0, 1, 2, 3}) { // one out of four wheels to turn
                    int const oldWheelVal = state.at(i) - '0';
                    for (int c : {1, -1}) { // increase or decrease wheel value
                        int newWheelVal = oldWheelVal + c;
                        if (newWheelVal == -1) newWheelVal = 9;
                        if (newWheelVal == 10) newWheelVal = 0;
                        std::string newWheel = state;
                        newWheel.at(i) = newWheelVal + '0';
          
                        if (considered.find(newWheel) == considered.end()) {
                            toConsider.push(newWheel);
                            considered.insert(newWheel); // we need to put this here instead of after it is popped in order to avoid "time limit exceeded".
                            // I think both places should effectively be the same!
                        }
                    }
                }
            }
            
            nMoves++;
            
        }
        
        return -1;
    }
};

Answer 1

慢速版本将允许将重复状态添加到队列中。它们是重复的只有当它们被从中拉出来时才会被检测到，但是“伤害”已经完成了。由于有许多不同的路径可以到达相同的状态，这很快就会使队列变得不必要地大，填充大量重复项。这不仅需要内存成本，还需要时间成本，因为额外的内存分配需要时间。

首先从队列中取出初始状态0000，并标记为已访问，然后将以下内容附加到它：

1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009

那么在下一次迭代中，会拉取1000，将下面的加入到队列中。 0000 将被发现，但未添加到队列中（标记为 ----）：

2000, ----, 1100, 1900, 1010, 1090, 1001, 1009

然后9000会从队列中拉出来，并添加如下：

----, 8000, 9100, 9900, 9010, 9090, 9001, 9009

然后0100将从队列中拉出，并追加到后面。同样，0000不会被添加，但是，再次发现其他状态没有，但还没有从队列中拉出，所以它们没有被检测为重复（标有星号）：

1100*, 9100*, 0200, ----, 0110, 0190, 0101, 0109

...等等。我们走得越远，添加的重复项就越多。

更快的版本永远不会将重复状态推送到队列。

广度优先搜索根据否决插入位置花费过多时间

Breadth-first search takes excessive time depending on veto insertion position

c++

performance

queue

breadth-first-search