n 个皇后的快速启发式算法 (n > 1000)

问题描述 投票：0回答：2

我写了两个程序：

  1. 将棋盘上的n个皇后放在一起，没有回溯算法的任何威胁。但这对于大 n 来说非常沉重。最后你可以运行 100 个皇后。
  2. 通过爬山算法将 n 个皇后放在棋盘上，没有任何威胁。这个算法比过去的解决方案更好，但是 300 个皇后需要 2 分钟，而且这次时间呈指数增长！

但我不知道要做得那么快！我想要更快的算法。

我想要更快的方式尽可能快地解决 1000 个皇后的问题。

这是我的爬山代码：

// N queen - Reset Repair Hill Climbing.cpp
// open-mind.ir

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <fstream>
#include <time.h>
#include <iomanip>


using namespace std;

//print solution in console
void printBoardinTerminal(int *board, int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            if (j == board[i])
            {
                cout << 1 << " ";
            }
            else
            {
                cout << 0 << " ";
            }
        }
        cout << endl;
    }
}

//print solution in File
void printBoardinFile(int *board, int len)
{
    ofstream fp("output.txt", ios::out);

    fp << "Answer for " << len << " queen: \n \n";

    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            fp << "----";
        }
        fp << "\n|";

        for (int j = 0; j < len; j++)
        {
            if (j == board[i])
            {
                fp << setw(4) << "* |" ;
            }
            else
            {
                fp << setw(4) << "  |";
            }
        }
        fp << "\n";
    }
}

//The number of queens couples who are threatened themself
int evaluate(int *board, int len)
{
    int score = 0;
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = i + 1; j < len; j++)
        {
            if (board[i] == board[j])
            {
                score++;
                continue;
            }
            if (board[i] - board[j] == i - j)
            {
                score++;
                continue;
            }
            if (board[i] - board[j] ==  j - i)
            {
                score++;
                continue;
            }
        }
    }
    return score;
}

//generate new state from current state 
int* generateBoard(int *board,int len)
{
    vector <int> choice;

    int temp;
    int score;
    int eval = evaluate(board, len);
    int k;

    int *boardOut;
    boardOut = new int [len];


    for (int i = 0; i < len; i++)
    {
            boardOut[i] = board[i];
    }

    for (int i = 0; i < len; i++)
    {
        choice.clear();

        choice.push_back(boardOut[i]);
        temp = boardOut[i];

        for (int j = 0; j < len; j++)
        {
            boardOut[i] = j;

            k = evaluate(boardOut, len);

            if (k == eval)
            {
                choice.push_back(j);
            }

            if (k < eval)
            {
                choice.clear();
                choice.push_back(j);
                eval = k;
            }
        }
        boardOut[i] = choice[rand() % choice.size()];
    }

    return boardOut;
}

//in this function , genarate new state by pervious function and if it has better value then replaces that by current state
bool findNextState(int *board, int len)
{
    int maineval = evaluate(board, len);

    int *tempBoard;

    tempBoard = generateBoard(board, len);

    if (evaluate(tempBoard, len) < maineval)
    {
        for (int p = 0; p < len; p++)
        {
            board[p] = tempBoard[p];
        }

        return  true;
    }

    return false;
}

// make random initial state , put one queen in each row
void initialRandomBoard(int * board, int len)
{
    bool access;
    int col;

    for (int i = 0; i < len; i++)
    {
        board[i] = rand() % len;
    }
}

//this function include a loop that call findNextState function , and do that until reach solution
//if findNextState function return NULL then we reset current state
void SolveNQueen(int len)
{
    cout << "The program is under process! wait!" << endl;

    int *board;
    board = new int[len];


    initialRandomBoard(board, len);

    while (evaluate(board, len) != 0)
    {
        if (!findNextState(board, len))
        {
            initialRandomBoard(board, len);
        }
    }


    //
    cout << endl << "Anwser for " << len << " queens: "<< endl << endl;
    printBoardinTerminal(board, len);
    printBoardinFile(board, len);
    //
}


