我已经深入搜索了互联网，但尚未找到解决我问题的方案。我认为我已经实现了一个用于滑动拼图游戏的广度优先搜索（BFS）。然而，除非状态只相差几步，否则它就无法解决问题，总是导致内存溢出错误。所以我想问大家，我哪里做错了？据我所知，我的代码是遵循BFS伪代码的。
编辑/备注：我已经用调试器逐步检查过了，但在我的眼中还没有发现什么异常，但我只是一个相对新手的程序员。
#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回答：
你的代码中有许多低效之处，导致运行速度变慢。说实话，我很惊讶你有耐心等待它达到内存溢出的状态。
主要问题在于这些搜索操作：std::find(visitedList.begin(), visitedList.end(), child) != visitedList.end()//和std::find(nodesToVisit.begin(), nodesToVisit.end(), child) == nodesToVisit.end()
这两个操作的时间复杂度都是O(N)，听起来还可以，但由于你在每个节点上都执行这些操作，最终导致时间复杂度为O(N2)。
你可以通过使用std::unordered_set<>来替代visitedList来解决这个问题。另外，你可以在节点入队时就将其添加到visited_list中（而不是在出队时）。这样，你只需要进行一次查找操作。
注意：你需要为std::hash<State>进行特化，以便使用std::unordered_set。
另一个提示：主循环中的这些cout << ...会显著减慢你的程序速度，因为它们默认会强制刷新并与操作系统同步，注释掉这些代码会使你的程序运行得更快。
实际上，你的代码还有很多其他可以改进的地方，但这些是另一个话题。修复算法复杂度问题会让你的程序进入非故障状态。
