پایان نامه طراحی الگوریتم فراابتکاری برای زمانبندی ماشین های موازی نامرتبط با تابع هدف چندگانه در محیط تولید بهنگام

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

فرمت فایل : WORD (قابل ویرایش)

تعداد صفحات:114

پایان نامه مقطع کارشناسی ارشد
مهندسی صنایع- مهندسی سیستم های اقتصادی اجتماعی

فهرست مطالب:
فصل اول مقدمه و کلیات    1
1-1.    مقدمه    2
1-2. تعریف مسأله زمانبندی    5
1-3. ضرورت انجام تحقیق    7
1-4. اهداف تحقیق    8
1-5. مفروضات مسئله    9
1-6. جنبه های نوآوری تحقیق    10
1-7. محتوای تحقیق    10
فصل دوم ادبیات و پیشینه تحقیق    11
2-1. مقدمه    12
2-2. طبقه بندی محیط های زمانبندی    15
2-3. مسائل ماشینهای موازی    19
2-3-1.  زمان نصب و آماده سازی    20
2-3-2. دسترسی محدود به ماشینها    26
2-3-3. زمان دسترسی متفاوت به کارها    27
2-4. مسائل با تمرکز بر موعد تحویل برای کارها    27
2-4-1. زمان تکمیل کارها    29
2-4-2. زمانهای زودکرد و دیرکرد    29
2-5. مروری بر رویکرد و اصول سیستم تولیدی  بهنگام    31
2-6. توالی ماشینﻫای موازی با معیارهای زودکرد و دیرکرد    33
2-7. جمع بندی    34
فصل سوم مدل ریاضی و بهینه سازی چند هدفه    36
3-1. مقدمه    37
3-2. تعریف مسئله    37
3-2-1. مفروضات مسئله    39
3-3. مدل پیشنهادی    39
3-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم    40
3-3-2.  پارامترهای ورودی    40
3-3-3.  توابع هدف    41
3-3-4.  محدودیتها    41
3-4. اعتبارسنجی مدل    43
3-5. پیچیدگی مسئله    45
3-6  بهینه سازی چند معیاره    47
3-6-1. ارتباط غالب    47
3-6-2. نقاط بهینه موضعی    48
3-6-3. نقاط بهینه سراسری    48
3-6-4. مرز بهینه    48
3-7. روشهای بهینه سازی    49
3-7-1. روشهای اسکالر    49
3-7-2. روش مجموع وزنی    51
3-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر    54
3-7-3. روش محدودیت-ε    55
3-7-3-1. طراحی روش محدودیت – ε برای حل مسأله    57
3-7-4. روشهای عکس العملی    57
3-7-5. روش های مبتنی بر منطق فازی    58
3-7-6. روش های فرا ابتکاری    59
3-7-7. الگوریتم NSGA-II    60
3-7-7-1. مرتب سازی سریع    61
3-7-7-2. عملگر گزینش تورنمنت تراکمی    63
3-7-7-3. فاصله تراکمی    63
3-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله    65
3-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله    70
3-8. مقایسه روش های بهینه سازی چند هدفه    71
3-8-1.  شاخص متوسط فاصله از نقطه ایدهآل    73
3-8-2.  شاخص نرخ دستیابی به توابع هدف    74
3-8-3.  شاخص گستردگی جواب های غیر مغلوب (SNS)    74
3-8-4. شاخص یکنواختی فضا    74
3-9. جمعﺑندی    75
فصل چهارم محاسبات و نتایج  تحقیق    77
4‐1. مقدمه    78
4‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها    79
4-3. الگوریتمهای  NSGA-II,CENSGA    80
4-4. روش مجموع وزنی    80
4-5. روش محدودیت-ε    81
4‐6. ساختار مسائل    82
4‐7. معیارهای ارزیابی الگوریتمها    83
4‐8. مسائل با ابعاد کوچک و متوسط    83
4-8-1. نتایج آزمایشات مسائل کوچک و متوسط    83
4‐9. مسائل با ابعاد بزرگ    90
4‐10. نتایج محاسباتی    90
4‐11. جمعﺑندی    96
فصل پنجم نتیجه گیری و پیشنهادات    97
5‐1. مقدمه    98
5‐2. نتیجهﮔیری    99
5‐3. پیشنهادهای آتی    100
فهرست منابع و مراجع    102
    
