صفحه‌ها: ۱ ۲
(۱۲ آذر ۱۳۹۰ ۰۹:۵۲ ب.ظ)mam نوشته شده توسط:میتونی برای ۲ موردش (افزایش سرعت و کاهش سرعت)مثال بزنی؟؟(02 آذر ۱۳۹۰ ۰۵:۰۸ ب.ظ)homa نوشته شده توسط: ممنون از جوابت ...
اما جواب غلطه چون تو یه تست اینکه باعث افزایش سرعت میشه رو گزینه‌ی اشتباه گرفته یعنی باعث کاهش سرعت میشه
تست ۱ فصل ۵ کتاب پوران
هرس کردن تعداد نود های که باید visit بشن (فضای حالت)کاهش میده پس سرعت باید بیشتر بشه!!!!! ولی نمیدونم دلیل اینکه گفته کاهش میده چیه؟؟؟؟
این تستی که میگین درست نیست پاسخش. جزوه دکتر فیلی هم این گزینه رو درست اعلام کرده.
مشخصاً هم شما میتونید سرعت بیشتری در یافتن گره پاسخ داشته باشید هم اینکه میتونید تعداد گره بیشتری رو با هرس در طی بازه زمانی که از هرس استفاده نمیکنید٬ ملاقات کنید.
چون من خودم هم به این نتیجه رسیدم ولی نمی دونم چه جوری یک مثال واضح بزنم
(۱۲ آذر ۱۳۹۰ ۱۰:۵۰ ب.ظ)homa نوشته شده توسط: میتونی برای ۲ موردش (افزایش سرعت و کاهش سرعت)مثال بزنی؟؟
چون من خودم هم به این نتیجه رسیدم ولی نمی دونم چه جوری یک مثال واضح بزنم
ببینید مشخصاً طبق تعریف٬ فاکتور انشعاب مؤثر از b به [tex]\sqrt{b}[/tex] تبدیل میکنه. خب طبق این استدلال٬ گره‌ها و شاخه‌هایی که ضروری نیستند حذف میشن و میشه سرعت یافتن گره‌های بعدی رو بیشتر کرد.
گفتم شاید گفتن یه نکته خالی از لطف نباشه و همانطور که بعضی دوستان اشاره کردن الگوریتم الفا بتا (بعضی مواقع)باعث کاهش سرعت میشه ..اما چگونه ؟
اولا اگر قرار باشه کل فضای حالت رو برای رسیدن به حالات انتهایی بسط دهیم هرس الفا بتا باعث افزایش سرعت میشه چون از جستجو در مسیرهای نامناسب جلوگیری میکنه اما الگوریتم معمولی MinMax تمام گرها رو بسط میدهد و بررسی میکنه .
اما مسئله این هست که اکثر مواقع ودر هر دو حالت ما قادر به بسط کل فضای حالت نیستیم به همین خاطر انرا برش داده و در عمق برش از تابع هیوریستیک (به جای تابع ارزیابی)برای تخمین حالات نهایی استفاده میکنیم .بنابراین کاملا منطقی هست که هر چقدر این عمق کمتر باشد سرعت افزایش میابد چون به محض رسیدن به عمق برش با استفاده از تابع هیوریستیک انرا محاسبه کرده و در مقابل هر چه این عمق برش بیشتر باشد لذا الگوریتم کندتر است چون مجبور است تا عمق بیشتری به بسط گرها ادامه داده .بنابراین از انجا که هرس باعث میشه تا عمق بیشتر پیش برویم لذا بروی سرعت تاثیر میگذارد .
اما یه نکته هست: :
درسته هرس الفا بتا در در اینجا سرعت رو نسبتا کاهش میدهد اما نتیجه خیلی بهتری رو بر میگرداند و تابع هیوریستیک ان با احتمال بیشتری میتواند در مرود گرهای پایانی اظهار نظر کند و در مقابل الگوریتمی که تنها به چند سط بسط درخت دست به تخمین گره های پایانی با بیشنیه عمق میزنند تخمین بدتری رو به نسب الگوریتم هرس خواهدن زد چون دارند در مورد اینده دور قضاوت میکنند اما هرس الفا بتا در مرود اینده نزدک میخواهد تخمین بزند.
بنابراین یه نقطه ضعف الگوریتم MinMax همینه و باید از تابع هیوریستیک قو تری برخوردار باشند و و نباید هزینه محاسبه این تابع رو هم فراموش کنیم که میتواند درنهایت افزایش سرعت رو خنثی کند .
هرس الفا بتا میتواند از هیوریستیک با سرعت بیشتری استفاده کند چون تا عمق بیشتری پیش میرود و اطلاعات بیشتری نسبت به حالات پایانی دارد.
در هر حال انچه که واضح هست این است که هرس افا بتا خیلی بهتر حالت معمولی عمل میکند .
سخن اخر اینکه
من با نظر دوستانی که گفتن سرعت تفاوت نخواهد کرد کاملا موافقم و همچنین سخن دوستانی که گفتن سرعت افزایش پیدا خواهد کرد اگر منظورشون میزان کارایی عامل باشه باز هم موافقم و علتش هم اینه که فرض کنید که:
فضای که در دسترس هر دو الگوریتم هست قادر به نگهادری ۱۰۰۰ نود(حالت مابعد) رو داره حال اگر هر دو الگوریتم موظف باشن از تمام این حافظه استفاده کنند و هزینه بسط هر گره در حافظه هم t در نظر بگیریم هر دو الگوریتم ۱۰۰۰ نود رو بسط خواهند داد (اما الگوریتم الفا بتا تا عمق بیشتری )و لذا هزینه بسط این ۱۰۰۰ گره یا حالت برابر با ۱۰۰۰t خواهد بود که این هزینه رو مستقل از نوع الگوریتم باید بپردازیم (سرعت یکسان). بنابراین سرعت هیچ تفاوتی نمیکنه اما باز هم عملکرد عاملی که دارد با هرس الفا بتا عمل مکیند خیلی بهتر و نزدیک به واقعیت خواهد بود(عنصر کارایی) .
فرض دیگری رو در نظر بگیرید که الگوریتمهای قادر باشند از تمام فضای حافظه ایی که به انها اختصاص داده شده بهره نبرند خب در این حالت الگوریتم الفابتا در اکثر مواقع از تمام فضا برای پیش بردن عمق جستجو بهره میبرد (۱۰۰۰t)اما الگوریتم معمولی با در نظر گرفتن عمق برش ایستا (عمق برش معمولا پویاست و ایستا نیست) میتواند به سرعت بهتری دست پیدا کند(T<=1000t) چون کافیه به عمق برش برسد و تعداد گرهایی بسط داده شده کمتر از میزان حافظه اختصاص داده شده باشد(حالت خیلی خیلی خاص و بدون در نظر گرفتن هزینه محاسبه هیوریستیک این نوع عامل که معمولا هزینه بالایی دارند چون باید اینده دور را تخمین بزنند مگر انکه عنصر کارایی رو فدای سرعت کنند)
در هر حال انچه که اهمیت دارد نظر طراح سئوال هست هر چند اگر نظر ایشان درست نباشد.