زمان کنونی: ۲۷ آذر ۱۳۹۷, ۰۹:۴۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

هرس آلفا- بتاباعث افزایش سرعت جستجو میشود یا کاهش؟

ارسال:
  

homa پرسیده:

هرس آلفا- بتاباعث افزایش سرعت جستجو میشود یا کاهش؟

هرس آلفا -بتا باعث افزایش سرعت جستجو میشود یا کاهش؟؟؟؟ و چرا؟؟؟؟

۰
ارسال:
  

hadi_m پاسخ داده:

هرس آلفا- بتا

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

۰
ارسال:
  

hadi_m پاسخ داده:

هرس آلفا- بتا

سخن اخر اینکه
من با نظر دوستانی که گفتن سرعت تفاوت نخواهد کرد کاملا موافقم و همچنین سخن دوستانی که گفتن سرعت افزایش پیدا خواهد کرد اگر منظورشون میزان کارایی عامل باشه باز هم موافقم و علتش هم اینه که فرض کنید که:
فضای که در دسترس هر دو الگوریتم هست قادر به نگهادری ۱۰۰۰ نود(حالت مابعد) رو داره حال اگر هر دو الگوریتم موظف باشن از تمام این حافظه استفاده کنند و هزینه بسط هر گره در حافظه هم t در نظر بگیریم هر دو الگوریتم ۱۰۰۰ نود رو بسط خواهند داد (اما الگوریتم الفا بتا تا عمق بیشتری )و لذا هزینه بسط این ۱۰۰۰ گره یا حالت برابر با ۱۰۰۰t خواهد بود که این هزینه رو مستقل از نوع الگوریتم باید بپردازیم (سرعت یکسان). بنابراین سرعت هیچ تفاوتی نمیکنه اما باز هم عملکرد عاملی که دارد با هرس الفا بتا عمل مکیند خیلی بهتر و نزدیک به واقعیت خواهد بود(عنصر کارایی) .
فرض دیگری رو در نظر بگیرید که الگوریتمهای قادر باشند از تمام فضای حافظه ایی که به انها اختصاص داده شده بهره نبرند خب در این حالت الگوریتم الفابتا در اکثر مواقع از تمام فضا برای پیش بردن عمق جستجو بهره میبرد (۱۰۰۰t)اما الگوریتم معمولی با در نظر گرفتن عمق برش ایستا (عمق برش معمولا پویاست و ایستا نیست) میتواند به سرعت بهتری دست پیدا کند(T<=1000t) چون کافیه به عمق برش برسد و تعداد گرهایی بسط داده شده کمتر از میزان حافظه اختصاص داده شده باشد(حالت خیلی خیلی خاص و بدون در نظر گرفتن هزینه محاسبه هیوریستیک این نوع عامل که معمولا هزینه بالایی دارند چون باید اینده دور را تخمین بزنند مگر انکه عنصر کارایی رو فدای سرعت کنند)

در هر حال انچه که اهمیت دارد نظر طراح سئوال هست هر چند اگر نظر ایشان درست نباشد.

۰
ارسال:
  

mamat پاسخ داده:

RE: هرس آلفا- بتا

(۰۲ آذر ۱۳۹۰ ۰۳:۵۱ ب.ظ)homa نوشته شده توسط:  هرس آلفا -بتا باعث افزایش سرعت جستجو میشود یا کاهش؟؟؟؟ و چرا؟؟؟؟

