زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۰:۱۵ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

جستجوی BFS+ کنکور ۹۱

ارسال:
  

kati پرسیده:

جستجوی BFS+ کنکور ۹۱

سلام این سوال شاید خیلی راحت باشه اما منو گیج کرده!!

اینکه گرینه های دیگه غلط هستند رو قبول دارم اما گزینه ۴ چطوری درست میشه؟!!
آخه اگر b=3 باشه اون موقع کمترین حالتش ۴۱ گره بسط میده !! و از اون تعداد گره ایی که خود سوال مشخص کرده (۳۲)بیشتر میشه! این چطوریه؟


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۶
ارسال:
  

masoud67 پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

اول اینکه توضیح این سوال با کشیدن شکل به خوبی مفهوم میشه و با توضیح و فرمول به خوبی بیان نمیشه . بهترین کار اینه که خودتون درختهای این مسئله رو ترسیم کنید
موردی که این جا باید دقت کنید ، گره های بسط داده شده و گره های تولید شده هست
و شاید خیلی ها این اشتباه را انجام بدن که این دو مورد را اشتباه در نظر بگیرن پس توی جوابی که براتون نوشتم دقیقا به بسط داده شده و تولید شده دقت کنید
وقتی میگه ۳۲ گره بسط داده میشه ، منظور اینه که ۳۲ گره با فرزندان این ۳۲ گره تولید میشن . پس تعداد گره های بسط داده شده برابر ۳۲ و تعداد گره های تولیدی بیشتر از ۳۲ تا هستند

مورد دوم : گفته شده عمق هدف در ارتفاع ۴ هست. پس یعنی ما باید تا ارتفاع ۳ تمام گره های را تولید کنیم (به طور کامل) و حالا میریم سراغ ارتفاع ۳ و شروع میکنیم به بسط دادن گره های ارتفاع ۳ که همون تولید گره های ارتفاع ۴ میباشد
پس دو رابطه پیش میاد
۱/ گفتیم تمام نودها تا ارتفاع ۳ باید تولید بشن
پس رابطه اول [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] باشه
در کل باید در جواب دادن به این سوال به گره های تولیدی و گره های بسط داده شده دقت زیادی داشت که اگر این دو تا را اشتباه کنیم جوابی که بدست میاد اشتباه میشه
نقل قول این ارسال در یک پاسخ

ارسال:
  

zeitun پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

(۰۸ بهمن ۱۳۹۲ ۰۳:۰۸ ب.ظ)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] صدق کنن؟ منظورم اینه چرا باید بیشتر از ۳۲ باشن؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

masoud67 پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

(۱۰ بهمن ۱۳۹۲ ۰۴:۲۰ ق.ظ)zeitun نوشته شده توسط:  چرا نودهای تولیدی باید توی رابطه ی [tex]1 b b^2 b^3 > 32[/tex] صدق کنن؟ منظورم اینه چرا باید بیشتر از ۳۲ باشن؟
بهترین کار واسه فهمیدنش رسم شکل هست.
ولی یه توضیحی میدم.
تو سوال گفته ۳۲ نود بسط داده میشه. بسط داده شده یعنی اینکه فرزندانش تولید میشن. مثلا در درخت با فاکتور ۳ در نظر بگیرید
در ارتفاع ۰ ابتدا نود ریشه تولید میشه
سپس در ارتفاع ۰ نود ریشه بسط داده میشه و نودهای ارتفاع ۱ تولید میشن (پس از همین جا میشه فهمید وقتی یک نود را بسط میدیم یعنی بیشتر از یک نود را تولید کردیم) در این جا ما نود ریشه را بسط دادیم ولی غیر از نود ریشه که قبلا تولید شده بود، نودهای فرزند ریشه هم تولید شده که میشه ۴ نود تولیدی

در ارتفاع ۱ نودهای این ارتفاع را بسط میدیم یعنی نودهای ارتفاع ۲ را تولید میکنیم که ۹ تاست. پس تا اینجا ۴ نود را بسط دادیم (ارتفاع صفر ویک) و ۱۴ نود را تولید کردیم (۱ + ۳ + ۹)

