Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > مقدمات هوش مصنوعی > حل مسائل معروف هوش مصنوعي


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۸-۱-۱۳۸۸, ۱۱:۳۵ قبل از ظهر   #1 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,300 تشكر در 3,124 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Arrow حل مسئله 8 وزير(8Queen) با روش هاي مختلف!

دوستان بياييد مسئله 8 وزير را با روش هاي مختلف در اينجا با هم حل کنيم

با استفاده از روشهايي از قبيل:
الگوريتم ژنتيک
جستجوي محلي
الگوريتم عقبگرد
مسئله ارضاي محدوديت
جستجوي تپه نوردي
و غيره

Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
advanture (۰۱-۳۱-۱۳۹۳), arameshn (۱۲-۹-۱۳۸۹), astronomer (۰۹-۶-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۲-۶-۱۳۸۸), hossein.itplus (۰۳-۲۲-۱۳۹۴), mahvash (۰۸-۲۱-۱۳۹۵), mari-nafas (۰۹-۲۹-۱۳۹۳), Musketeer (۰۹-۲۴-۱۳۹۰), tohidsabunchi (۰۸-۱۰-۱۳۸۹)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۰۸-۱-۱۳۸۸, ۱۱:۴۲ قبل از ظهر   #2 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,300 تشكر در 3,124 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

صورت مسئله : هشت وزير را در هشت خانه شطرنج (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 آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
+&+ALI (۰۴-۲۰-۱۳۹۱), advanture (۰۱-۳۱-۱۳۹۳), arameshn (۱۲-۹-۱۳۸۹), astronomer (۰۹-۶-۱۳۹۲), a_hamzeiian (۱۱-۲-۱۳۹۰), elenorgt500 (۰۹-۳۰-۱۳۹۱), green_Dream (۱۲-۸-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), sheera (۰۹-۱۰-۱۳۹۱), soodeh1010 (۰۲-۲۱-۱۳۹۰), tohidsabunchi (۰۸-۱۰-۱۳۸۹), انیسه (۰۴-۷-۱۳۹۳)
قديمي ۰۸-۱-۱۳۸۸, ۱۱:۵۸ قبل از ظهر   #3 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,300 تشكر در 3,124 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Question

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




در روش چینش سمت چپ 3 وزیر و در روش چینش سمت راست 4 وزیر همدیگر را گارد می دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می توان مسئله بهینه سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب های ممکن برای مسئله باشد. در صورتی S* می تواند جواب مسئله باشد که به ازای همه جواب های موجود در S ، S* بهینه تر از دیگر جواب ها باشد. در مسئله 8 وزیر دیدیم که جوابی بهینه است که تعداد گاردهای جفت وزیر آن کمتر باشد.

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

سخن آخر اینکه نحوه پیاده سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش های جستجو از اهمیت ویژه ای برخوردار است. به عنوان مثال برای مسئله 8 وزیر می توان به شکل های زیر حالت های همسایگی را تولید کرد :
1) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.
2) یکی از وزیر ها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.
3) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
arameshn (۱۲-۹-۱۳۸۹), astronomer (۰۹-۶-۱۳۹۲), a_hamzeiian (۱۱-۲-۱۳۹۰), bloodhat (۰۸-۶-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), payvand (۰۲-۱۵-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹)
قديمي ۰۸-۱-۱۳۸۸, ۱۲:۲۴ بعد از ظهر   #4 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,300 تشكر در 3,124 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink برنامه جستجوی تپه نوردی(برای هشت وزیر) نوشته شده با زبان c#

تپه نوردی Hill Climbing Searching یکی از الگوریتم های هوش مصنوعی می باشد که برای مسائل پیچیده به کار میرود به گونه ای که بجای اینکه برای حل مسئله از کل گراف استفاده کند.به صورت اتفاقی از یک قسمت از گراف استفاده میکند.

دريافت سورس برنامه به زبان #C
فايل ضميمه
نوع فايل: zip Hill Climbing Searching.zip (24.8 كيلو بايت, 2458 نمايش)

ويرايش شده توسط Astaraki; ۰۵-۳-۱۳۹۰ در ساعت ۰۸:۴۰ قبل از ظهر
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
arameshn (۱۲-۹-۱۳۸۹), a_hamzeiian (۱۱-۲-۱۳۹۰), bloodhat (۰۸-۶-۱۳۹۲), djmorteza (۰۲-۲۹-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), ht271 (۰۴-۴-۱۳۹۰), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), payvand (۰۲-۱۵-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹), yas1331 (۰۳-۱-۱۳۹۰)
قديمي ۰۸-۱-۱۳۸۸, ۱۲:۲۸ بعد از ظهر   #5 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,300 تشكر در 3,124 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

اين مسئله به وسيله الگوريتم ژنتيک نيز در لينک زير(پاورپوينت سوم) توضيح داده شده است

اسلاید های آموزشی الگوریتم ژنتیک

در لينک زير هم حل اين مسئله توسط الگوريتم ژنتيک با زبان vb.net قرار دارد:
كد:
http://www.sergejusz.com/engineering_tips/queens_ga.htm
البته در اون سايت برنامه کامل نيست!
و کاربر محترم ALI_KH برنامه ي کامل شده را به ما لطف کردند که در ضميمه ميتونيد دريافت کنيد:
فايل ضميمه
نوع فايل: rar queentest.rar (83.4 كيلو بايت, 4810 نمايش)