فهرست جداول
جدول 2-1. محیط¬های کارگاهی (نماد α)     13
جدول 2-2. توابع هدف رایج در ادبیات     15
جدول 3-1. زمان¬های پردازش،موعدهای تحویل و زمان دسترسی    44
جدول 3-2. زمان نصب ماشین یک و دو برای کارهای مختلف     44
جدول 4-1.  حدهای بالا برای مسائل مختلف     82
جدول 4-2.  جوابهای نامغلوب مربوط به مسأله 5j2m به تفکیک روش ها    84
جدول 4-3.  ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j2m     85
جدول 4-4.  جوابهای نامغلوب مربوط به مسأله 5j3m به تفکیک روش ها    85
جدول 4-5. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j3m     86
جدول 4-6. جوابهای نامغلوب مربوط به مسأله 8j2m به تفکیک روش ها    87
جدول 4-7.  ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m    88
جدول 4-8 . جوابهای نامغلوب مربوط به مسأله 8j3m به تفکیک روش ها     89
جدول 4-9.  ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j3m     90
جدول 4-10 نتایج شاخص¬های متریک برای الگوریتم CENSGAوNSGA-II     91
جدول 4- 11.  ارزیابی آماری الگوریتم¬های فراابتکاری بکار گرفته شده     94

فهرست شکل¬ها و نمودارها
شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید     19
شکل 3-1. سلسله¬مراتب پیچیدگی محیط¬های کارگاهی در مسائل زمان¬بندی    46
شکل 3-2. سلسله¬مراتب پیچیدگی توابع هدف در مسائل زمان¬بندی    46
شکل 3-3. نقاط بهینه موضعی     48
شکل 3-4.  رابطه فضای جواب و ارتباط غالب     48
شکل 3-5.  نمایش روش مجموع وزنی با مرز بهینه پارتو محدب     52
شکل 3-6.  نمایش روش مجموع وزنی با مرز بهینه پارتو غیر محدب     54
شکل 3-7. روش محدودیت- ε     56
شکل 3-8.  نمایش الگوریتم NSGAII    61
شکل 3-9.  محاسبه فاصله تراکمی     64
شکل 3-10.  ساختار کروموزوم    66
شکل 3-11.  نحوه ایجاد جمعیت اولیه     67
شکل 3-12.  نحوه عملکرد عملگر تقاطع     69
شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 3    69
شکل 3-14. نحوه عملکرد عملگر جهش     70
شکل 3-15. استراتژی انتخاب در الگوریتم CENSGA  و NSGA-II     71
شکل 3-16.  دو هدف در بهینه سازی چند هدفه    72
شکل 3-17.  یک مجموعه ایده آل از جواب های نامغلوب    72
شکل 3-18.  همگرائی خوب، اما تنوع ضعیف (الگوریتم 1)    73
شکل 3-19.  همگرائی ضعیف، اما تنوع خوب (الگوریتم 2)    73
شکل 4-1.  نمایش جوابهای نامغلوب ε-محدودیت مسأله 5j2m     84
شکل 4-2.  نمایش جوابهای نامغلوب روش وزنی مسأله 5j2m     84
شکل 4-3. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m    86
شکل 4-4.  نمایش جوابهای نامغلوب  روش محدودیت-ε مسأله 5j3m    86
شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m    88
شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j2m     88
شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m     89
شکل 4-8 .  نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j3m    89
شکل 4- 9  نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل    92
شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتم¬های  CENSGA,NSGA-II     93
شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها     95

چکیده
    در طول دهه گذشته، گسترش الگوریتم¬های فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب کرد. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامه¬ریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتم¬های بهینه سازی که برای مسائل گوناگون به کار برده می¬شدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف¬ ها را ترکیب می¬کردند و مسائل را با رویکرد تک هدفه حل می¬کردند. البته بعضی از محققان الگوریتم¬های پارتویی به کار می¬برند. در این تحقیق یک برنامه ریزی ماشین¬های موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه می-کنند. برای حل مدل و اعتبار سنجی آن از الگوریتم¬ مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتم¬هایی که از روش شاخه و کران برای حل استفاده می¬کنند قادر به حل مسائل بزرگ در زمان معقول نمی-باشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جمله¬ای سخت (NP-Hard) می¬باشد الگوربتم فراابتکاری (CENSGA)معرفی شده است. الگوریتم ارائه شده را  با استفاده از شاخص¬های آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده است که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA)  می¬باشد.  
