在 n 个皇后主要冲突搜索上表现不佳

我正在实施 nqueens min-conflict 搜索，如所述

Norvig, S., & Peter, J. R. and. (2014). Artificial Intelligence A Modern Approach. In Pearson (Vol. 58, Issue 12).

作者提到，仅此启发式就非常有效：

然而，当我实现它时，我无法在一分钟内解决超过 5000 个问题。虽然作者在 50 次迭代中实现了百万皇后的速度，但我的实现通常会超过 1000 次迭代以实现 5000 皇后。另一个问题 https://stackoverflow.com/questions/27697929/fast-heuristic-algorithm-for-n-queens-n-1000提到了类似的结果。

关于我做错了什么有什么想法吗？是算法问题还是我使用了不应该使用的循环？

update()顺便说一下，这是主要方法。

    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) {

        unsigned rowSpace[size];






        while (!update(rowSpace)) {

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




    }

};

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

1. 对于每个皇后，选择一个随机行
2. 创建 1..n 中与每个皇后的行号相对应的数字的排列
3. 将每个皇后放在冲突最少的行，随机打破平局

所有这些方法都将每个皇后限制在单个列中。第三种方法重用了我在执行交换时查找新目标行所用的函数。

以下是针对每种初始配置在 5000 个皇后上运行的一些示例：

# Board initialized by random rows
Number of queens = 5000, 100 reps
Average time per board: 1.57167
Average number of swaps: 3160.87

# Board initialized by shuffle
Number of queens = 5000, 100 reps
Average time per board: 1.17037
Average number of swaps: 2445.96

# Board initialized by min-conflict
Number of queens = 5000, 100 reps
Average time per board: 1.23296
Average number of swaps: 49.97

正如您所看到的，方法 3 为我们提供了目标交换次数，而其他方法则需要更多。事实上，此方法所需的交换次数从大约 1000 个皇后开始是一致的。

有趣的是，每种方法所花费的总时间与交换次数的变化相差不大。 （所有时间都包括设置初始棋盘和移动皇后。）