n وزیر با روش تپه نوردی – N queens by Hill climbing

fantasy-warrior-weapon-army-armor-sword-arms-shield

امروز ما می خواهیم با هم سوال N وزیر را باهم به روش تپه نوردی یا Hill climbing حل کنیم . اگر نمی دانید سوال N وزیر چیست به این (کد و الگوریتم هشت وزیر (n queens) با روش عقبگرد با ++C) پست ما مراجعه کنید که در آن این سوال را با روش back track حل کرده ایم.

روش تپه نوردی یا همان Hill climbing یک روش ابتکاری یا heuristic است. که می توان در آن با توجه به ابتکار خود راه حل های متفاوت و زیادی داشته باشیم.

اصل روش تپه نوردی یک تابع ارزیابی است که می گوید حالت فعلی مان  (Current state) چه ارزشی دارد که این تابع یک تابع ابتکاری یا heuristic است .

قدم بعدی در این الگوریتم ساخت چندین حالت جدید از حالت فعلی است ، بع از اینکه ما حالت های جدید را ساختیم با استفاده از تابع ارزیابی مان می بینیم کدام یک از آن ها از حالت فعلیمان و سایر حالت های تولید شده بهتر است ، سپس حالت جدید را انتخاب می کنیم ، و همین کار را برای حالت جدید می کنیم تا جایی که به جواب برسیم!

تابع تولید حالت اولیه صفحه ی شطرنج – Initial Random Board Function 

این تابع به صورت رندم یک صفحه ی شطرنج تولید می کند به طوری که در هر سطر یک وزیر وجود دارد.

int *board  : یک آرایه ی یک بعدی است ، که خانه ی صفر آرایه نشان می دهد که در سطر صفر صفحه شطرنج وزیر در کدام ستون قرار دارد ، خانه ی یک آرایه نشان می دهد که در سطر یک  شطرنج وزیر در کدام خانه است و همین طور به ترتیب تا خانه ی آخر آرایه.

int len : طول آرایه ی بالا را نشان می دهد که تعداد وزیر ها هم هست.

 

تابع ارزیابی برای n وزیر – evaluate function

تعداد زوج وزیر هایی که هم را تهدید می کنند تابع ارزیابی من برای این سوال است که کد آن را در پایین می بینید :

int *board  : یک آرایه ی یک بعدی است ، که خانه ی صفر آرایه نشان می دهد که در سطر صفر صفحه شطرنج وزیر در کدام ستون قرار دارد ، خانه ی یک آرایه نشان می دهد که در سطر یک  شطرنج وزیر در کدام خانه است و همین طور به ترتیب تا خانه ی آخر آرایه.

int len : طول آرایه ی بالا را نشان می دهد که تعداد وزیر ها هم هست.

 

 

تابع تولید یک حالت از حالت فعلی – generateBoard

این تابع  حالت فعلی مان را می گیرد و این کار را انجام می دهد : ابتدا وزیر در سطر صفر صفحه ی شطرنج را در نظر می گیرید و بررسی می کند وزیر را به کدام خانه ستون در همان سطر ببریم تا تعداد زوج وزیر هایی با تعداد تهدید کمتری داشته باشیم ، اگر چند تا ستون پیدا کردیم که ارزش یکسانی داشتند یکی را رندم انتخاب می کنیم ، در مرحله ی بعد می آییم و و همین کار را برای وزیر سطر یک می کنیم تا آخرین وزیر.

تابع تولید حالت بعدی –  find Next State

این تابع با استفاده از تابع قبلی یک حالت جدید تولید می کند و در صورتی که حالت جدید بهتر از حالت کنونیمان باشد آن را جای گزین حالت کنونیمان می کند و true را بر می گرداند اگر بهتر از حالت فعلیمان نباشد False را بر می گرداند. البته این تابع را با تابع قبل می توان یکی کرد ولی من اینطوری نوشتم تا واضح بشود.

 

تابع حل معمای وزیر – solved N queen function

این تابع عدد صحیح len را می گیرد که تعداد وزیر ها است که قرار است در یک صفحه ی شطرنج len * len قرار بگیرد.

مرتبا تابع find next state را برای آن فرا می خواند تا به جواب برسد ، ولی اگر تابع  find next stateمقدار false را برگرداند یعنی دیگر می نمی توانیم آن حالت را بهتر کنیم در نتیجه دوباره به صورت رندم یک state جدید درست می کنیم و کار را ادامه می دهیم و این کار ادامه میابد تا زمانی که به جواب برسیم.

تابع چاپ خروجی در command box و file

تابع printBoardinTerminal خروجی را روی صفحه ی نمایش نشان می دهد که آن به صورت زیر است :

تابع بالا برای اعداد کم مثل ۳۰ وزیر خوب است چون برای تعداد وزیر بالا به درستی نمی توان وزیر ها را نشان داد و خروجی به هم می ریزد به همین خاطر تابع printBoardinFile را نوشته ام که خروجی را در فایل می ریزد ، کد آن را در زیر مشاهده می کنید :

 

این برنامه برای تعداد وزیر های زیر ۱۰۰ تا در کسری از ثانیه جواب می دهد و برای ۱۰۰ وزیر در حدود ۵ ثانیه جواب می دهد و برای ۲۰۰ وزیر در حدود ۲ دقیقه جواب می دهد و برای ۳۰۰ وزیر در حدود ۵ دقیقه زمان می برد و هرچه تعداد وزیر ها را بیشتر کنید این زمان exponetially زیاد می شود.

نمونه ای از خروجی در command box :

Untitled picture

 

نمونه ای از خروجی در فایل:
output

با ایجاد تغییرات می توانید این برنامه را خیلی بهتر کنید که اگر این کار را کردید برنامه تان را برای ما بفرستید تا پست را آپدیت کنیم و برنامه تان را ایجا قرار دهیم ، همچنین خودم هنوز در حال کار روی برنامه هستم که در صورت بهبود دادن آن ، برنامه جدید را در همین جا قرار می دهم.

 

و در آخر هم کد و برنامه ی کلی حل سوال N وزیر با استفاذه از روش Hill climbing :

 

 

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۹ comments

Leave a Reply

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *