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

راهنمایی درمورد سوال آزمون تسلط ۱ سوال ۱۳۸ (دفترچه ۲) - جستجوی اول سطح

ارسال:
  

hosnieh پرسیده:

راهنمایی درمورد سوال آزمون تسلط ۱ سوال ۱۳۸ (دفترچه ۲) - جستجوی اول سطح

سلام،

دوستان اگه لطف کنن جواب سوال ۱۳۸ (دفترچه ۲، صفحه ۱۲) رو توضیح بدن ممنون میشم. تو پاسخنامه گفته جستجوی اول سطح مسیر بهینه پیدا میکنه، اما بنظر من نه اول عمق پیدا میکنه نه اول سطح Big Grin
ممنون میشم دوستانی که سوال دارن راهنمایی کنند.

۰
ارسال:
  

pos پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

توی جستجوی عمقی اگر انتخاب یالها به ترتیب حروف الفبا باشه میشه SADCG که مسیر بهینه نیست. ولی در جستجوی اول سطح ابتدا S انتخاب میشه بعد فرزندانش که میشه AB و در سطح بعد ابتدا D بعد G که برابر با هدف هست پس مسیر میشه SAG که مسیر بهینه هست.

۰
ارسال:
  

ahmadnouri پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

من سوالالت سنجش رو ندارم
اما اگه هزینه مسیر‌ها با هم برابر باشن الگوریتم Bfs مسیر بهینه رو پیدا می کنه .

۰
ارسال:
  

hosnieh پاسخ داده:

RE: راهنمایی درمورد سوال آزمون تسلط ۱


اینم سوال واسه دوستانی که ندارن.
dfs فرزند چپ رو گسترش میده تا پایین، بنابراین راه حلش تو این مسئله بهینه نیست.
bfs اول چپ بعد راست رو گسترش میده بعد میاد سراغ فرزند فرزند چپ، بنابراین این هم در این مسئله نمی تونه به جواب بهینه برسه.
اگه جایی از برداشتم اشتباه راهنماییم کنید.
ممنون

۰
ارسال:
  

ahmadnouri پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

من هم نظرم همون گزینه‌ی ۳ اه

راستی پیمایش BFsو dfs رو روی گراف های وزن دار چطوری عمل می کنن؟ من که جایی پیاده سازی این پیمایش‌ها رو روی گراف های وزن دار ندیدم اگه دوستان دیدن یه توضیحی بدن

۰
ارسال:
  

hosnieh پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

سوال دیگه ای هم که هست اینکه اگه bfs اینجا راه حل بهینه رو پیدا نمیکنه پس چطور میگیم این الگوریتم بهینه است؟

۰
ارسال:
  

ahmadnouri پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

الگوریتم Bfs سطح به سطح پیمایش میکنه یعنی قبل از هر راس در فاصله‌ی ۱+K تمام راس هادر فاصله k از راس شروع رو پیدا می کنه و چون با اولویت اونا رو پیمایش می کنه پس حتما تا فاصله‌ی K مسیری رو که بهینه است پیمایش می کنه.( البته زمانی که وزن یالها یکسان باشن)

۰
ارسال:
  

pos پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟

ارسال:
  

Masoud05 پاسخ داده:

RE: راهنمایی درمورد سوال آزمون تسلط ۱

(۲۳ آبان ۱۳۹۰ ۰۸:۰۳ ب.ظ)pos نوشته شده توسط:  bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟

bfs کم عمق ترین هدف رو بر میگردونه که این لزوماً جواب بهینه نخواهد بود
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۰
  

pos پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

(۲۳ آبان ۱۳۹۰ ۰۸:۱۷ ب.ظ)Masoud05 نوشته شده توسط:  
(23 آبان ۱۳۹۰ ۰۸:۰۳ ب.ظ)pos نوشته شده توسط:  bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟

bfs کم عمق ترین هدف رو بر میگردونه که این لزوماً جواب بهینه نخواهد بود

خوب الان که حالت کلی را نخواسته. جواب را با توجه به گراف می خواد. مگه توی این گراف bfs راه حل بهینه را نمیده؟ در حالت کلی هم فکر کنم bfs فکر کنم جواب بهینه را برمیگرداندا. شما مطمئنی bfs در حالت کلی بهینه نیست؟

ارسال: #۱۱
  

Masoud05 پاسخ داده:

RE: راهنمایی درمورد سوال آزمون تسلط ۱

(۲۳ آبان ۱۳۹۰ ۰۸:۲۵ ب.ظ)pos نوشته شده توسط:  
(23 آبان ۱۳۹۰ ۰۸:۱۷ ب.ظ)Masoud05 نوشته شده توسط:  
(23 آبان ۱۳۹۰ ۰۸:۰۳ ب.ظ)pos نوشته شده توسط:  bfs مسیر بهینه را پیدا می کند ولی dfs مسیر بهینه را پیدا نمی کند(در صورتی که‌تر تیب گسترش گره‌ها بر اساس حروف الفا باشه). خودشون کدوم گزینه را جواب اعلام کردند؟

bfs کم عمق ترین هدف رو بر میگردونه که این لزوماً جواب بهینه نخواهد بود

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

۰
ارسال: #۱۲
  

ahmadnouri پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

Masoud05 من توضیحی که ارائه دادین رو متوجه نشدم اگه میشه واضحتر و ساده‌تر برای من بی سواد توضیح بدین

