صفحه‌ها: ۱ ۲
هرس آلفا -بتا باعث افزایش سرعت جستجو میشود یا کاهش؟؟؟؟ و چرا؟؟؟؟
(۰۲ آذر ۱۳۹۰ ۰۳:۵۱ ب.ظ)homa نوشته شده توسط: هرس آلفا -بتا باعث افزایش سرعت جستجو میشود یا کاهش؟؟؟؟ و چرا؟؟؟؟
این الگوریتم در جستجوهای فضای رقابتی مورد استفاده قرار میگیرد.
و چون در این گونه مسائل فضای حالات مختلف قابل بررسی از مرتبه(O(b^m هستن در نتیجه رسیدن به حالت هدف دارای زمان نمایی است.
و چون این الگوریتم فضای حالت قابل بررسی را نصف میکند میتوان گفت که باعث افزایش سرعت جستجو میشود.
اگه جواب مشکلی داره بگین.
من خیلی وقته هوش رو نخوندم.
(۰۲ آذر ۱۳۹۰ ۰۴:۱۸ ب.ظ)mamat نوشته شده توسط:ممنون از جوابت ...(02 آذر ۱۳۹۰ ۰۳:۵۱ ب.ظ)homa نوشته شده توسط: هرس آلفا -بتا باعث افزایش سرعت جستجو میشود یا کاهش؟؟؟؟ و چرا؟؟؟؟
این الگوریتم در جستجوهای فضای رقابتی مورد استفاده قرار میگیرد.
و چون در این گونه مسائل فضای حالات مختلف قابل بررسی از مرتبه(O(b^m هستن در نتیجه رسیدن به حالت هدف دارای زمان نمایی است.
و چون این الگوریتم فضای حالت قابل بررسی را نصف میکند میتوان گفت که باعث افزایش سرعت جستجو میشود.
اگه جواب مشکلی داره بگین.
من خیلی وقته هوش رو نخوندم.
اما جواب غلطه چون تو یه تست اینکه باعث افزایش سرعت میشه رو گزینه‌ی اشتباه گرفته یعنی باعث کاهش سرعت میشه
تست ۱ فصل ۵ کتاب پوران
هرس کردن تعداد نود های که باید visit بشن (فضای حالت)کاهش میده پس سرعت باید بیشتر بشه
!!!!! ولی نمیدونم دلیل اینکه گفته کاهش میده چیه؟؟؟؟
فکر کنم دلیلش این بوده که در مسائلی که مقدار m زیاد باشه دیگه m/2 تاثسر آنچنانی نخواهد داشت. و باز مرتبه نمایی هست.
(۰۲ آذر ۱۳۹۰ ۰۵:۱۶ ب.ظ)mamat نوشته شده توسط: فکر کنم دلیلش این بوده که در مسائلی که مقدار m زیاد باشه دیگه m/2 تاثسر آنچنانی نخواهد داشت. و باز مرتبه نمایی هست.همون طور که خودتم داری میگی اگه بر فرض منظورش m های بینهات باشه براش تا ثیری نداره نه اینکه اون رو کاهش بده درسته؟؟
فکر نمی کنم دلیلش این باشه
فرض کنین درخت شما مثلا دارای ۱۰۰۰ سطح باشه. و اگر بخواین با روش minimax جواب را پیدا کنین الگوریتم تا ۱۰ سطح را براتون پیمایشمی کنه و جواب مورد نظرش را بر میگردانه. حالا اگر با هرس آلفابتا بخواین اینکار را بکنین در بهترین حالت اگر الگوریتم از نصف گره‌ها هم که صرفنظر کنه باز زمان شما کم نمیشه. چون فضای خالی که براش باقی مانده را برای افزایش عمق استفاده میکنه. مثلا اینبار جای ۱۰ سطح، ۲۰ سطح را بررسی می کنه. نتیجه اینکه هرس باعث افزایش عمق جستجو میشه نه کاهش زمان جستجو.
(۰۲ آذر ۱۳۹۰ ۰۵:۵۳ ب.ظ)pos نوشته شده توسط: فرض کنین درخت شما مثلا دارای ۱۰۰۰ سطح باشه. و اگر بخواین با روش minimax جواب را پیدا کنین الگوریتم تا ۱۰ سطح را براتون پیمایشمی کنه و جواب مورد نظرش را بر میگردانه. حالا اگر با هرس آلفابتا بخواین اینکار را بکنین در بهترین حالت اگر الگوریتم از نصف گره‌ها هم که صرفنظر کنه باز زمان شما کم نمیشه. چون فضای خالی که براش باقی مانده را برای افزایش عمق استفاده میکنه. مثلا اینبار جای ۱۰ سطح، ۲۰ سطح را بررسی می کنه. نتیجه اینکه هرس باعث افزایش عمق جستجو میشه نه کاهش زمان جستجو.
بله کاملا صحیحه. من به این نکته توجه نمی کردم و یادم رفته بود که عمق جستجو را دوبرابر میکنه .
به جزوه دانشگاهیم هم که نگاه کردم به این مورد اشاره شده بود.
از جواب سطحی و بدون مطالعه ای که دادم معذرت میخوام.
(۰۲ آذر ۱۳۹۰ ۰۵:۵۳ ب.ظ)pos نوشته شده توسط: فرض کنین درخت شما مثلا دارای ۱۰۰۰ سطح باشه. و اگر بخواین با روش minimax جواب را پیدا کنین الگوریتم تا ۱۰ سطح را براتون پیمایشمی کنه و جواب مورد نظرش را بر میگردانه. حالا اگر با هرس آلفابتا بخواین اینکار را بکنین در بهترین حالت اگر الگوریتم از نصف گره‌ها هم که صرفنظر کنه باز زمان شما کم نمیشه. چون فضای خالی که براش باقی مانده را برای افزایش عمق استفاده میکنه. مثلا اینبار جای ۱۰ سطح، ۲۰ سطح را بررسی می کنه. نتیجه اینکه هرس باعث افزایش عمق جستجو میشه نه کاهش زمان جستجو.استدلال اینکه با استفاده از هرس آلفا بتا عمق بیشتری بررسی میکنه میشه توضیح بدین؟؟؟
خوب شما به مقداری می تونین توی عمق حرکت کنین که فضای حافظه دارین. هرس باعث میشه یکسری گره‌ها تولید نشن و از همین فضای خالش شما بتونین برای تولید گره های سطح بعدی استفاده کنین. یعنی توی عمق پیشروی کنین.
البته تنها دلیلش فضای حافظه نیست. دلیلی که تو نوشته های دانشگاهیم پیدا کردم اینه که چون این الگوریتم برای مساله های خصمانه(رقابتی یا مسابقه) هست پس ما یک حد آستانه برای زمان داریم و در آن زمان باید بهترین حرکت رو انجام بدیم.
خوب ما با روش هرس آلفا-بتا همیشه تا عمق d بهترین حرکت را در فضای حالت d-1 را داریم. و به جهت محدودیت زمان باید در همین فضای حالات یک جواب بهینه محلی انتخاب کنیم.
عمق جستجو رابطه ای نزدیک با قوانین بازی که محدودیتی برای زمان عکس العمل هست، دارد. و زمانی که ما تقریبا نصف گره‌ها رو هرس میکنیم پس ما میتونیم در زمان اختصاص داده شده دوبرابر در عمق پیش بریم.
امیدوارم توضیح مناسبی باشه.
حالا اگه عمق هدف زیاد نباشه.....پس با هرس آلفا و بتا می تونیم زودتر از حد زمانی و مکانی به هدف برسیم پس سرعت افزایش پیدا کرده...این طور نیست؟؟؟؟؟؟؟؟؟؟؟؟؟
(۰۵ آذر ۱۳۹۰ ۰۵:۴۱ ب.ظ)homa نوشته شده توسط: حالا اگه عمق هدف زیاد نباشه.....پس با هرس آلفا و بتا می تونیم زودتر از حد زمانی و مکانی به هدف برسیم پس سرعت افزایش پیدا کرده...این طور نیست؟؟؟؟؟؟؟؟؟؟؟؟؟
من نمیدونم چرا شما اینقدر میخواین این الگوریتم رو خوب جلوه بدین
خوب و اما پاسخ به این سوال:
اگه عمق درخت جستجومون در این نوع بازی‌ها کم باشه (که نیست و نخواهد بود چون برای بازی شطرنج این درخت تقریبا برابر ۳۵ بتوان ۱۰۰ گره هست)، حالا فرض بر این باشه که عمقمون کمه، در اینصورت شرایط رقابتی بازی باید شدیدتر باشه و زمان برای حرکت طرفین کم باشه. و این باز حرکت زیاد در عمق را اجازه نخواهد داد.
این نظر بنده است. البته استنتاجی هست و برگرفته از هیچ منبعی نیست.
(۰۵ آذر ۱۳۹۰ ۰۹:۲۸ ب.ظ)mamat نوشته شده توسط:(05 آذر ۱۳۹۰ ۰۵:۴۱ ب.ظ)homa نوشته شده توسط: حالا اگه عمق هدف زیاد نباشه.....پس با هرس آلفا و بتا می تونیم زودتر از حد زمانی و مکانی به هدف برسیم پس سرعت افزایش پیدا کرده...این طور نیست؟؟؟؟؟؟؟؟؟؟؟؟؟
من نمیدونم چرا شما اینقدر میخواین این الگوریتم رو خوب جلوه بدین
خوب و اما پاسخ به این سوال:
اگه عمق درخت جستجومون در این نوع بازی‌ها کم باشه (که نیست و نخواهد بود چون برای بازی شطرنج این درخت تقریبا برابر ۳۵ بتوان ۱۰۰ گره هست)، حالا فرض بر این باشه که عمقمون کمه، در اینصورت شرایط رقابتی بازی باید شدیدتر باشه و زمان برای حرکت طرفین کم باشه. و این باز حرکت زیاد در عمق را اجازه نخواهد داد.
این نظر بنده است. البته استنتاجی هست و برگرفته از هیچ منبعی نیست.
مگه بده طرفدار یه فرمول باشی
حرفت رو قبول دارم ولی در مورد هر چی حرف میزنیم میگیم (اگر و فرض می کنیم) پس در حالت کلی به نظر من نمیشه در مورد سرعتش قضاوت کرد بستگی به شرایط داره البته این نظر منه...(چون طرفدارشم
)
ولی من "اگری" نگفتم و شما اگرهارو برای بهتر جلوه دادن این الگوریتم از نظر سرعت آوردین.
اما من میگم سرعت تفاوتی نخواهد کرد. چون به قول شما "اگر" فضای حالت کوچیک بشه و ما شرایط رقابتی رو از لحاظ زمان کم نکنیم دیگه میایم یه زمانی رو براش درنظر میگیریم که حتی این محاسبات رو هم نداشته باشه و مثلا DFS هم براش خوب جواب بده.
(۰۲ آذر ۱۳۹۰ ۰۵:۰۸ ب.ظ)homa نوشته شده توسط: ممنون از جوابت ...
اما جواب غلطه چون تو یه تست اینکه باعث افزایش سرعت میشه رو گزینه‌ی اشتباه گرفته یعنی باعث کاهش سرعت میشه
تست ۱ فصل ۵ کتاب پوران
هرس کردن تعداد نود های که باید visit بشن (فضای حالت)کاهش میده پس سرعت باید بیشتر بشه
این تستی که میگین درست نیست پاسخش. جزوه دکتر فیلی هم این گزینه رو درست اعلام کرده.
مشخصاً هم شما میتونید سرعت بیشتری در یافتن گره پاسخ داشته باشید هم اینکه میتونید تعداد گره بیشتری رو با هرس در طی بازه زمانی که از هرس استفاده نمیکنید٬ ملاقات کنید.