برق. قدرت. کنترل. الکترونیک. مخابرات. تاسیسات.

دایره المعارف تاسیسات برق (اطلاعات عمومی برق)

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

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

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

دیدیم که جستجوی هزینه یکنواخت در صورتی که هزینه گام ها به درستی انتخاب شود، موجب یافتن جواب بهینه مسئله خواهد شد. در مقابل این روش با مشکل کند بودن عمل جستجو همراه است. در مقابل جستجوی حریصانه در یافتن جواب مسئله بسیار سریع بوده اما با مشکل حلقه بینهایت و عدم بهینگی جواب مواجه است ( لازم به ذکر است که بهینگی جستجوی حریصانه در برخی مسائل همانند الگوریتم های پریم و کروسکال اثبات شده است. اما در حالت کلی نمی توان ادعا کرد همیشه جستجوی حریصانه منجر به یافتن جواب بهینه خواهد شد). حال این سوال مطرح می شود که چگونه می توان این دو روش را باهم ترکیب کرده و روش جستجویی را طراحی کنیم که هم سریع بوده و هم جواب بهینه مسئله را بتواند پیدا کند؟ جواب مسئله در روش جستجو A* که در ادامه بررسی خواهیم کرد، می بینیم.

http://aisthinktank.com/tutorial/ai/aiGreedy.aspx

جستجوی حریصانه آلفا-بتا،الگوریتم جستجویی است که بدنبال کاهش تعداد محاسبات گره ها یا نود ها(node) در جستجوی درختی الگوریتم min-max می گردد.


[الگوریتم minmax or min-max]
جستجوی حریصانه آلفا-بتا الگوریتمی برپایه روش مخالف است، که اغلب در بازی های دو نفره ای همچون شطرنج(chess), تیک-تاک-تو(Tic-tac-toa) و GO و تخته نرد(backgammon) بکار می رود.
در این الگوریتم اگر محاسبه حرکت فعلی بهتر از حرکت قبلی باشد،الگوریتم از ادامه دادن محاسبه بعدی صرف نظر می کند(پ.ن:اگر نتیجه محاسبات alpha و beta ها از alpha و beta های بعدی بهتر باشد،روند محاسباتی alpha و beta های جدید را متوقف می سازد).
الگوریتم آلفا و بتا در نتیجه نهایی الگوریتم min-max تاثیری نمی گزارد، و فقط باعث بهبود سرعت جستجوی الگوریتم min-max می شود.
[مشاهده روند جستجوی الگوریتم آلفا و بتا درعمل، به صورت انیمیشن]
نقل قول:
Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. Alpha-beta pruning is a sound optimization in that it does not change the result of the algorithm it optimizes.
از ویکی پدیای انگلیسی
و نمونه کد آن در ++C


و در آخر چند PDF فارسی درباره هوش مصنوعی[Artificial Intelligence] و الگوریتم های alpha-beta و min-max،امیدوارم برای دوستان مفید واقع بشود: پیروز باشید.

مرجع:http://www.barnamenevis.org/forum/showthread.php?t=161221


(Constraint Satisfaction Problem)

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

 

روش های جستجوی آگاهانه

این استراتژی ها با استفاده از دانش ویژه مسئله، راه حل های کارا تری پیدا می کنند.

 

کشف کنندگی(Heuristic)

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

برخی کشف کنندگی را متضاد حالت الگوریتمیک به کار می برند.

تکنیک های کشف کنندگی بر کاربرد های اولیه هوش مصنوعی حکم فرما بود. اولین آزمایشگاه سیستم های خبره، که توسط Ed Fergenbaum، Bruce Buchanan، Joshua Lederberg در دانشگاه استنفورد آغاز به کار کرد، پروژه برنامه نویسی کشف کننده (HPP) نامیده شد.

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

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

 

1- جستجوی بهترین (Best-First Search)

همانطور که می دانید، الگوریتم جستجوی عمومی با استفاده از صف ها دانش مسئله را به کار می برد. اگر با استفاده از یک تابع ارزیابی (Evaluation)، که توضیحاتی مبنی بر مطلوب بودن یا نبودن گره را در بر دارد، صف را مرتب کنیم، ابتدا گره ای که بهترین رتبه را در ارزیابی داشته باشد، بسط داده می شود. این استراتژی را جستجوی بهترین می گویند.