کلمات کلیدی: تولید بهنگام; زمان آماده¬سازی وابسته به توالی;  کنترل نخبه¬گرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.

سورس کد الگوریتم کوله پشتی

اختصاصی از کوشا فایل سورس کد الگوریتم کوله پشتی دانلود با لینک مستقیم و پرسرعت .

تأثیر پارامترهای الگوریتم PSO در طراحی بهینه سیستم های توزیع آب

اختصاصی از کوشا فایل تأثیر پارامترهای الگوریتم PSO در طراحی بهینه سیستم های توزیع آب دانلود با لینک مستقیم و پرسرعت .

• مقاله با عنوان: تأثیر پارامترهای الگوریتم PSO در طراحی بهینه سیستم های توزیع آب 

• نویسندگان: علیرضا مقدم ، امین علیزاده ، علی نقی ضیایی ، علیرضا فرید حسینی ، دانیال فلاح هروی 

• محل انتشار: هشتمین کنگره ملی مهندسی عمران - دانشگاه صنعتی نوشیروانی بابل - 17 و 18 اردیبهشت 93  

• محور: سازه های هیدرولیکی 

• فرمت فایل: PDF و شامل 8 صفحه می‌باشد.

چکیــــده:

طراحی بهینه سیستم‌های توزیع آب یکی از مسائل پیچیده بهینه سازی می‌باشد که محققان در دهه‌های اخیر الگوریتم‌های متفاوتی برای حل آن ارائه داده‌اند. یکی از بحث‌های مهم در استفاده از این الگوریتم‌ها تعیین پارامترها و عملگرهای آنها برای رسیدن به بهینه جهانی است و در اکثر این روش‌ها تعداد زیاد پارامترها باعث کاربردی نشدن آنها می‌شود. در این مقاله ضمن معرفی و کاربرد الگوریتم PSO در بهینه سازی شبکه‌های توزیع آب، تأثیر رفتار پارامترها و عملگرهای این الگوریتم در حل مسأله بهینه سازی شبکه شناخته شده هانوی مورد بحث و تحلیل گرفت. نتایج حاصله نشان می‌دهد که الگوریتم PSO با تعداد پارامترهای اندکی که دارد از سرعت همگرایی بسیار بالایی نیز برخوردار است و قادر است راه حل بهینه‌تر در طراحی شبکه‌های توزیع آب را در مدت زمان کمتری نسبت به سایر الگوریتم‌ها را ارائه دهد.

________________________________

** توجه: خواهشمندیم در صورت هرگونه مشکل در روند خرید و دریافت فایل از طریق بخش پشتیبانی در سایت مشکل خود را گزارش دهید. **

** توجه: در صورت مشکل در باز شدن فایل PDF مقالات نام فایل را به انگلیسی Rename کنید. **

** درخواست مقالات کنفرانس‌ها و همایش‌ها: با ارسال عنوان مقالات درخواستی خود به ایمیل [e-mail] پس از قرار گرفتن مقالات در سایت به راحتی اقدام به خرید و دریافت مقالات مورد نظر خود نمایید. **

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

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

• مقاله با عنوان: بهینه سازی قاب دوبعدی با استفاده از ترکیب الگوریتم جامعه پرندگان و مدل جایگزین فرآیند گوسی تحت بار زلزله 

• نویسندگان: محسنه اسدی ، سعید شجاعی ، پیمان ترکزاده 

• محل انتشار: هشتمین کنگره ملی مهندسی عمران - دانشگاه صنعتی نوشیروانی بابل - 17 و 18 اردیبهشت 93  

• محور: سازه های فولادی 

• فرمت فایل: PDF و شامل 7 صفحه می‌باشد.

چکیــــده:

