问C++ 8-滑动式难题解决程序非常慢

EN

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <assert.h>

using namespace std;

vector<string> solvePuzzle(string state);
vector<string> reconstructPath(map<string, string> cameFrom, string current);
vector<string> findNeighbors(string state);
float calcfScore(string state);
string to_string(int i);

int main() {

    // For Testing Purposes, otherwise we don't need this function

    string state;
    getline(cin, state);

    vector<string> solution = solvePuzzle(state);
    cout << "Solution:" << endl;
    for (int index = 0; index < solution.size(); index++) cout << solution[index] << endl;


    return 0;
}


vector<string> solvePuzzle(string state) {

    assert (state.length() == 9);

    vector<string> frontier;
    vector<string> visited;
    map<string, string> cameFrom;

    frontier.push_back(state);


    map<string, float> fScore;
    map<string, int> gScore;
    gScore[state] = 0;

    while (frontier.size() > 0) {

        int best_choice = 0;
        float minimum = 100;

        for (int index = 0; index < frontier.size(); index++) {
            if (fScore[frontier[index]] > minimum) best_choice = index;
        }

        string curr_state = frontier[best_choice];
        frontier.erase(frontier.begin() + best_choice);
        visited.push_back(curr_state);

        // DEBUGGING

        /*
        cout << endl << curr_state << endl;// << "Visited: ";
        //for (int index = 0; index < visited.size(); index++) cout << visited[index];
        cout << endl << "Frontier: ";
        for (int index = 0; index < frontier.size(); index++) cout << frontier[index];
        cout << endl;
        */

        if (curr_state == "123456780") {
            vector<string> path = reconstructPath(cameFrom, curr_state);

            cout << "No. of fScore's Taken: " << fScore.size() << endl;

            return path;
        }


        vector<string> neighbors = findNeighbors(curr_state);

        for (unsigned int index = 0; index < neighbors.size(); index++) {

            string neighbor = neighbors[index];
            //cout << neighbor;
            if (find(visited.begin(), visited.end(), neighbor) != visited.end()) {
                    //cout << " terminated in visited." << endl;
                    continue;
            }

            if (find(frontier.begin(), frontier.end(), neighbor) == frontier.end()) {
                //cout << " " << "State not yet Visited. State inserted in Frontier." << endl;
                frontier.push_back(neighbor);

            } else if ((gScore[curr_state] + 1) >= gScore[neighbor]) {
                    //cout << " terminated due to idiotic reasons." << endl;
                    continue;
            }

            // This path is the best until now. Record it!
            cameFrom[neighbor] = curr_state;
            gScore[neighbor] = gScore[curr_state] + 1;
            fScore[neighbor] = calcfScore(neighbor) + gScore[neighbor];

        }


        // mapping >>>>>>>>>>>>>>>>>>>>>>>>>>>
        //for (std::map<string,float>::iterator it=fScore.begin(); it!=fScore.end(); ++it) {
        //    std::cout << it->first << " => " << it->second << '\n';}
        //cout << endl;
    }

    return vector<string>();

}

vector<string> reconstructPath(map<string, string> cameFrom, string current) {

    vector<string> totalPath;
    totalPath.push_back(current);

    while (cameFrom.find(current) != cameFrom.end()) {

        current = cameFrom[current];
        totalPath.insert(totalPath.begin(), current);
    }

    return totalPath;

}


float calcfScore(string state) {

    float fScore = 0;
    string finalState = "123456780";

    for (int index = 1; index < 9; index++) {
        int req_loc = finalState.find(to_string(index));
        int loc = state.find(to_string(index));
        //cout << index << req_loc << loc << endl;

        fScore += abs(req_loc % 3 - loc % 3) + abs(static_cast<int>(req_loc/3) - static_cast<int>(loc/3));

        for (int smallIndex = (index - 1 - ((index - 1) % 3)); smallIndex < (index - 1 - ((index - 1) % 3)) + 3; smallIndex++) {

            if (smallIndex == index) continue;

            if ((smallIndex < index) & (state[smallIndex] > state[index]) & (state[smallIndex] < (index - 1 - ((index - 1) % 3)) + 3)) fScore += 2;
            if ((smallIndex > index) & (state[smallIndex] < state[index]) & (state[smallIndex] > (index - 1 - ((index - 1) % 3)))) fScore += 2;

        }


    }

    return fScore;

}

vector<string> findNeighbors(string state) {

    vector<string> neighbors;
    int index = state.find('0');

    if (index % 3 < 2) {
        string temp_state = state;
        temp_state[index] = state[index + 1];
        temp_state[index + 1] = '0';
        neighbors.push_back(temp_state);
    }

    if (index % 3 > 0) {
        string temp_state = state;
        temp_state[index] = state[index - 1];
        temp_state[index - 1] = '0';
        neighbors.push_back(temp_state);
    }

    if (index > 2) {
        string temp_state = state;
        temp_state[index] = state[index - 3];
        temp_state[index - 3] = '0';
        neighbors.push_back(temp_state);
    }

    if (index < 6) {
        string temp_state = state;
        temp_state[index] = state[index + 3];
        temp_state[index + 3] = '0';
        neighbors.push_back(temp_state);
    }

    return neighbors;

}

string to_string(int i)
{
    stringstream ss;
    ss << i;
    return ss.str();
}