امروز ما می خواهیم با هم سوال N وزیر را باهم به روش تپه نوردی یا Hill climbing حل کنیم . اگر نمی دانید سوال N وزیر چیست به این (کد و الگوریتم هشت وزیر (n queens) با روش عقبگرد با ++C) پست ما مراجعه کنید که در آن این سوال را با روش back track حل کرده ایم.
روش تپه نوردی یا همان Hill climbing یک روش ابتکاری یا heuristic است. که می توان در آن با توجه به ابتکار خود راه حل های متفاوت و زیادی داشته باشیم.
اصل روش تپه نوردی یک تابع ارزیابی است که می گوید حالت فعلی مان (Current state) چه ارزشی دارد که این تابع یک تابع ابتکاری یا heuristic است .
قدم بعدی در این الگوریتم ساخت چندین حالت جدید از حالت فعلی است ، بع از اینکه ما حالت های جدید را ساختیم با استفاده از تابع ارزیابی مان می بینیم کدام یک از آن ها از حالت فعلیمان و سایر حالت های تولید شده بهتر است ، سپس حالت جدید را انتخاب می کنیم ، و همین کار را برای حالت جدید می کنیم تا جایی که به جواب برسیم!
تابع تولید حالت اولیه صفحه ی شطرنج – Initial Random Board Function
این تابع به صورت رندم یک صفحه ی شطرنج تولید می کند به طوری که در هر سطر یک وزیر وجود دارد.
int *board : یک آرایه ی یک بعدی است ، که خانه ی صفر آرایه نشان می دهد که در سطر صفر صفحه شطرنج وزیر در کدام ستون قرار دارد ، خانه ی یک آرایه نشان می دهد که در سطر یک شطرنج وزیر در کدام خانه است و همین طور به ترتیب تا خانه ی آخر آرایه.
int len : طول آرایه ی بالا را نشان می دهد که تعداد وزیر ها هم هست.
void initialRandomBoard(int * board, int len)
{
bool access;
int col;
for (int i = 0; i < len; i++)
{
board[i] = rand() % len;
}
}
تابع ارزیابی برای n وزیر – evaluate function
تعداد زوج وزیر هایی که هم را تهدید می کنند تابع ارزیابی من برای این سوال است که کد آن را در پایین می بینید :
int *board : یک آرایه ی یک بعدی است ، که خانه ی صفر آرایه نشان می دهد که در سطر صفر صفحه شطرنج وزیر در کدام ستون قرار دارد ، خانه ی یک آرایه نشان می دهد که در سطر یک شطرنج وزیر در کدام خانه است و همین طور به ترتیب تا خانه ی آخر آرایه.
int len : طول آرایه ی بالا را نشان می دهد که تعداد وزیر ها هم هست.
//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;
}
تابع تولید یک حالت از حالت فعلی – generateBoard
این تابع حالت فعلی مان را می گیرد و این کار را انجام می دهد : ابتدا وزیر در سطر صفر صفحه ی شطرنج را در نظر می گیرید و بررسی می کند وزیر را به کدام خانه ستون در همان سطر ببریم تا تعداد زوج وزیر هایی با تعداد تهدید کمتری داشته باشیم ، اگر چند تا ستون پیدا کردیم که ارزش یکسانی داشتند یکی را رندم انتخاب می کنیم ، در مرحله ی بعد می آییم و و همین کار را برای وزیر سطر یک می کنیم تا آخرین وزیر.
//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;
}
تابع تولید حالت بعدی – find Next State
این تابع با استفاده از تابع قبلی یک حالت جدید تولید می کند و در صورتی که حالت جدید بهتر از حالت کنونیمان باشد آن را جای گزین حالت کنونیمان می کند و true را بر می گرداند اگر بهتر از حالت فعلیمان نباشد False را بر می گرداند. البته این تابع را با تابع قبل می توان یکی کرد ولی من اینطوری نوشتم تا واضح بشود.
//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;
}
تابع حل معمای وزیر – solved N queen function
این تابع عدد صحیح len را می گیرد که تعداد وزیر ها است که قرار است در یک صفحه ی شطرنج len * len قرار بگیرد.
مرتبا تابع find next state را برای آن فرا می خواند تا به جواب برسد ، ولی اگر تابع find next stateمقدار false را برگرداند یعنی دیگر می نمی توانیم آن حالت را بهتر کنیم در نتیجه دوباره به صورت رندم یک state جدید درست می کنیم و کار را ادامه می دهیم و این کار ادامه میابد تا زمانی که به جواب برسیم.
void SolveNQueen(int len)
{
cout << "The program is under process! wait!" << endl;
int numberOfTry = 0;
int *board;
board = new int[len];
initialRandomBoard(board, len);
while (evaluate(board, len) != 0)
{
if (numberOfTry > len * 3)
{
numberOfTry = 0;
initialRandomBoard(board, len);
}
if (!findNextState(board, len))
{
initialRandomBoard(board, len);
numberOfTry = 0;
}
numberOfTry++;
}
//
cout << endl << "Anwser for " << len << " queens: "<< endl << endl;
printBoardinTerminal(board, len);
printBoardinFile(board, len);
//
}
تابع چاپ خروجی در command box و file
تابع printBoardinTerminal خروجی را روی صفحه ی نمایش نشان می دهد که آن به صورت زیر است :
//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;
}
}
تابع بالا برای اعداد کم مثل ۳۰ وزیر خوب است چون برای تعداد وزیر بالا به درستی نمی توان وزیر ها را نشان داد و خروجی به هم می ریزد به همین خاطر تابع printBoardinFile را نوشته ام که خروجی را در فایل می ریزد ، کد آن را در زیر مشاهده می کنید :
//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";
}
}
این برنامه برای تعداد وزیر های زیر ۱۰۰ تا در کسری از ثانیه جواب می دهد و برای ۱۰۰ وزیر در حدود ۵ ثانیه جواب می دهد و برای ۲۰۰ وزیر در حدود ۲ دقیقه جواب می دهد و برای ۳۰۰ وزیر در حدود ۵ دقیقه زمان می برد و هرچه تعداد وزیر ها را بیشتر کنید این زمان exponetially زیاد می شود.
نمونه ای از خروجی در command box :
نمونه ای از خروجی در فایل:
با ایجاد تغییرات می توانید این برنامه را خیلی بهتر کنید که اگر این کار را کردید برنامه تان را برای ما بفرستید تا پست را آپدیت کنیم و برنامه تان را ایجا قرار دهیم ، همچنین خودم هنوز در حال کار روی برنامه هستم که در صورت بهبود دادن آن ، برنامه جدید را در همین جا قرار می دهم.
و در آخر هم کد و برنامه ی کلی حل سوال N وزیر با استفاذه از روش Hill climbing :
// 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;
}