در بهینه سازی دینامیکی قاب‌ها برای بدست آوردن پاسخ مسئله نیازمند تحلیل سازه در هر نسل هستیم که زمان زیادی را می‌طلبد و با افزایش زمان و درجات آزادی، بیشتر نیز می‌شوند. روش‌های جایگزین با برقراری یک رابطه تقریبی بین ورودی‌ها و خروجی‌های مسئله، جوابی نزدیک به حل مستقیم را در زمانی کوتاهتر بدست می‌دهند. از میان تکنیک‌های مختلف ساخت مدل جایگزین، روش فرآیند گوسی (GP) عملکرد مناسبی از خود نشان داده است. در این تحقیق روشی برای ترکیب مدل‌های جایگزین در راستای تسریع الگوریتم‌های فراابتکاری برای بهینه سازی قاب تحت بار زلزله ارائه می‌گردد. در ابتدا، با استفاده از روش مستقیم، سازه موردنظر را تحلیل دینامیکی کرده و نتایج را ذخیره می‌کنیم که در نهایت از آنها برای آموزش روش تقریبی استفاده می‌کنیم. با شروع به کار الگوریتم بهینه ساز (PSO) بجای استفاده از روش مستقیم، از روش تقریبی فرآیند گوسی (GP) استفاده می‌کنیم.

مقدمه:

بهینه سازی یعنی بهترین جواب برای هر نوع مسئله‌ای در حالی که محدودیت‌های مشخصی برای آن وجود داشته باشد. امروزه با وجود مسائل با ابعاد بزرگ و پیچیده و با توجه به اهمیت زمان و دقت، روش‌های بهینه سازی قدیمی دیگر توانایی حل مسائل بزرگ را ندارند. به همین دلیل نیاز به الگوریتم‌های تکاملی روز به روز بیشتر می‌شود. الگوریتم‌های که هم باعث صرفه جویی در زمان می‌شوند و هم به همگرایی به بهینه سراسری و گریز از بهینه محلی، منجر می‌شود. الگوریتم اجتماع ذرات یکی از این الگوریتم ها می‌باشد و از جدیدترین روش‌های جستجو می‌باشد. در این الگوریتم که توسط دکتر راسل ابرهات و دکتر جیمز کندی در 1995 ارائه شده است و از رفتار جمعی پرندگان و ماهی‌ها الهام گرفته شده است، فرآیند حرکت پرندگان به سمت منبع غذا یک پدیده اتفاقی طبیعی است که باعث می‌شود هر پرنده در گروه با سرعت و جهت خاص خود حرکت کند و موقعیت اولیه خود را در گروه بهبود دهد. بردار سرعت براساس حافظه ذخیره شده به وسیله هر پرنده بهبود می‌یابد که این حافظه اطلاعات شخصی هر فرد می‌باشد و از طرف دیگر موقعیت هر ذره در گروه با توجه به رفتار کلی گروه بهبود می‌یابد و گروه در مسیر جستجوی خود به مناطق بهتری دست می‌یابد و این چرخه بهبود موقعیت هر ذره و متعاقباً بهبود موقعیت کل گروه ادامه دارد تا گروه به بهترین نقطه (منبع غذا) برسد.

الگوریتم ژنتیک نیز یک روش بهینه سازی از طبیعت جاندار است که می‌توان از آن بعنوان یک روش عددی، جستجوی مستقیم و تصادفی نام برد. اساسی‌ترین اصل تکامل وراثت است، هرنسل خصوصیات نسل قبلی را به ارث می برد و به نسل بعد انتقال می دهد. جان هالند 1967 ایده استفاده از الگوریتم ژنتیک را در بهینه سازی‌های مهندسی را مطرح کرد. در این روش، ابتدا برای تعداد ثابت که جمعیت نامیده می‌شود مجموعه ای از پارامترهای هدف بصورت اتفاقی تولید می‌شود. پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می‌دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می‌کنیم تا مناسب ترین نسل‌های والد انتخاب شوند. سپس با فراخوانی عملگرهای ژنتیک از جمله جهش و انتخاب نسل بعدی را شکل می‌دهیم و در پایان هر مرحله نسل جدید ایجاده شده را با نسل‌های قبلی جایگزین می‌نماید. این روال تا برقراری معیار همگرایی ادامه داده خواهد شد.

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

________________________________

