سلام دوستا ن
فرق اینکه سوال میگه تست هدف در لحظه تولید یا در لحظه بسط . چیه؟
در جستجوهای bfs و A* میگگم
(۲۳ فروردین ۱۳۹۶ ۱۰:۵۰ ب.ظ)wskf نوشته شده توسط: سلام دوستا ن
فرق اینکه سوال میگه تست هدف در لحظه تولید یا در لحظه بسط . چیه؟
در جستجوهای bfs و A* میگگم
سلام . داریم گره A رو بسط میدیم که فرزندای E و G داره که G هدفه . وقتی میگه در لحظه تولید یعنی اینکه همین الآن که G رو تولید میکنیم ببینم هدفه یا نه . اگه بود که تمومه اگه نه گره بعدی رو تولید میکنیم . ولی وقتی میگه در لحظه بسط , گره های فرزند A رو تولید میکنیم که EوG هستند , بعد هروقت نوبت بسط Gرسید و خواستیم فرزندانشو تولید کنیم تست میکنیم ببینیم G هدف هست یا نه .
وقتی یک گره رو بسط می دیم فرزنداش تولید میشن و وارد صف اولویت میشن.
وقتی یک گره کاندید بسط دادنه از صف اولویت خارج میشه و میاد که بسط داده بشه.
پس لحظه بسط میشه لحظه خروج از صف اولویت؛ لحظه تولید میشه لحظه ورود به صف اولویت
شما وقتی در لحظه بسط آزمون هدف رو انجام بدی، چون لحظه خروج از صف اولویته، اگه گره هدف باشه دیگه این گره بسط داده نمیشه ولی اگه هدف نباشه، بسط داده میشه و فرزنداش تولید میشن. تو این حالت اگه گره هدف سمت راست ترین گره درخت جستجو باشه (بدترین حالت) به جز برای همین گره آخر تمام گره های ردیف بعدی هم تولید میشن و این یه جورایی سربار حساب میشه و خوب نیست.
برای آزمون هدف در لحظه تولید، اول گره بسط داده میشه بعد فرزنداش موقع ورود به صف چک میشن و اگه هدف باشن مشخص میشن. این جا اگه هدف بازم سمت راست ترین گره درخت جستجو باشه، دیگه برخلاف حالت قبل یه ردیف اضافه گره تولید نمیشه.
*برای این دو فصل جستجوی آگاهانه و ناآگاهانه، فیلمای دکتر رهنمون خیلی خوبن. قشنگ مفاهیمو تفکیک می کنه تو ذهن