(۱۴ دى ۱۳۸۹ ۱۱:۴۲ ب.ظ)sos006 نوشته شده توسط:  با سلام.من دو سه جلسه بیشتر سر کلاس هوش نرفتم. چند تا مشکل دارم.لطفا منبع مناسب هم اگه میشه واسه آزمون ارشد معرفی کنید.من خودم دارم از رو پوران میخونم

۱- منظور از بهینگی در یک الگوریتم جستجو چیست؟آیا منظور این است که اگر چند گره هدف داشته باشیم الگوریتم باید هدفی که نزدیکتر است را بیابد؟که اگر چنین باشد پس bfs بهینه است. ولی باز هم نکته دیگری این نظر بنده را نقض میکند که کم عمقترین هدف لزوما هدف بهینه نیست؟چرا؟
۲- تفاوت Tree-Search , Graph-Search چیه؟استفاده هر کدوم کجاست؟
۳- تحلیل و توضیح نکات مهم جستجوی دوطرفه رو لطفا بیان بفرمایید.من این روش جستجو رو چند بار خوندم ولی هموز نفهمیدم کجا کاربرد داره؟آخه اگه ما بدونیم که گره هدف کجاست دیگه جستجویی نیاز نیست که انجام بدیم.ثانیا اگه میشه طرز کارشو با یه مثال از خودتون توضیخ بدین؟
۴-شرط بهینه بودن الگوریتم bfs رو هم لطفا با مثال عملی توضیح بدین و همچنین بفرمایید که چرا اگه این شرط برقرار نباشه جستجو بهینه نمیشه؟
۵-صفحه ۸۲ کتاب پوران گفته شده‌: در میان الگوریتم های بهینه،*ََA از نظر بهینگی کارا است.یعنی هیچ الگوریتم بهینه دیگری تضمین نمیکند که تعداد کمتری نود نسبت به *A گسترش دهد.منظور از الگوریتم بهینه دیگر ،الگوریتم های در بین آگاهنه است؟

کم عمق ترین هدف در صورتی که هزینه اعمال یکسان باشه‌، لزوماً بهینه است. graph Search هم برای زمانی که حلقه داریم( یه گره از طریق چند مسیر قابل دسترسی است )استفاده می شود
در مورد *A هم بهینه است بشرطی که هیورستیک آن قابل قبول باشد( کمتر از هزینه واقعی تخمین بزند) پس هیچ روشی از *A از نظر بهینگی بهتر نیست اما *A مسئله حافظه دارد پس از روش مناسبی *SMA استفاده می شود و در صورتی کامل است که عمق هدف از حافظه بیشتر نباشد
در مورد دانستن گره هدف می توانید مسئله ۸ وزیر را در نظر بگیرید که نود هدف مشخص است اما در مسئله بازی شطرنج هدف کاملاَ واضح نیست یعنی باید یه تعریف ضمنی از برد داشته باشیم( مثلاَ توی n حرکت حداکثر ببریم یا باید به فلان سبک بازی کرد) در حالی که در مسئله ۸ وزیر اصلاً مسیر راه حل مهم نیست.( مسیر مهم نسیت اما روش مهمه چون با الگوریتم ضیف نمی توان مسئله چند میلیون وزیر را حل کرد )

با اجازه دوستمون ۱۲۸ یه پاسخ شکل دار می ذارم:


در تصویر بالا فرض کنید هزینه هر مرحله یکسان باشه.
فرض کنید یک هدف، گره ۷ و یک هدف دیگه، گره ۱۰ باشه.
اگر از bfs استفاده کنید اول ۷ و بعدش ۱۰ رو پیدا می کنید. از اونجا که هزینه پیدا کردن ۷ کمتره پس ۷ راه حل بهینه است و bfs اون رو زودتر از راه حل های دیگه (گره شماره ۱۰) پیدا کرده. پس بهینه است.

۱-منظور از بهینگی اینه که اگر یک مسئله دارای چندین جواب بود و الگوریتم فقط یک جواب را به ما بدهد آن جواب بهترین جواب باشد.لزوما این جواب بهینه کم عمق ترین نیست!

۲-از tree search وقتی استفاده میشه که اولا مسیر رسیدن به هدف برای ما مهم باشه ثانیا طرح الگوریتم ما به گونه ای باشه
که در هر مرحله یک انتساب داشته باشیم یعنی در هر سطح یک گره انتخاب می کنیم و و قتی اون گره انتخاب شد دوباره به خونه قبلی بر نمی گردیم و از اونجا برای انتساب گره بعدی در سطح بعد تلاش می کنیم.در این جا یک درخت تولید می شود (یعنی دور نداریم)

۳-جستجوی دو طرفه وقتی استفاده میشه که غایت مسئله رسیدن به هدف هست و لی مسیر رسیدن به هدف مهم‌تر است. و به قدری سطح گراف جستجو بزرگ است که ما با اینکه هدف را می شناسیم ممکنه اگر فقط از ابتدا شروع کنیم در رسیدن به اون گمراه شویم.در واقع اینجا در نصف مسیر از الگوریتم عقب گرد استفاده می کنیم.مثل اینکه شما می دونید مبدا آراد و هدف بخارست است.ولی مطمئن نیستید این راهی که الگوریتم از آراد پیش گرفته در نهایت به بخارست می خورد یا نه؟ممکن است به بن بست بخوریم و در شهری قرار بگیریم که به هیچ طریق مسیری به سمت بخارست در آن نباشد و مجبور باشیم که مسیر پیموده شده در گراف را به عقب برگردیم که هزینه زمانی و مکانی بسیار گزافی در بر دارد.
بارز ترین خصوصیت جستجوی دو طرفه پایین آوردن مرتبه‌ی زمانی استO(2^n%2

۴-فرض کن می خوای از آراد بری به بخارست.الان دنبال مسیر رفتن به بخارست می گردی و فرض کن تنها معیارت برای انتخاب راه کمترین فاصله یعنی پیمودن کمترین مسافت باشه.و باز فرض کن ما یک جاده مستقیم از اراد به بخارست به طول ۴۵۸ کیلوتر داریم.الگوریتم bfs کاری که می کنه اینه که گره های فرزند آراد(که در اینجا شهر هایی هستند که جاده مستقیم و بی واسطه با گره‌ی پدر دارند)را گسترش داده و به ترتیب آن‌ها را ملاقات می کند.در بین این فرزند‌ها بخارست که همون هدف است نیز دیده می شود و الگوریتم سریعا این جواب را با طول ۴۵۸ به عنوان جواب برمی گرداند.ولی وقتی به نقشه یا درخت جستجو نگاه می کنی متوجه می شوی که ازآراد مسیری به شهر A با ۵۰ کیلومتر و از A مسیری به B با ۱۲۰ کیلومتر و از Bمسیری به بخارست با ۸۰ کیلومتر وجود دارد که جمعا می شود ۲۵۰ کیلومتر که خیلی از جواب قبلی بهتر است.در اینجا الگوریتم BFS راه بهینه را پیدا نکرده..... در اینجا هدف دورتر (هدفی که در سطوح پایین تری از درخت قرار گرفته)یهینه‌تر بوده...

۵-فکر کنم منظور کتاب در بین الگوریتم های آگاهانه باشه.البته SMA* , RTA* همه جزو همون دسته‌ی A* هستند.