** توجه: خواهشمندیم در صورت هرگونه مشکل در روند خرید و دریافت فایل از طریق بخش پشتیبانی در سایت مشکل خود را گزارش دهید. **

** توجه: در صورت مشکل در باز شدن فایل PDF مقالات نام فایل را به انگلیسی Rename کنید. **

** درخواست مقالات کنفرانس‌ها و همایش‌ها: با ارسال عنوان مقالات درخواستی خود به ایمیل [e-mail] پس از قرار گرفتن مقالات در سایت به راحتی اقدام به خرید و دریافت مقالات مورد نظر خود نمایید. **

الگوریتم و سورس کد مسئله هشت وزیر ( 8 وزیر )

اختصاصی از کوشا فایل الگوریتم و سورس کد مسئله هشت وزیر ( 8 وزیر ) دانلود با لینک مستقیم و پرسرعت .

مساله هشت وزیر از جمله مسائل پرمخاطب مباحث طراحی الگوریتم است. ۸  مهره وزیر رو روی صفحه شطرنج چنان بچینید که نتونن همدیگه رو تهدید کنن.

برای افرادی که با بازی شطرنج آشنایی ندارن:

وزیر مهره ای از مهره های بازی شطرنجه که می تونه در تمامی 8 جهت هر تعداد خانه – تا زمانی که مهره ای مانع نباشه – حرکت کنه و اگه در یکی از این خانه ها مهره حریف قرار داشته باشه تهدیدش کنه.

مساله هشت وزیر :  ما مساله رو در حالت کلی در نظر می گیریم. یعنی زمانی که ابعاد صفحه شطرنج n در n و تعداد مهره ها n هستش. ( n > 3 ) روشهای مختلفی برای پیدا کردن جواب وجود داره. یکی از این روشها چیدن تصادفی مهره ها روی صفحه شطرنجه! به عبارت دیگه n مهره رو به صورت تصادفی در خانه های مختلف صفحه قرار می دیم و بررسی می کنیم که آیا شرط مساله رو برآورده می کنن یا نه؟ این روش بسیار سریع ما رو به جواب می رسونه. اما ایرادی که داره نمی شه مطمئن بود بشه به همه حالتهای چینش دست پیدا کرد. در صفحه 8 در 8 شطرنج این مساله 92 جواب مختلف داره. شما ممکنه روش تصادفی رو هزار بار به کار ببرید، اما نتونید همه 92 حالت ممکنه رو به دست بیارید. این روش زمانی مفیده که پیدا کردن یه جواب برای ما کافی باشه.

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

برای پیاده سازی چنین الگوریتمی و تشخیص اینکه چه خانه هایی از سطر امن هستن روشهای مختلفی وجود داره. ساده ترینشون اینه که هر بار تمامی خانه هایی رو که امکان تهدید شدن از اونها وجود داره بررسی کنیم تا از قرار نداشتن مهره وزیر در اونها مطمئن باشیم. اما این روش اصلا کارا و بهینه نیست.

روش دیگه تعریف کردن صفحه شطرنج به صورت یه آرایه n در n هستش که خونه های امن و غیر امن با علامتگذاری مشخص می شن. هر بار که مهره ای رو صفحه قرار می گیره تمام خونه هایی که توسط این مهره تهدید می شن به صورت غیر امن علامتگذاری می شن. به این ترتیب می شه فهمید که هر خونه با توجه به چینش مهره های قبلی امن هست یا نه؟ اما این روش هم معایبی داره که باعث می شه به روش سوم رجوع کنیم. برای آشنایی با این معایب کافیه سعی کنید کد برنامه رو بنویسید!

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

کدی که به زبان ++C درباره این مساله نوشته شده با استفاده از روش سوم تعداد جوابهای ممکن – و نه خود جوابها – برای مقادیر مختلف n رو مشخص می کنه. به عنوان مثال اگر n رو 8 وارد کنید خروجی برنامه 92 خواهد بود. توصیه می کنم برای nهای بزرگ برنامه رو امتحان نکنید! اگر n رو 16 وارد کنید بعد از گذشتن زمان زیادی عدد 14772512 روی صفحه نمایش چاپ می شه. یعنی در صفحه شطرنج 16 در 16 حدود ۱۵ میلیون حالت مختلف برای چیدمان صحیح وجود داره!!