سلام این سوال شاید خیلی راحت باشه اما منو گیج کرده!!
اینکه گرینه های دیگه غلط هستند رو قبول دارم اما گزینه ۴ چطوری درست میشه؟!!
آخه اگر b=3 باشه اون موقع کمترین حالتش ۴۱ گره بسط میده !! و از اون تعداد گره ایی که خود سوال مشخص کرده (۳۲)بیشتر میشه! این چطوریه؟
(۰۳ بهمن ۱۳۹۲ ۱۲:۲۳ ق.ظ)kati نوشته شده توسط: سلام این سوال شاید خیلی راحت باشه اما منو گیج کرده!!
اینکه گرینه های دیگه غلط هستند رو قبول دارم اما گزینه ۴ چطوری درست میشه؟!!
آخه اگر b=3 باشه اون موقع کمترین حالتش ۴۱ گره بسط میده !! و از اون تعداد گره ایی که خود سوال مشخص کرده (۳۲)بیشتر میشه! این چطوریه؟
فایلی که پیوست کردین ارور میده و باز نمیشه...ظاهرا خودتون باس بیشتر روش فکر کنید..
(۰۳ بهمن ۱۳۹۲ ۱۲:۳۰ ق.ظ)kh.jafarzade نوشته شده توسط: فایلی که پیوست کردین ارور میده و باز نمیشه...ظاهرا خودتون باس بیشتر روش فکر کنید..آره یه مدته بدجور فایلها ارور میده. من خودم معمولا یه فایلو باید یه بار اتچ کنم بعد حذف کنم و دوباره اتچ کنم تا درست بشه
ای بابا ! عجب گیری کردیمااا !! اتفاقا حذف هم کردم و بعد دوباره اتچ کردم اما بازم نمیشه!
فرض کنید برای مسئله ای با جست و جوی اول پهنا (BFS) و تست هدف در لحظه ی تولید نیاز به بسط دادن ۳۲ گره باشد.
اگر فاکتور انشعاب درخت جست و جو ثابت باشد و عمق درخت برابر ۵ و عمق هدف برابر ۴ باشد کدام یک از گزینه ها مقدار
فاکتور انشعاب (b) رانشان می دهد؟( فرض کنید ریشه ی درخت در عمق ۰ واقع شده است)
۱. b=2
۲. b>5
۳.[tex]2< b< 3[/tex]
۴. [tex]3\leqslant b\leqslant 5[/tex]
منم این سوالو بلد نیستم تایپ کردم یکی که بلده حلشو توضیح بده
(۰۸ بهمن ۱۳۹۲ ۰۱:۲۰ ق.ظ)zeitun نوشته شده توسط: فرض کنید برای مسئله ای با جست و جوی اول پهنا (BFS) و تست هدف در لحظه ی تولید نیاز به بسط دادن ۳۲ گره باشد.
اگر فاکتور انشعاب درخت جست و جو ثابت باشد و عمق درخت برابر ۵ و عمق هدف برابر ۴ باشد کدام یک از گزینه ها مقدار
فاکتور انشعاب (b) رانشان می دهد؟( فرض کنید ریشه ی درخت در عمق ۰ واقع شده است)
۱. b=2
۲. b>5
۳.[tex]2< b< 3[/tex]
۴. [tex]3\leqslant b\leqslant 5[/tex]
منم این سوالو بلد نیستم تایپ کردم یکی که بلده حلشو توضیح بده
چون تست هدف در * لحظه تولید * (فرزندان)صورت میگیره بنابر این شما وقتی در عمق ۳ داری یک گره را بسط میدی اگر هدف جز فرزندانت باشه متوجه میشی خب حالا :
اگه بابای هدف سمت راست ترین گره عمق ۳ باشه شما حداکثر این قد گره را بسط میدی
[tex]1 b b^{2} b^{3}[/tex]
اگه بابای هدف اولین گره (سمت چپ ترین گره )عمق ۳ یاشه شما این قد گره را بسط میدی
[tex]1 b b^{2} 1[/tex]
گزینه ها باید تو این نامساوی صدق کنه:
[tex]1 b b^{2} 1\leq 32\leq 1 b b^{2} b^{3}[/tex]
به ازای ۳و ۵ صدق میکنه برای کمتر از ۳ هم درست نیست
(گزینه ۴)
اول اینکه توضیح این سوال با کشیدن شکل به خوبی مفهوم میشه و با توضیح و فرمول به خوبی بیان نمیشه . بهترین کار اینه که خودتون درختهای این مسئله رو ترسیم کنید
موردی که این جا باید دقت کنید ، گره های بسط داده شده و گره های تولید شده هست
و شاید خیلی ها این اشتباه را انجام بدن که این دو مورد را اشتباه در نظر بگیرن پس توی جوابی که براتون نوشتم دقیقا به بسط داده شده و تولید شده دقت کنید
وقتی میگه ۳۲ گره بسط داده میشه ، منظور اینه که ۳۲ گره با فرزندان این ۳۲ گره تولید میشن . پس تعداد گره های بسط داده شده برابر ۳۲ و تعداد گره های تولیدی بیشتر از ۳۲ تا هستند
مورد دوم : گفته شده عمق هدف در ارتفاع ۴ هست. پس یعنی ما باید تا ارتفاع ۳ تمام گره های را تولید کنیم (به طور کامل) و حالا میریم سراغ ارتفاع ۳ و شروع میکنیم به بسط دادن گره های ارتفاع ۳ که همون تولید گره های ارتفاع ۴ میباشد
پس دو رابطه پیش میاد
۱/ گفتیم تمام نودها تا ارتفاع ۳ باید تولید بشن
پس رابطه اول [tex]1 b b^2 < 32[/tex]
حواستون باشه اینجا ارتفاع ۳ را نمیاریم. چون ۳۲ تعداد گره های بسط داده شده هست نه گره های تولیدی. بازهم میگم ما گره های ارتفاع ۳ را تولید کردیم ولی هنوز بسط ندادیم.
از رابطه بالا اگر b=6 را قرار بدیم متوجه میشیم که مشکل داره پس برای b های بزرگتر از ۵ جواب نمیده
[tex]1 6 6^2 = 43 \nless 32[/tex]
یا به عبارتی اگر فاکتور انشعاب ۶ باشه وقتی تمام گره ها تا ارتفاع ۲ را تولید کنیم ، این تعداد گره تولیدی برابر است با ۴۳ . پس یعنی ۳۲امین گره در ارتفاع ۲ میباشد که با بسط دادن آن گره هدف در ارتفاع ۳ قرار میگیره که با شرط مسئله جور نیست
ولی برای ۵ رابطه صحیحه
۲ .وقتی میگیم نود هدف در ارتفاع ۴ هست، یعنی زمانی که در ارتفاع سه هستیم و داریم نودهای ارتفاع ۴ را بسط میدیم هدف پیدا میشه.
پس از طرفی تعداد های نودهای تولیدی باید در این رابطه نیز صدق کنن
[tex]1 b b^2 b^3 > 32[/tex]
مثلا اگر B = 2 را بذاریم رابطه بالا به این شکل میشه
[tex]1 b b^2 b^3 = 1 2 4 8 16 = 31 \ngtr 32[/tex]
معنی این رابطه این میشه که وقتی فاکتور انشعاب دو باشه، اگر گره ها را تا ارتفاع ۴ تولید کنیم هنوز گره هدف را پیدا نکردیم و باید نودهای ارتفاع ۴ را بسط بدیم (تولید نودهای ارتفاع ۵) تا هدف پیدا بشه که این با فرض مسئله جور نیست چون هدف در ارتفاع ۵ قرار میگیره
تو این مورد به ازای فاکتور ۳ معادله درسته
که از دو قسمت بالا متوجه میشیم که فاکتور انشعاب باید [tex]3\leqslant b\leqslant 5[/tex] باشه
در کل باید در جواب دادن به این سوال به گره های تولیدی و گره های بسط داده شده دقت زیادی داشت که اگر این دو تا را اشتباه کنیم جوابی که بدست میاد اشتباه میشه
(۰۸ بهمن ۱۳۹۲ ۰۳:۰۸ ب.ظ)masoud67 نوشته شده توسط: اول اینکه توضیح این سوال با کشیدن شکل به خوبی مفهوم میشه و با توضیح و فرمول به خوبی بیان نمیشه . بهترین کار اینه که خودتون درختهای این مسئله رو ترسیم کنید
موردی که این جا باید دقت کنید ، گره های بسط داده شده و گره های تولید شده هست
و شاید خیلی ها این اشتباه را انجام بدن که این دو مورد را اشتباه در نظر بگیرن پس توی جوابی که براتون نوشتم دقیقا به بسط داده شده و تولید شده دقت کنید
وقتی میگه ۳۲ گره بسط داده میشه ، منظور اینه که ۳۲ گره با فرزندان این ۳۲ گره تولید میشن . پس تعداد گره های بسط داده شده برابر ۳۲ و تعداد گره های تولیدی بیشتر از ۳۲ تا هستند
مورد دوم : گفته شده عمق هدف در ارتفاع ۴ هست. پس یعنی ما باید تا ارتفاع ۳ تمام گره های را تولید کنیم (به طور کامل) و حالا میریم سراغ ارتفاع ۳ و شروع میکنیم به بسط دادن گره های ارتفاع ۳ که همون تولید گره های ارتفاع ۴ میباشد
پس دو رابطه پیش میاد
۱/ گفتیم تمام نودها تا ارتفاع ۳ باید تولید بشن
پس رابطه اول [tex]1 b b^2 < 32[/tex]
حواستون باشه اینجا ارتفاع ۳ را نمیاریم. چون ۳۲ تعداد گره های بسط داده شده هست نه گره های تولیدی. بازهم میگم ما گره های ارتفاع ۳ را تولید کردیم ولی هنوز بسط ندادیم.
از رابطه بالا اگر b=6 را قرار بدیم متوجه میشیم که مشکل داره پس برای b های بزرگتر از ۵ جواب نمیده
[tex]1 6 6^2 = 43 \nless 32[/tex]
یا به عبارتی اگر فاکتور انشعاب ۶ باشه وقتی تمام گره ها تا ارتفاع ۲ را تولید کنیم ، این تعداد گره تولیدی برابر است با ۴۳ . پس یعنی ۳۲امین گره در ارتفاع ۲ میباشد که با بسط دادن آن گره هدف در ارتفاع ۳ قرار میگیره که با شرط مسئله جور نیست
ولی برای ۵ رابطه صحیحه
۲ .وقتی میگیم نود هدف در ارتفاع ۴ هست، یعنی زمانی که در ارتفاع سه هستیم و داریم نودهای ارتفاع ۴ را بسط میدیم هدف پیدا میشه.
پس از طرفی تعداد های نودهای تولیدی باید در این رابطه نیز صدق کنن
[tex]1 b b^2 b^3 > 32[/tex]
مثلا اگر B = 2 را بذاریم رابطه بالا به این شکل میشه
[tex]1 b b^2 b^3 = 1 2 4 8 16 = 31 \ngtr 32[/tex]
معنی این رابطه این میشه که وقتی فاکتور انشعاب دو باشه، اگر گره ها را تا ارتفاع ۴ تولید کنیم هنوز گره هدف را پیدا نکردیم و باید نودهای ارتفاع ۴ را بسط بدیم (تولید نودهای ارتفاع ۵) تا هدف پیدا بشه که این با فرض مسئله جور نیست چون هدف در ارتفاع ۵ قرار میگیره
تو این مورد به ازای فاکتور ۳ معادله درسته
که از دو قسمت بالا متوجه میشیم که فاکتور انشعاب باید [tex]3\leqslant b\leqslant 5[/tex] باشه
در کل باید در جواب دادن به این سوال به گره های تولیدی و گره های بسط داده شده دقت زیادی داشت که اگر این دو تا را اشتباه کنیم جوابی که بدست میاد اشتباه میشه
چرا نودهای تولیدی باید توی رابطه ی [tex]1 b b^2 b^3 > 32[/tex] صدق کنن؟ منظورم اینه چرا باید بیشتر از ۳۲ باشن؟
(۱۰ بهمن ۱۳۹۲ ۰۴:۲۰ ق.ظ)zeitun نوشته شده توسط: چرا نودهای تولیدی باید توی رابطه ی [tex]1 b b^2 b^3 > 32[/tex] صدق کنن؟ منظورم اینه چرا باید بیشتر از ۳۲ باشن؟بهترین کار واسه فهمیدنش رسم شکل هست.
ولی یه توضیحی میدم.
تو سوال گفته ۳۲ نود بسط داده میشه. بسط داده شده یعنی اینکه فرزندانش تولید میشن. مثلا در درخت با فاکتور ۳ در نظر بگیرید
در ارتفاع ۰ ابتدا نود ریشه تولید میشه
سپس در ارتفاع ۰ نود ریشه بسط داده میشه و نودهای ارتفاع ۱ تولید میشن (پس از همین جا میشه فهمید وقتی یک نود را بسط میدیم یعنی بیشتر از یک نود را تولید کردیم) در این جا ما نود ریشه را بسط دادیم ولی غیر از نود ریشه که قبلا تولید شده بود، نودهای فرزند ریشه هم تولید شده که میشه ۴ نود تولیدی
در ارتفاع ۱ نودهای این ارتفاع را بسط میدیم یعنی نودهای ارتفاع ۲ را تولید میکنیم که ۹ تاست. پس تا اینجا ۴ نود را بسط دادیم (ارتفاع صفر ویک) و ۱۴ نود را تولید کردیم (۱ + ۳ + ۹)
در ارتفاع ۲ نودها را بسط میدیم که نودهای بسطی میشه (۱+۳+۹) و نودهای تولیدی میشه (۱+۳+۹+۲۷) . الان میشه فهمید چرا نودهای تولیدی بیشتر از ۳۲ باید باشه. چون ما ۱۴ نود بسط دادیم (هنوز به ۳۲ تا نرسیدیم) ولی ۵۱ نود را تولید کردیم.
به همین دلیل اون رابطه را نوشتم
امیدوارم توضیحات خوب بوده باشه، اگه نبود یه دور واسه خودتون شکل را رسم کنید ، متوجه میشید. منم تو این مورد یه کم گیج بودم ، نشستم ۴ تا شکل رسم کردم تا برام جا افتاد
مرسی از هر دو دوست عزیز که توضیح دادید.
متوجه شدم.
من متوجه نمیشم که چرا تا عمق ۲ گره ها رو بسط میدید؟ مگه عمق درخت ۵ با سطح ریشه ۰ نیست؟ و مگه هدف تو عمق ۴ نیست؟ پس تا عمق ۳ باید بسط داده شه و ین عمق ۴ هست که معلوم نیست چند تا بسط داده میشه ولی مطمئنا یه گره تو عمق ۴ بسط داده شده که عمق درخت ۵ شده. با این رویکرد گزینه ۴ درست نیست. به نظر من گزینه ۳ درسته. اگه تا عمق ۳ درخت پر باشه . البته یعنی چی که فاکتور انشعاب بین دو و سه باشه ؟!
دوستان عزیز کلید سنجش رو میدونن کدوم گزینه بوده؟
اگر هم میگید تا عمق ۲ بسط میدیم لطفا یکی رو کاغذ بکشه که چطوری عمق درخت تو BFS با این شرایط ۵ میشه.