در ارتفاع ۲ نودها را بسط میدیم که نودهای بسطی میشه (۱+۳+۹) و نودهای تولیدی میشه (۱+۳+۹+۲۷) . الان میشه فهمید چرا نودهای تولیدی بیشتر از ۳۲ باید باشه. چون ما ۱۴ نود بسط دادیم (هنوز به ۳۲ تا نرسیدیم) ولی ۵۱ نود را تولید کردیم.
به همین دلیل اون رابطه را نوشتم

امیدوارم توضیحات خوب بوده باشه، اگه نبود یه دور واسه خودتون شکل را رسم کنید ، متوجه میشید. منم تو این مورد یه کم گیج بودم ، نشستم ۴ تا شکل رسم کردم تا برام جا افتاد
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

kh.jafarzade پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

(۰۳ بهمن ۱۳۹۲ ۱۲:۲۳ ق.ظ)kati نوشته شده توسط:  سلام این سوال شاید خیلی راحت باشه اما منو گیج کرده!!

اینکه گرینه های دیگه غلط هستند رو قبول دارم اما گزینه ۴ چطوری درست میشه؟!!
آخه اگر b=3 باشه اون موقع کمترین حالتش ۴۱ گره بسط میده !! و از اون تعداد گره ایی که خود سوال مشخص کرده (۳۲)بیشتر میشه! این چطوریه؟

فایلی که پیوست کردین ارور میده و باز نمیشه...ظاهرا خودتون باس بیشتر روش فکر کنید..Big Grin
نقل قول این ارسال در یک پاسخ

ارسال:
  

masoud67 پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

(۰۳ بهمن ۱۳۹۲ ۱۲:۳۰ ق.ظ)kh.jafarzade نوشته شده توسط:  فایلی که پیوست کردین ارور میده و باز نمیشه...ظاهرا خودتون باس بیشتر روش فکر کنید..Big Grin
آره یه مدته بدجور فایلها ارور میده. من خودم معمولا یه فایلو باید یه بار اتچ کنم بعد حذف کنم و دوباره اتچ کنم تا درست بشه
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

kati پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

ای بابا ! عجب گیری کردیمااا !! اتفاقا حذف هم کردم و بعد دوباره اتچ کردم اما بازم نمیشه!
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

zeitun پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

فرض کنید برای مسئله ای با جست و جوی اول پهنا (BFS) و تست هدف در لحظه ی تولید نیاز به بسط دادن ۳۲ گره باشد.
اگر فاکتور انشعاب درخت جست و جو ثابت باشد و عمق درخت برابر ۵ و عمق هدف برابر ۴ باشد کدام یک از گزینه ها مقدار
فاکتور انشعاب (b) رانشان می دهد؟( فرض کنید ریشه ی درخت در عمق ۰ واقع شده است)
۱. b=2
۲. b>5
۳.[tex]2< b< 3[/tex]
۴. [tex]3\leqslant b\leqslant 5[/tex]

منم این سوالو بلد نیستم تایپ کردم یکی که بلده حلشو توضیح بده Blush
نقل قول این ارسال در یک پاسخ

ارسال:
  

atharrashno پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

(۰۸ بهمن ۱۳۹۲ ۰۱:۲۰ ق.ظ)zeitun نوشته شده توسط:  فرض کنید برای مسئله ای با جست و جوی اول پهنا (BFS) و تست هدف در لحظه ی تولید نیاز به بسط دادن ۳۲ گره باشد.
اگر فاکتور انشعاب درخت جست و جو ثابت باشد و عمق درخت برابر ۵ و عمق هدف برابر ۴ باشد کدام یک از گزینه ها مقدار
فاکتور انشعاب (b) رانشان می دهد؟( فرض کنید ریشه ی درخت در عمق ۰ واقع شده است)
۱. b=2
۲. b>5
۳.[tex]2< b< 3[/tex]
۴. [tex]3\leqslant b\leqslant 5[/tex]

