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

مسیر ساده با کمترین تعداد یال - IT 86

ارسال:
  

delete4all پرسیده:

مسیر ساده با کمترین تعداد یال - IT 86

سلام
سوال ۴۸ طراحی الگوریتم کنکور فناوری اطلاعات سال ۸۶ هست

یه توضیح مختصر لطفا درباره اینکه چرا جواب میشه گزینه ۴ بهم بدین لطفا
چرا جواب گزینه ۲ نمیشه!؟ فرقشون چیه مگه


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

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

۱
ارسال:
  

Jooybari پاسخ داده:

RE: مسیر ساده با کمترین تعداد یال - IT 86

سلام وقت بخیر.
اگه قرار باشه کمترین تعداد یال رو داشته باشه و وزنشون اهمیت نداشته باشه، من BFS رو انتخاب میکنم. چون پیچیدگی محاسباتیش کمتره. دقیقاً هم برای همین کار طراحی شده. دایکسرا مجموع وزن رو در حالتی که تمام وزنها نامنفی باشن کمینه میکنه.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

msour44 پاسخ داده:

RE: مسیر ساده با کمترین تعداد یال - IT 86

سلام
kruskal برای یافتن درخت پوشای مینیمم استفاده می شود. dijkstra برای یافتن کوتاه ترین مسیر های هم مبدا. dfs , bfs جز الگوریتم های پیمایش گراف هستند.فرق بین دایجسترا با اول سطح اینه که اگر وزن تمام یال ها یکسان باشند دایجسترا به اول سطح تبدیل می شود البته در حاصل نهایی ولی با مرتبه ها و مکانیسم متفاوت. در کل زمانی که کوتاه ترین مسیر ها هم مبدا در گراف با وزن های یکسان یا در گراف بدون وزن را بخواهند از اول سطح استفاده می شود.
در bfs از یک راس شروع و هربار فرزندان ان با یک اولویت از قبل تعیین شده وارد صف می شود و هر باراز صف یک نود برداشته وتکرار مراحل.
در دایجسترا هم از یک صف اولویت استفاده می شود که ابتدا تمام نود ها در ان با یک ارزش زیاد(فاصله از مبدا) قرار دارندبه جز نود مبدا با ارزش صفر هر بار نود با ارزش مینیمم از صف خارج و روی فرزندان ان عمل relax( بررسی اینکه ایا فاصله فعلی بدست امده از فاصله قبلی کمتر است یا نه و در صورت نیاز اصلاح ارزش در صف) انجام می شود .حال اگر ورن تمام یال ها یکسان باشد عمل relax فقط یکبار برای هر نود باعث تغییر ارزش در صف می شود یعنی همان نردیک ترین فاصله جایگزین ارزش اولیه بسیار زیاد می شود.
البته در این تست که فاصله برحست کمترین تعداد یال را می خواهد که از اول سطح استفاده می شود.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Happiness.72 پاسخ داده:

RE: مسیر ساده با کمترین تعداد یال - IT 86

BFS کابردش اینه که کوتاه ترین مسیرهایی رو که از یک مبدا یکسان سرچشمه گرفتن رو بر حسب کوتاه ترین یال شناسایی کنه.
کروسکال به همراه پریم (که اینجا تو گزینه ها نیست) واسه پیدا کردن درخت پوشای کمینه هستن.
دایکسترا هم واسه SSSP هستش . منظور از SSSP کوتاه ترین مسیر وزن دار از یک راس هستش. single-source shortest-path

مساله ای که اینجا عرض میکنم این هستش : تو صورت سوال اشاره شده و به محض دیدن این تیپ تست های میشه جواب داد " مسیر ساده با کمترین تعداد یال " هستش. که DFS و BFS الگوریتم هایی برای پیمایش ساده گراف هستند.Smile
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

delete4all پاسخ داده:

RE: مسیر ساده با کمترین تعداد یال - IT 86

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۸۵۷ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  تعداد جواب mostafaheydar1370 ۲۱ ۱۹,۴۳۲ ۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ
آخرین ارسال: miinaa
  تعداد روش های نوشتن عدد n ss311 ۲ ۳,۳۷۷ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۲,۰۳۸ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  تعداد درخت فراگیر ss311 ۰ ۲,۳۲۳ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  تعداد توابع پوشا ss311 ۰ ۲,۰۹۰ ۰۶ بهمن ۱۳۹۸ ۰۴:۵۷ ب.ظ
آخرین ارسال: ss311
  تعداد اعداد ۵ رقمی هم ارز ss311 ۲ ۲,۶۵۶ ۰۶ بهمن ۱۳۹۸ ۰۴:۳۹ ب.ظ
آخرین ارسال: ss311
  انخاب مسیر آینده ؟ آینده دکترا چه خواهد شد ؟ shivap ۱۰ ۱۱,۳۹۹ ۰۲ آذر ۱۳۹۸ ۱۲:۳۶ ق.ظ
آخرین ارسال: WILL
  تعداد رشته های n بیتی hamedsos ۲ ۳,۱۵۲ ۱۸ آبان ۱۳۹۸ ۰۹:۰۶ ب.ظ
آخرین ارسال: Jooybari
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۲,۹۵۷ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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