 |
انجمن را در گوگل محبوب کنيد :
|
|||||||
 |
| تبليغات سايت | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
  |
|
|
LinkBack | ابزارهاي تاپيک | نحوه نمايش |
۰۸-۱-۱۳۸۸, ۱۱:۳۵ قبل از ظهر
|
#1 (لینک دائم) |
|
Administrator
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
 |
حل مسئله 8 وزير(8Queen) با روش هاي مختلف!
دوستان بياييد مسئله 8 وزير را با روش هاي مختلف در اينجا با هم حل کنيم
 با استفاده از روشهايي از قبيل: الگوريتم ژنتيک جستجوي محلي الگوريتم عقبگرد مسئله ارضاي محدوديت جستجوي تپه نوردي و غيره 
|
|
|
| از Astaraki تشكر كرده اند: | advanture (۰۱-۳۱-۱۳۹۳), arameshn (۱۲-۹-۱۳۸۹), astronomer (۰۹-۶-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۲-۶-۱۳۸۸), hossein.itplus (۰۳-۲۲-۱۳۹۴), mahvash (۰۸-۲۱-۱۳۹۵), mari-nafas (۰۹-۲۹-۱۳۹۳), Musketeer (۰۹-۲۴-۱۳۹۰), persian subtitle (۰۷-۲۶-۱۳۹۹), tohidsabunchi (۰۸-۱۰-۱۳۸۹) |
| #ADS | |
|
نشان دهنده تبلیغات
تبليغگر
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
|
|
|
|
۰۸-۱-۱۳۸۸, ۱۱:۴۲ قبل از ظهر
|
#2 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
صورت مسئله : هشت وزير را در هشت خانه شطرنج (8*8) طوري قرار دهيد كه هيچكدام يكديگر را تهديد نكنند. وزير در خانه هاي شطرنج به صورت عرضي،طولي و قطري مي تواند حركت كند. اين مسئله قابل تعميم به مسئله N وزير در يك شطرنج N*N است.
تاريخچه: اين مسئله در سالي 1848 توسط شطرنج بازي به نام Max Bezzel عنوان شد و رياضي دانان بسياري ازجمله Gauss و Georg Cantor بر روي اين مسئله كار كرده و در نهايت آنرا به N وزير تعميم دادند. اولين راه حل توسط Franz Nauck در سال 1850 ارائه شد كه به همان مسئله N وزير تعميم داده شد. پس از آن Gunther راه حلي با استفاده از دترمينان ارائه داد كه J.W.L. Glaisher آنرا كامل نمود. در سال 1979 ، Edsger Dijkstra با استفاده از الگوريتم عقب گرد اول عمق اين مسئله را حل كرد. راه حل: براي حل اين مسئله كه داراي 92 جواب است ، بايد تكنيكهايي جهت كاهش حالات ،روش Brute Force يا امتحان تك تك جواب ها انجام شود. تعداد همه حالاتي كه مي تواند در روش Brute Force چك شود برابر 16,777,216 يا هشت به توان هشت است! يكي از روش هاي حل اين مسئله براي n>=4 يا n=1 استفاده از روش مكاشفه اي (heuristic) است: 1- عدد n را بر عدد 12 تقسيم كن و باقي مانده را يادداشت كن 2- به ترتيب اعداد زوج 2 تا n را در ليستي بنويس 3- اگر باقي مانده 3 يا 9 بود ، عدد 2 را به انتهاي ليست انتقال بده. 4- به ليست اعداد فرد 1 تا N را به ترتيب اضافه كن، اما اگر باقي مانده 8 بود اعداد را دو به دو باهم عوض كند (مثلا 1و3و5و7و9 تبديل به 3و1و7و5و9 ميشه) 5- اگر باقي مانده 2 بود جاي 1 و3 را با هم عوض كن و 5 را به انتهاي ليست ببر 6- اگر باقي مانده 3 يا 9 بود ، اعداد 1 و 3 را به انتهاي ليست ببر. 7- حال با استفاده از ليست بدست آمده وزير ها در صفحه شطرنج چيده مي شوند، بطوريكه جاي وزير ستون اول ،اولين عدد ليست ،جاي وزير ستون دوم ، دومين عدد ليست و ... اين الگوريتم يك راه حل براي حل اين مسئله است، براي بدست آوردن همه حالات از روشهاي ديگري مي توان استفاده كرد. روش حل مسئله 12 راه حل يكتا دارد كه با در نظر گيري تقارن و چرخش به 92 حالت قابل تبديل است. |
|
|
|
| از Astaraki تشكر كرده اند: | +&+ALI (۰۴-۲۰-۱۳۹۱), advanture (۰۱-۳۱-۱۳۹۳), arameshn (۱۲-۹-۱۳۸۹), astronomer (۰۹-۶-۱۳۹۲), a_hamzeiian (۱۱-۲-۱۳۹۰), elenorgt500 (۰۹-۳۰-۱۳۹۱), green_Dream (۱۲-۸-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), sheera (۰۹-۱۰-۱۳۹۱), soodeh1010 (۰۲-۲۱-۱۳۹۰), tohidsabunchi (۰۸-۱۰-۱۳۸۹), انیسه (۰۴-۷-۱۳۹۳) |
|
۰۸-۱-۱۳۸۸, ۱۱:۵۸ قبل از ظهر
|
#3 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
روش های جستجوی محلی
برای معرفی هریک از روش های جستجویی که در فصل به بررسی آن ها می پردازیم از مسئله 8 وزیر استفاده خواهیم کرد. در مسئله 8 وزیر هدف قرار دادن 8 وزیر بر روی صفحه شطرنج به گونه ای است که هیچیک از وزیرها همدیگر را گارد ندهند. تعمیم یافته مسئله 8 وزیر، مسئله n وزیر است که در آن بر روی یک صفحه شطرنج n*n باید n وزیر را به گونه ای قرار دهیم که هیچیک همدیگر را گارد ندهند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش های جستجوی معمولی قادر به حل آن ها نخواهد بود. از سوی دیگر می توان به مسئله 8 وزیر به عنوان یک مسئله بهینه سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می باشد. به عنوان مثال فرض کنید در صفحه شطرنج معمولی ، 8 وزیر را به دو روش زیر قرار دهیم :   در روش چینش سمت چپ 3 وزیر و در روش چینش سمت راست 4 وزیر همدیگر را گارد می دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می توان مسئله بهینه سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب های ممکن برای مسئله باشد. در صورتی S* می تواند جواب مسئله باشد که به ازای همه جواب های موجود در S ، S* بهینه تر از دیگر جواب ها باشد. در مسئله 8 وزیر دیدیم که جوابی بهینه است که تعداد گاردهای جفت وزیر آن کمتر باشد. روش های جستجوی محلی همگی حالت های همسایه حالت فعلی را برای رسیدن به بهینه ترین جواب بررسی می کنند. از این رو وجود دو تابع در همه این روش های جستجو الزامی است. اولین تابع میزان بهینگی جواب مسئله ارزیابی می کند و تابع دوم یکی از حالت های همسایه حالت فعلی را انتخاب می کند. سخن آخر اینکه نحوه پیاده سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش های جستجو از اهمیت ویژه ای برخوردار است. به عنوان مثال برای مسئله 8 وزیر می توان به شکل های زیر حالت های همسایگی را تولید کرد : 1) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد. 2) یکی از وزیر ها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند. 3) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند |
|
|
|
| از Astaraki تشكر كرده اند: | arameshn (۱۲-۹-۱۳۸۹), astronomer (۰۹-۶-۱۳۹۲), a_hamzeiian (۱۱-۲-۱۳۹۰), bloodhat (۰۸-۶-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), payvand (۰۲-۱۵-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹) |
|
۰۸-۱-۱۳۸۸, ۱۲:۲۴ بعد از ظهر
|
#4 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
برنامه جستجوی تپه نوردی(برای هشت وزیر) نوشته شده با زبان c#
تپه نوردی Hill Climbing Searching یکی از الگوریتم های هوش مصنوعی می باشد که برای مسائل پیچیده به کار میرود به گونه ای که بجای اینکه برای حل مسئله از کل گراف استفاده کند.به صورت اتفاقی از یک قسمت از گراف استفاده میکند.
دريافت سورس برنامه به زبان #C
__________________
 ويرايش شده توسط Astaraki; ۰۵-۳-۱۳۹۰ در ساعت ۰۸:۴۰ قبل از ظهر |
