8 通过 BFS 拼图

Question

我已经在互联网上进行了深入的搜索，但我还没有找到解决我的问题的方法。我已经（我认为）为滑动方块游戏实现了 BFS。但是，除非状态相差几步，否则它无法解决问题，否则只会导致内存不足错误。所以我的问题是，我哪里错了？ AFAIK 我的代码遵循 BFS 伪代码。

EDIT/NOTE: 我已经逐步调试了调试器，但我还没有发现任何不寻常的地方，但我只是一个新手程序员。

#include <ctime>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <deque>
#include <vector>

using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm:  Breadth-First Search 
//
// Move Generator:  
//
////////////////////////////////////////////////////////////////////////////////////////////
class State{
public:
    int state[9];

    State(){
        for (int i = 0; i < 9; i++){
            state[i] = i;
        }
    }

    State(string st){
        for (int i = 0; i < st.length(); i++){
            state[i] = st.at(i) - '0';
        }
    }

    State(const State &st){
        for (int i = 0; i < 9; i++){
            state[i] = st.state[i];
        }
    }

    bool operator==(const State& other) {

        for (int i = 0; i < 9; i++){
            if (this->state[i] != other.state[i]){return false;}
        }
        return true;
    }

    bool operator!=(const State& other) {
        return !(*this == other);
    }

    void swap(int x, int y){
        // State b; // blank state
        // for (int i = 0; i < 9; i++) // fill blank state with current state
        //  b.state[i] = state[i];

        int t = this->state[x]; // saves value of the value in position x of the state

        this->state[x] = this->state[y]; // swaps value of position x with position y in the state
        this->state[y] = t; // swaps value of position y with saved position x in the state
    }

    int findBlank(){ // finds position in 3x3 of blank tile
        for (int i=0; i<9; i++){
            if (state[i]==0) return i;
        }
    }

    vector<State> blankExpand(){
        int pos = this->findBlank();
        vector<State> vecStates;


        if (pos != 0 && pos != 1 && pos != 2){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos - 3);
            vecStates.push_back(newState);
        }

        if (pos != 6 && pos != 7 && pos != 8){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos + 3);
            vecStates.push_back(newState);
        }

        if (pos != 0 && pos != 3 && pos != 6){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos - 1);
            vecStates.push_back(newState);
        }

        if (pos != 2 && pos != 5 && pos != 8){ // swaps the tile above it
            State newState = State(*this);
            newState.swap(pos,pos + 1);
            vecStates.push_back(newState);
        }

        return vecStates;
    }
};

string breadthFirstSearch_with_VisitedList(string const initialState, string const goalState){
    string path;

  clock_t startTime;
  startTime = clock();

  deque<State> nodesToVisit;
  vector<State> visitedList;
  int maxQLength = 0;


  //Init
    State init(initialState);
    State goal(goalState);
    nodesToVisit.push_back(init);

    int count = 0;
    int numOfStateExpansions = 0 ;
//
    while (!nodesToVisit.empty()){
        if(maxQLength < nodesToVisit.size()){maxQLength = nodesToVisit.size();}

        State cur = nodesToVisit.front();
        nodesToVisit.pop_front();
         //remove front

        if (cur == goal){
            //solution found
            cout << "solved!";
            break;
        }

        //Get children
        vector<State> children = cur.blankExpand();

        numOfStateExpansions += children.size();        

        //For each child
        for (State& child : children) {
            for (int i = 0 ; i < 9;i++){
                cout << child.state[i];
            }
            cout << " child" << endl;

          //If already visited ignore
          if (std::find(visitedList.begin(), visitedList.end(), child) != visitedList.end()) {
            // cout << "duplicate" << endl;
            continue;
          }

          //If not in nodes to Visit
          else if (std::find(nodesToVisit.begin(), nodesToVisit.end(), child) == nodesToVisit.end()) {
            //Add child
            nodesToVisit.push_back(child);
          }
        }
        visitedList.push_back(cur);

    }



//***********************************************************************************************************
    clock_t actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);  
    return path;    

}

int main(){
    breadthFirstSearch_with_VisitedList("042158367", "123804765");
    //042158367
}

// 0 4 2
// 1 5 8
// 3 6 7

Answer 1

您的代码中有许多低效之处正在减慢速度。我真的很惊讶你有耐心等待它达到内存不足的状态。

罪魁祸首是以下搜索： std::find(visitedList.begin(), visitedList.end(), child) != visitedList.end() //and std::find(nodesToVisit.begin(), nodesToVisit.end(), child) == nodesToVisit.end()

这两个都在 O(N) 中执行，这听起来不错，但由于您在每个节点上执行它们，因此结果为 O(N²).

您可以通过对 visitedList 使用 std::unordered_set<> 来解决这个问题。此外，您可以在将节点加入队列后立即将它们添加到 visited_list（而不是在将它们出队时）。这样，您只需执行一次查找。

N.B。您必须专门化 std::hash<State> 才能使用 std::unordered_set.

另一个提示：主循环中的这些 cout << ... 确实会减慢你的速度，因为它们默认强制刷新并与 OS 同步，注释掉这些将使你的程序运行快多了。

实际上您的代码还可以进行更多改进，但这是改天的话题。修复算法的复杂性将使它进入事物的非破坏领域。

8 通过 BFS 拼图

8 Tile Puzzle via BFS

c++

artificial-intelligence

sliding-tile-puzzle