быстрый эвристический алгоритм для n королев (n & gt; 1000)

Я пишу две программы:

  1. собрать n ферзей на шахматной доске, не угрожая алгоритмом возврата. но это очень тяжело для большого п. наконец, вы можете запустить это за 100 королев.
  2. собрать n ферзей на шахматной доске без какой-либо угрозы по алгоритму восхождения на холм. этот алгоритм лучше, чем в прошлом решении, но это займет 2 минуты для 300 королев и на этот раз увеличится в геометрической прогрессии!

Но у меня не было никакой идеи сделать это быстро! Я хочу алгоритм для этого быстрее.

Я хочу быстрее решить проблему как можно быстрее за 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;
}

2

Решение

Примечание: этот ответ предполагает, что вы заинтересованы в поиске один правильное решение. Если вам нужно найти все решения, это не поможет вам.

Искусственный интеллект: современный подход, Второе издание Рассел & В главе 5 «Проблемы удовлетворения ограничений» на странице 143 Norvig сравнивает различные алгоритмы задачи удовлетворения ограничений для различных задач. (Последним выпуском является третье издание, и похоже, что проблемы удовлетворенности ограничениями теперь есть в главе 6.)

Согласно их результатам, минимальный конфликт эвристики локального поиска получил наибольшее количество баллов из алгоритмов, протестированных на N-Проблема с ферзями, требующая в среднем 4 000 проверок по сравнению с> 40 000 000 проверками для возврата и проверки вперед.

Алгоритм довольно прост:

  • выберите начальное (случайное или предварительно выбранное) назначение королев
  • в то время как есть угрожаемые королевы (или пока вы не устанете пытаться … стоит поставить это в 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 минут быстрее, чем я ожидал.

7

Другие решения


По вопросам рекламы [email protected]