|
|
|
| از Astaraki تشكر كرده اند: | arameshn (۱۲-۹-۱۳۸۹), a_hamzeiian (۱۱-۲-۱۳۹۰), bloodhat (۰۸-۶-۱۳۹۲), djmorteza (۰۲-۲۹-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), ht271 (۰۴-۴-۱۳۹۰), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), payvand (۰۲-۱۵-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹), yas1331 (۰۳-۱-۱۳۹۰) |
|
۰۸-۱-۱۳۸۸, ۱۲:۲۸ بعد از ظهر
|
#5 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
اين مسئله به وسيله الگوريتم ژنتيک نيز در لينک زير(پاورپوينت سوم) توضيح داده شده است
اسلاید های آموزشی الگوریتم ژنتیک در لينک زير هم حل اين مسئله توسط الگوريتم ژنتيک با زبان vb.net قرار دارد: كد:
http://www.sergejusz.com/engineering_tips/queens_ga.htm و کاربر محترم ALI_KH برنامه ي کامل شده را به ما لطف کردند که در ضميمه ميتونيد دريافت کنيد: 
__________________
ويرايش شده توسط Astaraki; ۱۱-۳-۱۳۸۹ در ساعت ۰۱:۲۶ بعد از ظهر |
|
|
|
| از Astaraki تشكر كرده اند: | arameshn (۱۲-۹-۱۳۸۹), a_hamzeiian (۱۱-۲-۱۳۹۰), dibaa (۰۲-۲۱-۱۳۹۱), ehsan_teimouri (۰۲-۲۶-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), kirkirkirkir (۱۰-۱۷-۱۳۸۹), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), mostafa_mit (۰۹-۹-۱۳۹۰), sahar68 (۱۱-۲۲-۱۳۸۹), tohidsabunchi (۰۸-۱۰-۱۳۸۹) |
|
۰۸-۱-۱۳۸۸, ۱۲:۳۰ بعد از ظهر
|
#6 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
حل مسئله هشت وزير با آنالينگ شبيه سازي شده
|
|
|
|
| از Astaraki تشكر كرده اند: | advanture (۰۱-۳۱-۱۳۹۳), arameshn (۱۲-۹-۱۳۸۹), arashmob (۰۳-۲۱-۱۳۹۳), a_rahmanbi (۰۳-۷-۱۳۹۰), elenorgt500 (۰۹-۳۰-۱۳۹۱), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), ir.ajax (۰۹-۲۹-۱۳۸۹), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹) |
|
۰۸-۱-۱۳۸۸, ۱۲:۳۳ بعد از ظهر
|
#7 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
هشت وزير با prolog
|
|
|
|
| از Astaraki تشكر كرده اند: | arameshn (۱۲-۹-۱۳۸۹), hadijojo (۰۲-۲۳-۱۳۹۱), jojepanbeyi (۰۹-۱۵-۱۳۹۰), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹) |
|
۰۸-۱-۱۳۸۸, ۱۲:۴۴ بعد از ظهر
|
#8 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
هشت وزير با روش بازگشت به عقب Backtracking
فرض کنید که در محله‌ای به دنبال یک کتاب فروشی خاص می‌گردیم. این کتاب فروشی در کوچه‌ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.
کاری که برای یافتن این کتاب فروشی می‌کنیم این است که در این محله ابتدا به دنبال آن خیابان فرعی می‌گردیم که در ابتدای آن یک مدرسه قرار دارد. سپس در این خیابان به دنبال کوچه‌ای می‌گردیم که یک خواربار فروشی در نبش آن است. هنگامی که کوچه را یافتیم، اگر در آن کتاب فروشی بود به جواب رسیده‌ایم وگرنه به خیابان فرعی برگشته و به دنبال کوچه‌ای دیگر می‌گردیم که یک خواربار فروشی در نبش آن باشد. اگر در این خیابان چنین کوچه‌ای وجود نداشت به خیابان اصلی برگشته و جستجوی خود را با یافتن خیابان فرعی دیگری با یک مدرسه در آن دنبال می کنیم. روالی که برای یافتن جواب در مثال بالا دنبال شد، روش بازگشت به عقب (Backtracking) نام دارد. در این روش همانطور که در مثال مشاهده کردید، در هر زمان که متوجه شدیم مسیر انتخاب شده به جواب نمی‌رسد، یک مرحله به عقب برگشته و مسیر دیگری را دنبال می کنیم. روش بازگشت به عقب برای آن دسته از مسائلی قابل استفاده است که برای رسیدن به جواب بتوان یک جستجوی سیستماتیک را دنبال کرد. به عنوان نمونه می‌توان بهره‌گیری از این روش را در بازیهای کامپیوتری، سیستمهای اثبات تئوریها، شبکه‌های مفهومی، هایپرتکس و ... دید. مثال 8 وزير: چگونه هشت وزیر را بر روی صفحه شطرنج قرار دهیم به گونه‌ای که هیچ یک از آنها مورد تهدید دیگری قرار نگیرد؟ در مقاله زير اين مسئله با استفاده از روش عقبگرد همراه با سورس کد آن کاملاً توضيح داده شده
|
|
|
|
| از Astaraki تشكر كرده اند: | arameshn (۱۲-۹-۱۳۸۹), arezoooo (۰۴-۱۱-۱۳۹۱), djmorteza (۰۲-۲۹-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), fereshte2 (۰۳-۱۹-۱۳۸۹), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), mehrshadkiani (۰۲-۱۹-۱۳۹۲), sinarock (۰۹-۹-۱۳۹۲), soodeh1010 (۰۲-۲۱-۱۳۹۰), tohidsabunchi (۰۸-۱۰-۱۳۸۹) |
|
۰۸-۲۶-۱۳۸۸, ۰۹:۳۷ بعد از ظهر
|
#9 (لینک دائم) | |
|
عضو جدید
 