من یه توضیحی هم در مورد بهینه بودن Bfs بدم
من در پست قبلیم گفتم اگه یال‌ها وزن یکسانی داشته باشنBfs بهینه است چون کوتاه ترین مسیر از نظر تعداد یال‌ها از راس شروع رو بر می گردونه اینی که من گفتم درسته دیگه؟ نه؟

ارسال: #۱۳
  

Masoud05 پاسخ داده:

RE: راهنمایی درمورد سوال آزمون تسلط ۱

(۲۳ آبان ۱۳۹۰ ۰۹:۱۲ ب.ظ)ahmadnouri نوشته شده توسط:  Masoud05 من توضیحی که ارائه دادین رو متوجه نشدم اگه میشه واضحتر و ساده‌تر برای من بی سواد توضیح بدین

من یه توضیحی هم در مورد بهینه بودن Bfs بدم
من در پست قبلیم گفتم اگه یال‌ها وزن یکسانی داشته باشنBfs بهینه است چون کوتاه ترین مسیر از نظر تعداد یال‌ها از راس شروع رو بر می گردونه اینی که من گفتم درسته دیگه؟ نه؟

شما استادین‌، اینی که شما میگید درسته.
اگه یال‌ها وزن نداشت و یا وزن منفی هم داخلش باشه لزوما کم عمق ترین هدف‌، هدف بهینه نیست . یه مثال برا خودت بزن که چند تا هدف داخلش باشه و هدف بهینه خودت جوری انتخاب کن که عمقش از مابقی اهداف بیشتر باشه تا به چیزی که گفتم بررسی . البته داخل کتاب پوران این نکته رو مستقیماً آورده.( فصل حل مسئله با استفاده از جستجو )
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۴
  

hosnieh پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

خودشون گفتن bfs. ولی من هنوزم معتقدم نه bfs نه dfs تو این سوال جواب بهینه نمیدن.( شاید چون یال‌ها وزن دارند)
من جواب سوالم هنوز نگرفتم!

۰
ارسال: #۱۵
  

hosnieh پاسخ داده:

راهنمایی درمورد سوال آزمون تسلط ۱

استدلال شما درسته ولی خب تو صورت سوال اشاره ای به انتخاب بر اساس حروف الفبا نشده، پیش فرض ذهنی هم فرزند چپ اول بعد راست هستش.
ممنون از پاسختون

ارسال: #۱۶
  

nfe89 پاسخ داده:

RE: راهنمایی درمورد سوال آزمون تسلط ۱

(۲۴ آبان ۱۳۹۰ ۰۷:۴۶ ب.ظ)hosnieh نوشته شده توسط:  استدلال شما درسته ولی خب تو صورت سوال اشاره ای به انتخاب بر اساس حروف الفبا نشده، پیش فرض ذهنی هم فرزند چپ اول بعد راست هستش.
ممنون از پاسختون

پیشفرض حروف الفباست !
چپ و راست نگید. ما داریم روی گراف پیمایش میکنیم.
یه گراف رو میتونی گره هاشو جابجا کنی (جوری که اتصال گره‌ها و هزینه یالها فرقی نکنه )
تو این مثال میتونی جوری جابجا کنی که G بشه فرزند سمت چپ A
پس اینکه بگیم پیشفرض اول چپه اشتباست
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرخصی در ترم اول و سپس انصراف MSZ ۱۶ ۳۲,۱۷۵ ۲۱ مهر ۱۳۹۹ ۱۱:۱۹ ب.ظ
آخرین ارسال: Allen
Star درخواست کمک و راهنمایی برای شرکت در آزمون ارشد marvelous ۸ ۱,۵۷۸ ۲۲ شهریور ۱۳۹۹ ۰۱:۳۳ ق.ظ
آخرین ارسال: Start
  مشکل در حل تست ۲۲ فصل اول کتاب گسسته یوسفی pure.yaser ۷ ۲,۵۷۶ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۵۴ ب.ظ
آخرین ارسال: mohsentafresh
  در جستجوی اساتید امنیت wskf ۰ ۳۳۹ ۱۸ فروردین ۱۳۹۹ ۰۸:۴۶ ب.ظ
آخرین ارسال: wskf
  دفترچه ی کنکور کارشناسی ارشد ۹۷ Doctorwho ۱ ۱,۸۱۵ ۲۴ مهر ۱۳۹۸ ۰۵:۰۸ ب.ظ
آخرین ارسال: mohamadreza025
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۲ ۱,۶۲۹ ۰۷ مهر ۱۳۹۸ ۰۶:۴۵ ب.ظ
آخرین ارسال: hamzadebaroon
  راهنمایی انتخاب واحد ترم اول، ارشد نرم، مباحث بیگ دیتا و دیتابیس arian_61 ۱ ۶۷۶ ۲۵ شهریور ۱۳۹۸ ۱۰:۴۱ ب.ظ
آخرین ارسال: arian_61
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۹۰۱ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous
  سطح و عمق و ارتفاع درخت remove ۵ ۵,۹۲۴ ۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ
آخرین ارسال: mstfvi
  راهنمایی در مورد دروس ترم اول هوش sina_bhh ۴۷ ۲۳,۹۰۴ ۲۰ آذر ۱۳۹۷ ۰۵:۳۷ ب.ظ
آخرین ارسال: Arezouuu

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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