ويرايش شده توسط Astaraki; ۱۱-۳-۱۳۸۹ در ساعت ۰۱:۲۶ بعد از ظهر
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
arameshn (۱۲-۹-۱۳۸۹), a_hamzeiian (۱۱-۲-۱۳۹۰), dibaa (۰۲-۲۱-۱۳۹۱), ehsan_teimouri (۰۲-۲۶-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), gh452003 (۰۹-۱۳-۱۳۸۸), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), kirkirkirkir (۱۰-۱۷-۱۳۸۹), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), mostafa_mit (۰۹-۹-۱۳۹۰), sahar68 (۱۱-۲۲-۱۳۸۹), tohidsabunchi (۰۸-۱۰-۱۳۸۹)
قديمي ۰۸-۱-۱۳۸۸, ۱۲:۳۰ بعد از ظهر   #6 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,300 تشكر در 3,124 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Cool

حل مسئله هشت وزير با آنالينگ شبيه سازي شده
فايل ضميمه
نوع فايل: pdf AIapxSA8Q.pdf (122.6 كيلو بايت, 3821 نمايش)
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
advanture (۰۱-۳۱-۱۳۹۳), arameshn (۱۲-۹-۱۳۸۹), arashmob (۰۳-۲۱-۱۳۹۳), a_rahmanbi (۰۳-۷-۱۳۹۰), elenorgt500 (۰۹-۳۰-۱۳۹۱), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), ir.ajax (۰۹-۲۹-۱۳۸۹), Mahdi67 (۱۱-۲۳-۱۳۸۹), matinbakhtiar (۰۲-۲۹-۱۳۹۱), tohidsabunchi (۰۸-۱۰-۱۳۸۹)
قديمي ۰۸-۲۹-۱۳۹۰, ۰۵:۳۲ بعد از ظهر   #7 (لینک دائم)
عضو جدید
 
آواتار sajad_vorojack
 
تاريخ عضويت: آبان ۱۳۹۰
پست ها: 2
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

نقل قول:
نوشته اصلي بوسيله reyhane نمايش پست
تپه نوردی hill climbing searching یکی از الگوریتم های هوش مصنوعی می باشد که برای مسائل پیچیده به کار میرود به گونه ای که بجای اینکه برای حل مسئله از کل گراف استفاده کند.به صورت اتفاقی از یک قسمت از گراف استفاده میکند.

دريافت سورس برنامه به زبان #c
سلام ریحانه جانم ممنون بابت این همه زحمت
میخواستم سورس کامل برنامه داشته باشم دوم اینکه میشه یه مطلب راهنمایی و اینکه الگوریتم این برنامه چی هستو روش کارش چطوره رو برام بذارید
و اینکه سورس این برنامه رو با زبان های دیگه ای هم دارید یا نه؟ بازم ممنون از لطفتون
sajad_vorojack آفلاين است   پاسخ با نقل قول
قديمي ۱۱-۸-۱۳۹۰, ۰۹:۱۶ بعد از ظهر   #8 (لینک دائم)
عضو جدید
 
آواتار bahare64
 
تاريخ عضويت: مرداد ۱۳۹۰
پست ها: 3
تشكرها: 1
0 تشكر در 0 پست
پيش فرض

سلام ممنون بابت اطلاعات مفیدی که قرار میدن،
من برای انجام پایان نامم نیاز به پیاده سازی الگوریتم ممتیک دارم تمامی قسمتهای الگوریتمو پیاده سازی کردم فقط قسمت سرچ محلی باقی مونده نمی دونم باید از کجا شروع کنم ممکنه کمکم کنید بازم ممنون.
bahare64 آفلاين است   پاسخ با نقل قول
قديمي ۱۱-۲-۱۳۸۸, ۰۹:۲۴ بعد از ظهر   #9 (لینک دائم)
ali-kh
Guest
 
آواتار ali-kh
 
پست ها: n/a
پيش فرض

اینم یه برنامه برای الگوریتم عقبگرد که خودم با c# نوشتم
فايل ضميمه
نوع فايل: rar EightQueen.rar (770.5 كيلو بايت, 1440 نمايش)
  پاسخ با نقل قول
از تشكر كرده است:
Astaraki (۱۱-۳-۱۳۸۸)
قديمي ۰۱-۱۴-۱۳۸۹, ۰۷:۲۱ بعد از ظهر   #10 (لینک دائم)
عضو جدید
 
آواتار persiandata
 
تاريخ عضويت: بهمن ۱۳۸۸
پست ها: 1
تشكرها: 1
1 تشكر در 1 پست
پيش فرض

سلام کاش یکی پیدا میشد و برنامه n وزیر با الگوریتم ژنتیک توی سی شارپ رو میگذاشت . خواهشا کمک کنید فقط با سی شارپ
persiandata آفلاين است   پاسخ با نقل قول
از persiandata تشكر كرده است:
m.shh (۰۳-۱-۱۳۹۰)
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 
ابزارهاي تاپيک
نحوه نمايش

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۲:۱۶ بعد از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design