nqueens min-conflic搜索性能低下

Question

我正在执行nqueens min-conflict搜索，如]所述>

[Norvig，S.＆Peter，J. R. and。 （2014）。人工智能是一种现代方法。在皮尔逊（第58卷，第12期）中。

作者提到这种启发式方法非常有效：

然而，当我实现它时，我不能在一分钟之内解决超过5000个问题。尽管作者在50次迭代中实现了100万次迭代的速度，但我的实现通常会在5000次迭代中进行1000次迭代。 Another question提到了类似的结果。

关于我在做什么错的任何想法？是算法上的还是我在不应该使用的循环中使用？

update()是主要方法。

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <tuple>
#include <limits>
#include <queue>
#include <list>
#include <algorithm>
#include <map>

using namespace std;

/*
 * The n-queens problem solver
 * 
 * size      - the number of queens
 * isVerbose - whether the intermediate nodes are displayed
 */
//column,conflicts[row]


class NqueensSearch {
public:
    unsigned iterations = 0;
    unsigned boardSize;
    ofstream myfile;
    bool is_debug;
    bool isVerbose;

    NqueensSearch(int size, bool isVerbose) {
        boardSize = (unsigned) size;
        this->isVerbose = isVerbose;
    }

    void intialize(unsigned currentState[]) {
        int min = 0;
        int max = boardSize - 1;
        for (unsigned i = 0; i < boardSize; i++) {
            currentState[i] = rand() % (max - min + 1) + min;
        }

    }

    unsigned randomMax(unsigned max) {
        unsigned min = 0;
        return rand() % (max - min + 1) + min;
    }

    unsigned randomRowOrColumn() {
        return randomMax(boardSize - 1);
    }

    void debug(const string message) {
        if (is_debug) {
            myfile << message << endl;
        }
    }

    void enable_debug() {
        is_debug = true;
        if (is_debug) {
            myfile.open("debug.txt");
        }
    }

    void printBoard(const unsigned currentState[]) {
        string header;
        for (unsigned i = 0; i < boardSize - 1; i++) {
            header += "-";

        }
        header += to_string(iterations);
        cout << header << endl;


        for (unsigned i = 0; i < boardSize; i++) {

            string line;
            unsigned place = currentState[i];
            for (unsigned j = 0; j < boardSize; j++) {
                if (j == place) {
                    line += "Q";
                } else {
                    line += "*";
                }

            }
            cout << line << endl;

        }
    }



    bool isConflict(unsigned row, unsigned column, unsigned otherRow, unsigned otherColumn) {
        if (row == otherRow) {
            debug("same row " + to_string(row));
            return false;
        }
        unsigned rowDistance = abs((int) row - (int) otherRow);
        if (column == otherColumn) {
            return true;
        } else if (abs((int) column - (int) otherColumn) == rowDistance) {
            return true;
        }
        return false;
    }

    bool isGoal(const unsigned currentState[]) {
        bool result = true;
        for (unsigned row = 0; row < boardSize; row++) {
            for (unsigned otherRow = 0; otherRow < boardSize; otherRow++) {
                if (isConflict(row, currentState[row], otherRow, currentState[otherRow])) {
                    result = false;
                }
            }
        }

        return result;

    }

    unsigned getMinConflictColumn(const unsigned currentState[], unsigned row) {
        unsigned columnOfMinConflict = 0;
        unsigned queenColumn = currentState[row];
        unsigned minConflicts = numeric_limits<unsigned>::max();
        debug("getMinConflictColumn, row:" + to_string(row));

        for (unsigned column = 0; column < boardSize; column++) {
            unsigned conflicCout = 0;

            if (column == queenColumn) continue;
            for (unsigned otherRow = 0; otherRow < boardSize; otherRow++) {
                if (row == otherRow)//same row ignore
                {
                    //debug("same row "+to_string(row));
                    continue;
                }
                if (isConflict(row, column, otherRow, currentState[otherRow])) {
                    conflicCout++;
                }

            }
            if (conflicCout == 0) {
                debug("\t noflict at " + to_string(column) + " : " + to_string(row));
            }
            debug("Conflict at " + to_string(column) + ":" + to_string(row) + " = " + to_string(conflicCout));
            if (conflicCout < minConflicts) {
                debug("Conflict updated");
                minConflicts = conflicCout;
                columnOfMinConflict = column;
            }

        }

        return columnOfMinConflict;

    }



    void placeQueen(unsigned currentState[], unsigned row, unsigned column) {
        currentState[row] = column;
    }


    list<unsigned> rowsInConflict(const unsigned currentState[]) {
        list<unsigned> rowsInConflict; //TODO change to map

        for (unsigned row = 0; row < boardSize; row++) {
            for (unsigned otherRow = 0; otherRow < boardSize; otherRow++) {
                if (isConflict(row, currentState[row], otherRow, currentState[otherRow])) {
                    rowsInConflict.push_front(row);
                    debug("row in conflict " + to_string(row));
                    rowsInConflict.push_front(otherRow);
                    //return rowsInConflict;
                }
            }
        }

        return rowsInConflict;
    }

    bool update(unsigned currentState[]) {
                unsigned randomRow, column;

        list<unsigned> conflictRows = rowsInConflict(currentState);
        if (conflictRows.empty()) {
            return true;
        }

        list<unsigned>::iterator it = conflictRows.begin();
        std::advance(it, rand() % conflictRows.size());
        randomRow = (unsigned) *it;

        column = getMinConflictColumn(currentState, randomRow);
        placeQueen(currentState, randomRow, column);


        return false;

    }



    void solve_nqueen(unsigned size, bool isVerbose) {
        boardSize = size;
        unsigned rowSpace[size];




        //enable_debug();
        intialize(rowSpace);
        if (isVerbose) {
            printBoard(rowSpace);
        }


        while (!update(rowSpace)) {
            if (isVerbose) {
                printBoard(rowSpace);

            }
            if (iterations >= 1000) {
                cout << "Random restart." << endl;
                intialize(rowSpace);
                iterations = 0;
            }
            iterations++;
        }
        printBoard(rowSpace);




    }

};

/*
 * The main function.
 */
int main(int argc, char** argv) {

    int size;
    bool isVerbose = false, isArgValid = true;

    if (argc == 2) {
        size = atoi(argv[1]);
        isArgValid = (size > 0);
    } else if (argc == 3) {
        if (strcmp(argv[1], "-v") == 0) {
            isVerbose = true;
            size = atoi(argv[2]);
            isArgValid = (size > 0);
        } else {
            isArgValid = false;
        }
    } else {
        isArgValid = false;
    }

    if (!isArgValid) {
        cout << "Error in command line arguments." << endl;
        cout << "Usage: " << argv[0] << " [-v] n" << endl;
        cout << "where n is the number of queens and the size of the board (nxn)." << endl;
        cout << "The option -v enables the output of the intermediate states of" << endl;
        cout << "the search procedure." << endl;
        return 1;
    }

    NqueensSearch problem(size, isVerbose);
    problem.solve_nqueen(size, isVerbose);
    //solve_nqueen(size, isVerbose);

    return 0;
}

我正在实施Norque，S.，＆Peter，J. R. and。提到的nqueens最小冲突搜索。 （2014）。人工智能是一种现代方法。在皮尔逊（第58卷，第12期）中。作者...

Answer 1

正如我在评论中所说，如果您要尽量减少交换次数，从良好的初始配置开始至关重要。在我的nQueens实现中，我有3种不同的方法来为每个皇后生成初始行：