منم این سوالو بلد نیستم تایپ کردم یکی که بلده حلشو توضیح بده Blush

چون تست هدف در * لحظه تولید * (فرزندان)صورت میگیره بنابر این شما وقتی در عمق ۳ داری یک گره را بسط میدی اگر هدف جز فرزندانت باشه متوجه میشی خب حالا :
اگه بابای هدف سمت راست ترین گره عمق ۳ باشه شما حداکثر این قد گره را بسط میدی
[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]

به ازای ۳و ۵ صدق میکنه برای کمتر از ۳ هم درست نیست
(گزینه ۴)
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۰
  

kati پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

مرسی از هر دو دوست عزیز که توضیح دادید.
متوجه شدم.
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۱
  

paieez پاسخ داده:

RE: جستجوی BFS+ کنکور ۹۱

من متوجه نمیشم که چرا تا عمق ۲ گره ها رو بسط میدید؟ مگه عمق درخت ۵ با سطح ریشه ۰ نیست؟ و مگه هدف تو عمق ۴ نیست؟ پس تا عمق ۳ باید بسط داده شه و ین عمق ۴ هست که معلوم نیست چند تا بسط داده میشه ولی مطمئنا یه گره تو عمق ۴ بسط داده شده که عمق درخت ۵ شده. با این رویکرد گزینه ۴ درست نیست. به نظر من گزینه ۳ درسته. اگه تا عمق ۳ درخت پر باشه . البته یعنی چی که فاکتور انشعاب بین دو و سه باشه ؟!
دوستان عزیز کلید سنجش رو میدونن کدوم گزینه بوده؟
اگر هم میگید تا عمق ۲ بسط میدیم لطفا یکی رو کاغذ بکشه که چطوری عمق درخت تو BFS با این شرایط ۵ میشه.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  در جستجوی اساتید امنیت wskf ۰ ۱,۸۷۸ ۱۸ فروردین ۱۳۹۹ ۰۸:۴۶ ب.ظ
آخرین ارسال: wskf
  مباحث آزاد آزمون دکترا ۹۸ (قبل ار کنکور-بعد از کنکور) taha.maten ۰ ۲,۱۰۲ ۲۴ بهمن ۱۳۹۷ ۱۲:۴۶ ب.ظ
آخرین ارسال: taha.maten
  دوران در درخت جستجوی دودویی tarane.68 ۵ ۵,۷۹۲ ۱۷ مهر ۱۳۹۷ ۰۱:۴۰ ب.ظ
آخرین ارسال: fsadat7
  مصاحبه با ۷۹ نرم افزار(کنکور مهندسی کامپیوتر) و ۱۶۲ شبکه(کنکور آی تی) theshatoonak ۳ ۷,۳۰۰ ۲۲ آبان ۱۳۹۶ ۰۳:۳۸ ب.ظ
آخرین ارسال: yahmat
Information در جستجوی منبعی ساده، مختصر و مفید برای معادلات دیفرانسیل SepehrE46 ۱ ۲,۲۳۳ ۲۶ مهر ۱۳۹۶ ۰۴:۵۸ ب.ظ
آخرین ارسال: James Sullivan
  جستجوی اول بهترین amir_ghanati ۱ ۱,۶۳۳ ۱۶ شهریور ۱۳۹۶ ۰۸:۵۲ ب.ظ
آخرین ارسال: amir_ghanati
  روش DFS و BFS kilookiloo ۲ ۳,۱۷۳ ۲۶ فروردین ۱۳۹۶ ۰۲:۲۲ ب.ظ
آخرین ارسال: kilookiloo
  جستجوی موفق و ناموفق در درهم سازی wskf ۴ ۳,۶۸۸ ۲۷ بهمن ۱۳۹۵ ۰۷:۳۶ ب.ظ
آخرین ارسال: wskf

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close