این الگوریتم در جستجوهای فضای رقابتی مورد استفاده قرار میگیرد.
و چون در این گونه مسائل فضای حالات مختلف قابل بررسی از مرتبه(O(b^m هستن در نتیجه رسیدن به حالت هدف دارای زمان نمایی است.
و چون این الگوریتم فضای حالت قابل بررسی را نصف میکند میتوان گفت که باعث افزایش سرعت جستجو میشود.

اگه جواب مشکلی داره بگین.
من خیلی وقته هوش رو نخوندم.

ارسال:
  

homa پاسخ داده:

RE: هرس آلفا- بتا

(۰۲ آذر ۱۳۹۰ ۰۴:۱۸ ب.ظ)mamat نوشته شده توسط:  
(02 آذر ۱۳۹۰ ۰۳:۵۱ ب.ظ)homa نوشته شده توسط:  هرس آلفا -بتا باعث افزایش سرعت جستجو میشود یا کاهش؟؟؟؟ و چرا؟؟؟؟

این الگوریتم در جستجوهای فضای رقابتی مورد استفاده قرار میگیرد.
و چون در این گونه مسائل فضای حالات مختلف قابل بررسی از مرتبه(O(b^m هستن در نتیجه رسیدن به حالت هدف دارای زمان نمایی است.
و چون این الگوریتم فضای حالت قابل بررسی را نصف میکند میتوان گفت که باعث افزایش سرعت جستجو میشود.

اگه جواب مشکلی داره بگین.
من خیلی وقته هوش رو نخوندم.
ممنون از جوابت ...
اما جواب غلطه چون تو یه تست اینکه باعث افزایش سرعت میشه رو گزینه‌ی اشتباه گرفته یعنی باعث کاهش سرعت میشه
تست ۱ فصل ۵ کتاب پوران
هرس کردن تعداد نود های که باید visit بشن (فضای حالت)کاهش میده پس سرعت باید بیشتر بشهHuh !!!!! ولی نمیدونم دلیل اینکه گفته کاهش میده چیه؟؟؟؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

mamat پاسخ داده:

هرس آلفا- بتا

فکر کنم دلیلش این بوده که در مسائلی که مقدار m زیاد باشه دیگه m/2 تاثسر آنچنانی نخواهد داشت. و باز مرتبه نمایی هست.

ارسال:
  

homa پاسخ داده:

RE: هرس آلفا- بتا

(۰۲ آذر ۱۳۹۰ ۰۵:۱۶ ب.ظ)mamat نوشته شده توسط:  فکر کنم دلیلش این بوده که در مسائلی که مقدار m زیاد باشه دیگه m/2 تاثسر آنچنانی نخواهد داشت. و باز مرتبه نمایی هست.
همون طور که خودتم داری میگی اگه بر فرض منظورش m های بینهات باشه براش تا ثیری نداره نه اینکه اون رو کاهش بده درسته؟؟
فکر نمی کنم دلیلش این باشه
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

pos پاسخ داده:

هرس آلفا- بتا

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

ارسال:
  

mamat پاسخ داده:

هرس آلفا- بتا

(۰۲ آذر ۱۳۹۰ ۰۵:۵۳ ب.ظ)pos نوشته شده توسط:  فرض کنین درخت شما مثلا دارای ۱۰۰۰ سطح باشه. و اگر بخواین با روش minimax جواب را پیدا کنین الگوریتم تا ۱۰ سطح را براتون پیمایشمی کنه و جواب مورد نظرش را بر میگردانه. حالا اگر با هرس آلفابتا بخواین اینکار را بکنین در بهترین حالت اگر الگوریتم از نصف گره‌ها هم که صرفنظر کنه باز زمان شما کم نمیشه. چون فضای خالی که براش باقی مانده را برای افزایش عمق استفاده میکنه. مثلا اینبار جای ۱۰ سطح، ۲۰ سطح را بررسی می کنه. نتیجه اینکه هرس باعث افزایش عمق جستجو میشه نه کاهش زمان جستجو.

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

ارسال: #۱۰
  

homa پاسخ داده:

RE: هرس آلفا- بتا

(۰۲ آذر ۱۳۹۰ ۰۵:۵۳ ب.ظ)pos نوشته شده توسط:  فرض کنین درخت شما مثلا دارای ۱۰۰۰ سطح باشه. و اگر بخواین با روش minimax جواب را پیدا کنین الگوریتم تا ۱۰ سطح را براتون پیمایشمی کنه و جواب مورد نظرش را بر میگردانه. حالا اگر با هرس آلفابتا بخواین اینکار را بکنین در بهترین حالت اگر الگوریتم از نصف گره‌ها هم که صرفنظر کنه باز زمان شما کم نمیشه. چون فضای خالی که براش باقی مانده را برای افزایش عمق استفاده میکنه. مثلا اینبار جای ۱۰ سطح، ۲۰ سطح را بررسی می کنه. نتیجه اینکه هرس باعث افزایش عمق جستجو میشه نه کاهش زمان جستجو.
استدلال اینکه با استفاده از هرس آلفا بتا عمق بیشتری بررسی میکنه میشه توضیح بدین؟؟؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۱
  

pos پاسخ داده:

هرس آلفا- بتا

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

۰
ارسال: #۱۲
  

mamat پاسخ داده:

هرس آلفا- بتا

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

امیدوارم توضیح مناسبی باشه.

۰
ارسال: #۱۳
  

homa پاسخ داده:

RE: هرس آلفا- بتا

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

ارسال: #۱۴
  

mamat پاسخ داده:

RE: هرس آلفا- بتا

(۰۵ آذر ۱۳۹۰ ۰۵:۴۱ ب.ظ)homa نوشته شده توسط:  حالا اگه عمق هدف زیاد نباشه.....پس با هرس آلفا و بتا می تونیم زودتر از حد زمانی و مکانی به هدف برسیم پس سرعت افزایش پیدا کرده...این طور نیست؟؟؟؟؟؟؟؟؟؟؟؟؟

من نمیدونم چرا شما اینقدر میخواین این الگوریتم رو خوب جلوه بدینTongue

خوب و اما پاسخ به این سوال:
اگه عمق درخت جستجومون در این نوع بازی‌ها کم باشه (که نیست و نخواهد بود چون برای بازی شطرنج این درخت تقریبا برابر ۳۵ بتوان ۱۰۰ گره هست)، حالا فرض بر این باشه که عمقمون کمه، در اینصورت شرایط رقابتی بازی باید شدیدتر باشه و زمان برای حرکت طرفین کم باشه. و این باز حرکت زیاد در عمق را اجازه نخواهد داد.

این نظر بنده است. البته استنتاجی هست و برگرفته از هیچ منبعی نیست.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۵
  

mamat پاسخ داده:

هرس آلفا- بتا

ولی من "اگری" نگفتم و شما اگرهارو برای بهتر جلوه دادن این الگوریتم از نظر سرعت آوردین.

اما من میگم سرعت تفاوتی نخواهد کرد. چون به قول شما "اگر" فضای حالت کوچیک بشه و ما شرایط رقابتی رو از لحاظ زمان کم نکنیم دیگه میایم یه زمانی رو براش درنظر میگیریم که حتی این محاسبات رو هم نداشته باشه و مثلا DFS هم براش خوب جواب بده.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  توضیح کامل همراه با مثال هرس آلفا بتا saeed_435 ۲ ۸,۴۴۴ ۲۳ دى ۱۳۹۰ ۰۱:۴۳ ق.ظ
آخرین ارسال: saeed_435
  فرض استقلال اهداف فرعی در هیوریستیک برای جستجو در فضای حالت homa ۱ ۱,۵۳۹ ۱۸ بهمن ۱۳۸۹ ۰۲:۵۸ ب.ظ
آخرین ارسال: امیدوار
  [ نکات ] حل مساله با جستجو Masoud05 ۱ ۱,۹۸۴ ۲۵ دى ۱۳۸۹ ۰۲:۲۲ ب.ظ
آخرین ارسال: Masoud05
  در خواست توضیح(کاهش هزینه ها درالگوریتم های نا آگاهانه تکرارشونده؟) navidfj ۱ ۲,۱۷۳ ۰۷ دى ۱۳۸۹ ۰۷:۳۸ ق.ظ
آخرین ارسال: bijibuji

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close