تاريخ عضويت: آبان ۱۳۸۸
پست ها: 1
تشكرها: 0
7 تشكر در 1 پست
|
درخواست راهنمایی در مورد برنامه تپه نوردی با c#
نقل قول:
|
|
|
|
|
| از hamide_kh تشكر كرده اند: | behrouz6763 (۰۴-۲۹-۱۳۹۰), elenorgt500 (۰۹-۳۰-۱۳۹۱), fmahdi (۰۲-۲۶-۱۳۹۰), hadijojo (۰۲-۲۳-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹) |
|
۰۹-۱۳-۱۳۸۸, ۰۷:۳۳ بعد از ظهر
|
#10 (لینک دائم) |
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
و این هم برنامه ی NQueen که n رو از کاربر می خواد و بعد تمام جوابهای موجود رو چاپ میکنه!
 با TC اجرا ميشه
|
|
|
|
| از Astaraki تشكر كرده اند: | advanture (۰۱-۳۱-۱۳۹۳), Ameer (۱۰-۱-۱۳۸۸), arameshn (۱۲-۹-۱۳۸۹), Artemiss (۰۱-۲۹-۱۳۹۰), behrouz6763 (۰۴-۲۹-۱۳۹۰), elenorgt500 (۰۹-۳۰-۱۳۹۱), fmahdi (۰۲-۲۶-۱۳۹۰), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), ict69 (۰۷-۲۵-۱۳۸۹), ir.ajax (۰۹-۲۹-۱۳۸۹), mahbub2 (۰۳-۳۱-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), mari-nafas (۰۹-۲۹-۱۳۹۳), matinbakhtiar (۰۲-۲۹-۱۳۹۱), noran (۱۰-۲-۱۳۹۰), rezahashemian (۰۴-۱۲-۱۳۹۳), sahar-93 (۰۳-۲-۱۳۹۳), termehtala (۰۵-۱-۱۳۹۰), tohidsabunchi (۰۸-۱۰-۱۳۸۹), zahrajoon (۰۸-۵-۱۳۹۰) |
|
| كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان) | |
Linear Mode
|
|
زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۱۲:۱۷ بعد از ظهر ميباشد.