int main()
{
    int n;
    srand(time(NULL));

    cout << "Enter  number \'N\', \'N\' indicate numbers of queens in \"N * N\" chess board: " << endl;
    cin >> n;

    if (n < 4)
    {
        cout << "\'n\' must be uper than 3!" << endl;
        exit(1);
    }

    SolveNQueen(n);

    cout << endl << "As well , you can see result in \"output.txt\"." << endl << endl;

    return 0;
}
c++ algorithm chess heuristics n-queens
2个回答
10
投票

注意：此答案假设您有兴趣寻找one有效的解决方案。如果您需要找到所有解决方案，这对您没有帮助。

Russell & Norvig 的《人工智能：现代方法》第二版在第 5 章：第 143 页的约束满足问题中提供了一个表格，比较了各种任务的各种约束满足问题算法。 （最新版本是第三版，约束满足问题现在好像是第6章了。）

根据他们的结果，最小冲突本地搜索启发式在 n

-Queens 问题测试的算法中得分最高，平均需要 4K 次检查，而回溯和前向检查则需要超过 40,000K 次检查。

算法非常简单：

选择初始（随机或预选）皇后分配

    当存在受威胁的皇后时（或者直到你厌倦了尝试......将其放入
  • for
    • 循环中以限制尝试次数是值得的）： 
  • 随机选择一个受威胁的女王
      将选定的皇后移至冲突最小化的方格
    在最后一步中，我假设每个皇后都被限制在她的列中，所以她只能更改列中的行。如果有几行可以最小化当前女王的冲突，您可以在其中随机选择。
就是这样。它是完全随机的，而且效果很好。

编辑：

我在这里有一个注释，关于当我实现这个算法时，我不记得我得到了多少

n

，说我知道我已经超过了 100。我没有找到我的旧代码，但我决定无论如何把一些东西放在一起。事实证明，这个方法远比我记忆中有效。以下是 10 个皇后的结果：

Starting Configuration: 14 0 2 13 12 17 10 14 14 2 9 8 11 10 6 16 0 7 10 8 Solution found Ending Configuration: 17 2 6 12 19 5 0 14 16 7 9 3 1 15 11 18 4 13 8 10 Elapsed time (sec): 0.00167 Number of moves: 227

在没有尝试优化代码的情况下，以下是我针对不同问题大小得到的大致时间：
Queens ~Time(sec) ====== ========== 100 0.03 200 0.12 500 1.42 1000 9.76 2000 72.32 5000 1062.39

我只运行了一次 5000 个皇后的最后一个，但在 18 分钟内找到解决方案比我预期的要快。

有一个封闭公式可以为 N 皇后问题找到一个解决方案。
0
投票
这是 C 中的实现：

#include "stdio.h" #include "stdlib.h" void push(int **v, int val) { **v = val; (*v)++; } void pushRange(int **v, int start, int stop, int step, int add1, int add2) { for (int i = start; i < stop; i += step) push(v, i); if (add1 >= 0) push(v, add1); if (add2 >= 0) push(v, add2); } void solveNQueens(int *queens, int len) { if (len % 6 == 2) { pushRange(&queens, 1, len, 2, 2, 0); pushRange(&queens, 6, len, 2, 4, -1); } else if (len % 6 == 3) { pushRange(&queens, 3, len, 2, 1, -1); pushRange(&queens, 4, len, 2, 0, 2); } else { pushRange(&queens, 1, len, 2, -1, -1); pushRange(&queens, 0, len, 2, -1, -1); } } void printBoard(int *queens, int len) { for (int row = 0; row < len; row++) { for (int col = 0; col < len; col++) { printf("%d ", col == queens[row]); } printf("\n"); } } int main() { int n = 9; int *queens = malloc(n * sizeof(int)); solveNQueens(queens, n); printBoard(queens, n); free(queens); return 0; } 




    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.