نام «جستجوی بهترین» نادرست است. زیرا اگر ما می توانستیم واقعا بهترین گره را در ابتدا بسط دهیم، دیگر نمی توانستیم نام این عمل را جستجو بگذاریم.

به دلیل وجود توابع ارزیابی گوناگون، خانواده بزرگی از الگوریتم های جستجوی بهترین وجود دارد. همان گونه که الگوریتم جستجوی بهترین نیز عضوی از خانواده بزرگ الگوریتم جستجوی عمومی است.

مثال :

امیدوارم نقشه رومانی رو یادتون نرفته باشه! یک تابع کشف کننده خوب برای مسائل مسیریابی، مانند این مسئله، تابع مسافت مستقیم تا هدف است.

hSLD(n) : مسافت مستقیم بین n و مکان هدف.

فاصله مستقیم بین شهر های نقشه  و هدف :

366

0

160

242

161

178

77

151

226

244

Arad

Bucharest

Craiova

Dobreta

Eforie

Fagaras

Guirgui

Hirsova

Iasi

Lugoj

241

234

380

98

193

253

329

80

199

374

Mehadia

Neamt

Oradea

Pitesti

Rimnicu Vilcea

Sibiu

Timisoara

Urziceni

Valsui

Zerind

با محاسبه مقادیر hSLD در این مسئله، تابع کشف کنندگی حالت مطلوب را ارائه می دهد. زیرا یک مسیر A به B را معمولا در جهت درست هدایت می کند.

 

جستجوی حریصانه

با بررسی درخت جستجوی حریصانه برای رسیدن به بخارست، به این نتیجه می رسیم که استراتژی ترجیح می دهد که راه بزرگتر را برای رسیدن به هدف پیدا کند(زیرا راهی که انتخاب کرده 32 کیلومتر طولانی تر از راه  Rimnicuاست.)، بدون اینکه نگرانی ای در مورد طولانی بودن آن داشته باشد. از این رو نام حریصانه برای این استراتژی کاملا مناسب است.

گرچه حرص یکی از هفت گناه کبیره است!! ولی الگوریتم های حریص اغلب کارآیی خوبی دارند. آن ها تمایل به یافتن راه حل های سریع دارند.

اگر چه همانطور که در این مثال نشان داده شد، آن ها همیشه راه حل بهینه را پیدا نمی کنند.

با یک تابع کشف کنندگی خوب، پیچیدگی زمان و فضای این جستجو می تواند کاهش اساسی پیدا کند. میزان کاهش به مسئله و کیفیت تابع h بستگی دارد.

 

ویژگی ها

از شناسایی های مشابه گریزان است.

بهینه نیست.

کامل نیست.

پیچیدگی فضای آن O(bm) است. (m = حداکثر عمق فضای جستجو)

پیچیدگی زمان آن O(bm) است.

 

·   حداقل سازی مجموع هزینه مسیر : جستجوی A*

جستجوی حریصانه هزینه تخمین زده شده h(n) به سمت هدف را به حداقل می رساند و به موجب آن، هزینه جستجو را به مقدار قابل ملاحظه ای کاهش می دهد. ولی نه بهینه و نه کامل است.

همچنین جستجو با هزینه یکسان، هزینه مسیر g(n) را به حداقل می رساند و علاوه بر آن بهینه و کامل نیز هست.

اگر بتوانیم دو استراتژی را (برای دست یابی به مزایای آن ها) ترکیب کنیم، بهترین کار را انجام داده ایم.

این کار به این صورت انجام می شود :

f(n) = g(n) + h(n)

در نتیجه :

هزینه تخمین زده شده ارزانترین راه حل از طریق n = f(n)

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

این استراتژی جستجو را جستجوی A* می گویند.


http://artificial-i.blogfa.com/8506.aspx



صفحات جانبی

نظرسنجی

    لطفاً نظرات خود را درمورد وبلاگ با اینجانب در میان بگذارید.(iman.sariri@yahoo.com)نتایج تاکنون15000مفید و 125غیرمفید. با سپاس


  • آخرین پستها

آمار وبلاگ

  • کل بازدید :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :