سلام دوستان.
کدام یک از این دو گزینه صحیح هست؟
1) الگوریتم اول عمق همیشه با صرف مقدار کمتری از حافظه نسبت به الگوریتم اول پهنا به جواب میرسد.
2)الگوریتم جستجوی A* (با هر هیروستیکی) همیشه تعداد کمتری گره نسبت به هر الگوریتم مطلع دیگر (با همان هیروستیک) بسط میدهد.
در پوران اولی رو درست اعلام کرده و دومی رو به این علت گفته غلط که عبارت "با هر هیروستیکی" رو آورده و گفته هیروستیک باید قابل قبول باشه.
اما در سنجش دومی رو درست اعلام کرده و گفته اولی غلطه چون :"جستجوی اول عمق بهینه نیست و ممکنه با صرف فضای بیشتری به جواب برسه"
امان از این نظرات مختلف کتابهااااااا
اگه ممکنه راهنماییم کنید. خیلی خیلی ممنونم.
سلام.
به نظر من اولی درسته. اول عمق حافظه خطی داره اما اول سطح حافظه نمایی. حالا اول عمق ممکنه اصلا به جواب نرسه اما اگر برسه با حافظه کمتری میرسه.
اینجا اصلا حرفی از بهینگی نزده که بخوایم ازش ایراد بگیریم. بحث حافظه مطرحه فقط!
گزینه دوم هم مشخصا ذکر کرده با هر هیورستیکی! پس خودش میخواسته بگه این غلطه! چون *A فقط با هیورستیک قابل قبول از بقیه بهتره.
البته تو تحلیل دومی شک دارم که منظورش حافظه مصرفیه یا نه... چون مثلا RBFS و *IDA مصرف حافظشون خطیه اما *A نمایی.
پیچیدگی حافظه توی dfs خطی است( O(b^m چون فقط گرههای مسیر رو نگه میداریم ولی توی جستجوی سطحی چون باید والدهای تمام گرهها رو نگه داره(به خاطر بدست آوردن فرزندانشان)نمایی است
جستجوی اول عمق از لحاظ زمانی بهینه نیست ولی از لحاظ فضای مصرفی بهینه است.ولی جستجوی کاملی نیست چون ممکنه به جواب نرسه و در حلقه تکرار بیفته
توی A* هم شرط قبولی تابع هیوریستیک ، کمتر یا مساوی بودن هزینه تخمینی از هزینه واقعی هست
اگر بخوایم از میون این دوتا یکی رو درست اعلام کینم من اولی رو غلط می دونم!
کافیه درختی رو تصور کنید که اگر از BFS حلش کنیم در سطح اول(نود های سمت راست) به جواب میرسه اما اگر به DFS حلش کنیم در سمت چپ ترین گره در عمق 1000 به جواب می رسه!صدها مثال دیگه هم میشه زد!
گزینه دوم هم 100% درست نیست اما از اولی درستره!بحث درموردشم خیلی مفصله و مربوط میشه hهای معادلاتی که اگه اهله روبتیک و ربات های Maze باشید بامن هم عقیده خواهید بود.
موفق باشید
سلام
گزینه دوم غلطه چون همان طور که گفتید جستجوی *A فقط در صورتی می تونه از هر الگوریتم جستجوی دیگه ایی بهتر باشه که یک هیوریسیک قابل قبول داشته باشه و نه هر هیوریستیکی .
گزینه اول هم می تونه غلط باشه .فکر کنید در درخت جستجو یک جوابی رو (مثلا a )در سطح ۱ و در شاخه سمت راست و یک جواب دیگه ایی رو (مثلا e)در سطح ۶ ام و درشاخه سمت چپ داشته باشیم حالا از اون جایی که جستجوی اول پهنا می تونه به صورت سطحی جواب رو در عمق کمتر جستجو و پیدا می کنه پس جواب شاخه سمت راست در سطح اول توسط اول پهنا(BFS) سریعتر از جواب شاخه سمت چپ در سطح ۶ ام توسط اول عمق(DFS)پیدا می شه ( در واقع اول عمق باید گره ها رو تا سطح ۶ام طی کنه تا به جواب برسه اما اول پهنا می تونه خیلی راحت اون یکی جواب رو تو سح ۱ پیدا کنه) پس در اینجا BFS حافظه کمتری رو مصرف کرده چون گره های کمتر رو تولید کرده.
نتیجه گیری این که هر دو غلطه
البته این نتیجه گیری رو من از طریق کتاب راهیان ارشد گرفتم.
حالا شما لطف کنید سوال رو کامل بزارید ببینیم باقی گزینه ها چیه!! اگر جایی اشتباه کردم راهنمایی کنید.
به نظر من هم این کلمه "همیشه" جمله اول رو اشتباه میکنه.
ممنونم از تمام دوستان.
۴ گزینه سوال اینها هستن:
۱/الگوریتم SMA* همیشه سریعتر از *A به جواب میرسه
۲/ جستجوهای کور همیشه نیاز به حافظه کمتری نسبت به جستجوهای مطلع دارن.
۳/الگوریتم اول عمق همیشه با صرف مقدار کمتری از حافظه نسبت به الگوریتم اول پهنا به جواب میرسد.
۴/ الگوریتم جستجوی A* (با هر هیروستیکی) همیشه تعداد کمتری گره نسبت به هر الگوریتم مطلع دیگر (با همان هیروستیک) بسط میدهد.
فکر میکنم گزینه ۱ به این علت غلط هست که *SMAبا محدودیت حافظه روبروست و هر لحظه ممکنه مسیری که قبلا پیمایش کرده را از حافظه خارج کنه و با مسیر جدید جایگزین کنه که باعث اتلاف زمانه.
و علت اشتباه بودن ۲ هم اینه که جست و جوهای ناآگاهانه یا همون "کور" معمولا به حافظه بیشتری نیاز دارن.
با وجود این گزینه ها شما جواب نهایی رو چه گزینهای اعلام می کنید؟
(08 بهمن 1391 11:35 ب.ظ)IT.setareh91 نوشته شده توسط: [ -> ]با وجود این گزینه ها شما جواب نهایی رو چه گزینهای اعلام می کنید؟
همون گزینه 3/ چون همیشه حافظه کمتری مصرف میکنه . البته اگر جواب در عمق نامحدود نباشه و در حلقه نیفته. که میبینیم گزینه هم روی این موارد بحثی نکرده و اشاره اش فقط به حافظه است. . البته من به صورت کلی و در حالت میانگین جواب رو صحیح میدونم و استثنا ها رو در نظر نمیگیرم
به نظر من گزینه 1 غلطه چون با توجه به پیچدگی فضایی ، *SMA از *A بهتره. اما اگردر *SMA حافظه به اندازه کافی داشته باشیم *SMA مثل *A عمل می کنه و با هم فرقی نمی کنند پس نمی شه گفت که همیشه *SMA بهتر از *A هست.
گزینه 2 هم می شه واسش مثال زد که غلطه : BFS(جستجو کور) پیچیدگی فضایی نمایی داره اما RBFS پیچیدگی فضایی (جستجو مطلع )خطی داره.
گزینه 3 و 4 هم که گفته شد.
با این وجود هیچ کدوم درست نمی شن و از این سوالا تو کنکور متاسفانه کم نیستن.
بهتره از بین بد و بدتر بد رو انتخاب کنیم که طبق سنجش لابد می شه 2 دیگه !!!!!!!
(08 بهمن 1391 05:49 ب.ظ)IT.setareh91 نوشته شده توسط: [ -> ]سوال ۱۰۶ هوش مصنوعی آی تی سلام دوستان.
کدام یک از این دو گزینه صحیح هست؟
۱) الگوریتم اول عمق همیشه با صرف مقدار کمتری از حافظه نسبت به الگوریتم اول پهنا به جواب میرسد.
۲)الگوریتم جستجوی A* (با هر هیروستیکی) همیشه تعداد کمتری گره نسبت به هر الگوریتم مطلع دیگر (با همان هیروستیک) بسط میدهد.
در پوران اولی رو درست اعلام کرده و دومی رو به این علت گفته غلط که عبارت "با هر هیروستیکی" رو آورده و گفته هیروستیک باید قابل قبول باشه.
اما در سنجش دومی رو درست اعلام کرده و گفته اولی غلطه چون :"جستجوی اول عمق بهینه نیست و ممکنه با صرف فضای بیشتری به جواب برسه"
امان از این نظرات مختلف کتابهااااااا
اگه ممکنه راهنماییم کنید. خیلی خیلی ممنونم.
گزینه اول:
به نظر من گزینه اول قطعا غلطه اخه جست و جو اول عمق کامل و بهینه نیست در نتیجه امکان داره اصلا جواب را به ما نده/...
گزینه دوم:
به نظر من گزینه دوم درسته چون الگوریتم *A با هر هیوریستکی(قابل قبول و یکنوا) کامل و بهینه است و اگر مسئله جوابی داشته باشه اونا با بسط کمترین گره پیدا میکنه/...(البته یه شرط کوچولو داره که اصلا مهم نیست/...طبق صفحه 120 رویکرد نوین در هوش مصنوعی نویسنده راسل و ترجمه راحتی)
بهترین راه برای حل این نمونه سوالات، تحلیل Average case هست همونطور که خانم fatima1537 اشاره فرمودن
اونی که بعضی دوستان میگن DFS ممکنه جواب تو سطح اول سمت راست رو خیلی دیر پیدا کنه میشه تحلیل Worst case. سوال کنکور از شما بدترین حالت رو نخواسته
گزینه 4 اشتباهش خیلی واضحه. هر هیورستیکی رو تاکید کرده دوباره با واژه ی با همان هیورستیک. کاملا مشخصه ممکنه هیورستیک تخمین بدتر از میزان واقعی زده باشه
دومی درسته چون تاکیدش روی لیست closed بوده تو کتاب پوران عین جمله آورده شده که A* با هر هیورستیکی از هر جستجوی دیگه ایی نود های کمتری رو گسترش میده . اینطور فرض کنید که جزء صفات ذاتیشه
تو تعریف اول عمق ام گفته شده که ممکنه تو یه مسیر بینهایت قرار بگیره در حالی که ج یه جایی نزدیک ریشه باشه
یعنی کامل بودن و بهینگیش مشروطه پس چون گفته همیشه غلطه
دوستان واقعا اینقدر بحث رو میشه عمیق کرد و اینقدر میشه دلیل واسه درستی و نادرستسش آوزد که بهتره جای حل سةال، نکاتی که دوستان گفتن رو یاد بگیریم.
چون مشخصا سوال غیر استانداردیه و میشه ١٠٠ جوز تفسیرش کرد.
متأسفانه زیاد پیش آمده که در هوش مصنوعی (به ویژه آی‌تی) سوالات باید تفسیر بشوند. حالا تفسیر هر کسی مشابه تفسیر طراح باشه، موفق‌تره.
قید عمومیت در این دو گزینه (هر هیورستیک + همیشه) باعث میشه که هر دوی این گزینه‌ها نادرست بشوند. اما در کل میشه اینطور برداشت کرد که در حالت کلی، پیچیدگی فضایی جستجوی اول-عمق کمتر از اول پهناست. از طرفی هیورستیک جستجوی آ-استار باید شرایط خاص خودش رو داشته باشه. قابل قبول باشه یا احیاناً یکنوا باشه.
گاهی هم سوالات هوش مصنوعی که درست را خواسته بررسی درست و درست‌تر یا بالعکس میتونه باشه. نتیجه این میشه که اینطور سوالات رو به راحتی از کنارش نباید رد شد و در همان نگاه اول هم نباید پاسخ رو انتخاب کرد.
(08 بهمن 1391 05:49 ب.ظ)IT.setareh91 نوشته شده توسط: [ -> ]سلام دوستان.
کدام یک از این دو گزینه صحیح هست؟
۱) الگوریتم اول عمق همیشه با صرف مقدار کمتری از حافظه نسبت به الگوریتم اول پهنا به جواب میرسد.
۲)الگوریتم جستجوی A* (با هر هیروستیکی) همیشه تعداد کمتری گره نسبت به هر الگوریتم مطلع دیگر (با همان هیروستیک) بسط میدهد.
دوستان من بررسی کردم گزینه دوم کاملا صحیحه و عینا توی راسل ذکر شده.
یعنی قابل قبول بودن لازم نیست.
با هر هیورستیکی برقراره!
لطفا فایل ضمیمه رو که صفحه ای از راسله رو ببینید و قسمتی که هایلایت کردم رو بخونید!
جالبه که هیچ کدوممون حتی فکرش رو هم نمیکردیم دومی درست باشه!