مسئله n وزیر با روش تپه نوردی، آموزش و کد
امروز ما می خواهیم با هم سوال N وزیر را باهم به روش تپه نوردی یا Hill climbing حل کنیم . اگر نمی دانید سوال N وزیر چیست به این (کد و الگوریتم هشت وزیر (n queens) با روش عقبگرد با ++C) پست ما مراجعه کنید که در آن این سوال را با روش back track حل کرده ایم.
روش تپه نوردی یا همان Hill climbing یک روش ابتکاری یا heuristic است. که می توان در آن با توجه به ابتکار خود راه حل های متفاوت و زیادی داشته باشیم.
اصل روش تپه نوردی یک تابع ارزیابی است که می گوید حالت فعلی مان (Current state) چه ارزشی دارد که این تابع یک تابع ابتکاری یا heuristic است .
قدم بعدی در این الگوریتم ساخت چندین حالت جدید از حالت فعلی است ، بع از اینکه ما حالت های جدید را ساختیم با استفاده از تابع ارزیابی مان می بینیم کدام یک از آن ها از حالت فعلیمان و سایر حالت های تولید شده بهتر است ، سپس حالت جدید را انتخاب می کنیم ، و همین کار را برای حالت جدید می کنیم تا جایی که به جواب برسیم!
تابع تولید حالت اولیه صفحه ی شطرنج – Initial Random Board Function
این تابع به صورت رندم یک صفحه ی شطرنج تولید می کند به طوری که در هر سطر یک وزیر وجود دارد.
int *board : یک آرایه ی یک بعدی است ، که خانه ی صفر آرایه نشان می دهد که در سطر صفر صفحه شطرنج وزیر در کدام ستون قرار دارد ، خانه ی یک آرایه نشان می دهد که در سطر یک شطرنج وزیر در کدام خانه است و همین طور به ترتیب تا خانه ی آخر آرایه.
int len : طول آرایه ی بالا را نشان می دهد که تعداد وزیر ها هم هست.
1 2 3 4 5 6 7 8 9 10 | 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 : طول آرایه ی بالا را نشان می دهد که تعداد وزیر ها هم هست.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | //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
این تابع حالت فعلی مان را می گیرد و این کار را انجام می دهد : ابتدا وزیر در سطر صفر صفحه ی شطرنج را در نظر می گیرید و بررسی می کند وزیر را به کدام خانه ستون در همان سطر ببریم تا تعداد زوج وزیر هایی با تعداد تهدید کمتری داشته باشیم ، اگر چند تا ستون پیدا کردیم که ارزش یکسانی داشتند یکی را رندم انتخاب می کنیم ، در مرحله ی بعد می آییم و و همین کار را برای وزیر سطر یک می کنیم تا آخرین وزیر.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | //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 را بر می گرداند. البته این تابع را با تابع قبل می توان یکی کرد ولی من اینطوری نوشتم تا واضح بشود.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | //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 جدید درست می کنیم و کار را ادامه می دهیم و این کار ادامه میابد تا زمانی که به جواب برسیم.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | 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 خروجی را روی صفحه ی نمایش نشان می دهد که آن به صورت زیر است :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | //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 را نوشته ام که خروجی را در فایل می ریزد ، کد آن را در زیر مشاهده می کنید :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | //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 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 | // 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 نوشتم که با استفاده از الگوریتم ژنتیک تا ۵۰۰ وزیر رو زیر یک دقیقه حل میکنه. اگه دوست داشتید ایمیل بزنید تا کدشو بدم بهتون
Reza_m_n_65@yahoo.com
سلام خوب هستین؟آقای مقیدنیا میشه کدی که با C# نوشتین که با استفاده از الگوریتم ژنتیک تا ۵۰۰ وزیر رو زیر یک دقیقه حل میکنه رو بهم بدین؟
استادم ازم خواسته به زبان جاوا این رو بنویسم ۵ نمره پایانی درسم هست میخواستم خواهش کنم میشه کدتون رو واسم بفرستین من ازش کمک بگیرم به جاوا بنویسمش؟
منتظر جوابتونم
مرسی
سلام.خسته نباشین.اگه یه نسخه پی دی افم بزارین برا پستاتون که بشه پستارو سیو کرد خیلی عالیتر میشه مرسی
سلام
ممنون از الگوریتم خوبتون.ولی میخواستم بدونم چرا اگه از فایل استفاده نشه خروجی به هم میریزه؟
چون ستون های صفحه نمایش محدوده اگر تعداد ستون ها بیشتر از ستون های صفحه نمایش باشه خوب همه چی جابجا می شه
با سلام
این کد تضمین میکند جواب را پیدا کند؟
به عبارت دیگر کامل است؟
همچنین تضمین میکند بهترین جواب را به ما بدهد یا به عبارتی بهینه است؟
این مسیله می خواهد n وزیر را در صفحه ی شطرنج بچیند، بهینه بودن نداریم، جواب می ده حتما.
سلام
نوشته خیلی خوبی بود. میخواستم بگم آیا با این روش میشه تمامی حالات رو پیدا کرد و چاپ کرد؟ مثلا ۸ تا وزیر ۹۲ حالت میتونن توی یه صفحه ۸×۸ قرار بگیرن ولی با این روش فقط ۱ حالت رو میتونیم پیدا کنیم.
با تشکر
درود ، با این روش نمی شه تمام حالات رو پیدا کرد، روش های ابتکاری یا همان تپه نوردی برای پیدا کردن یک جواب است نه تمام جواب ها ، چون ما تپه نوردی را برای مساله های سنگین محاسباتی استفاده می کنیم . ولی اگر بخواهید تمام گزینه ها را پیدا کنید به این پست بروید که با روش عقبگرد همه ی روش ها را پیدا می کند :
کد و حل معمای eight puzzle (پازل هشت) با روش Back tracking