۰
subtitle
ارسال: #۱
  
مسیر ساده با کمترین تعداد یال - IT 86
سلام
سوال ۴۸ طراحی الگوریتم کنکور فناوری اطلاعات سال ۸۶ هست
یه توضیح مختصر لطفا درباره اینکه چرا جواب میشه گزینه ۴ بهم بدین لطفا
چرا جواب گزینه ۲ نمیشه!؟ فرقشون چیه مگه
سوال ۴۸ طراحی الگوریتم کنکور فناوری اطلاعات سال ۸۶ هست
یه توضیح مختصر لطفا درباره اینکه چرا جواب میشه گزینه ۴ بهم بدین لطفا
چرا جواب گزینه ۲ نمیشه!؟ فرقشون چیه مگه
۱
ارسال: #۲
  
RE: مسیر ساده با کمترین تعداد یال - IT 86
سلام وقت بخیر.
اگه قرار باشه کمترین تعداد یال رو داشته باشه و وزنشون اهمیت نداشته باشه، من BFS رو انتخاب میکنم. چون پیچیدگی محاسباتیش کمتره. دقیقاً هم برای همین کار طراحی شده. دایکسرا مجموع وزن رو در حالتی که تمام وزنها نامنفی باشن کمینه میکنه.
اگه قرار باشه کمترین تعداد یال رو داشته باشه و وزنشون اهمیت نداشته باشه، من BFS رو انتخاب میکنم. چون پیچیدگی محاسباتیش کمتره. دقیقاً هم برای همین کار طراحی شده. دایکسرا مجموع وزن رو در حالتی که تمام وزنها نامنفی باشن کمینه میکنه.
۰
ارسال: #۳
  
RE: مسیر ساده با کمترین تعداد یال - IT 86
سلام
kruskal برای یافتن درخت پوشای مینیمم استفاده می شود. dijkstra برای یافتن کوتاه ترین مسیر های هم مبدا. dfs , bfs جز الگوریتم های پیمایش گراف هستند.فرق بین دایجسترا با اول سطح اینه که اگر وزن تمام یال ها یکسان باشند دایجسترا به اول سطح تبدیل می شود البته در حاصل نهایی ولی با مرتبه ها و مکانیسم متفاوت. در کل زمانی که کوتاه ترین مسیر ها هم مبدا در گراف با وزن های یکسان یا در گراف بدون وزن را بخواهند از اول سطح استفاده می شود.
در bfs از یک راس شروع و هربار فرزندان ان با یک اولویت از قبل تعیین شده وارد صف می شود و هر باراز صف یک نود برداشته وتکرار مراحل.
در دایجسترا هم از یک صف اولویت استفاده می شود که ابتدا تمام نود ها در ان با یک ارزش زیاد(فاصله از مبدا) قرار دارندبه جز نود مبدا با ارزش صفر هر بار نود با ارزش مینیمم از صف خارج و روی فرزندان ان عمل relax( بررسی اینکه ایا فاصله فعلی بدست امده از فاصله قبلی کمتر است یا نه و در صورت نیاز اصلاح ارزش در صف) انجام می شود .حال اگر ورن تمام یال ها یکسان باشد عمل relax فقط یکبار برای هر نود باعث تغییر ارزش در صف می شود یعنی همان نردیک ترین فاصله جایگزین ارزش اولیه بسیار زیاد می شود.
البته در این تست که فاصله برحست کمترین تعداد یال را می خواهد که از اول سطح استفاده می شود.
kruskal برای یافتن درخت پوشای مینیمم استفاده می شود. dijkstra برای یافتن کوتاه ترین مسیر های هم مبدا. dfs , bfs جز الگوریتم های پیمایش گراف هستند.فرق بین دایجسترا با اول سطح اینه که اگر وزن تمام یال ها یکسان باشند دایجسترا به اول سطح تبدیل می شود البته در حاصل نهایی ولی با مرتبه ها و مکانیسم متفاوت. در کل زمانی که کوتاه ترین مسیر ها هم مبدا در گراف با وزن های یکسان یا در گراف بدون وزن را بخواهند از اول سطح استفاده می شود.
در bfs از یک راس شروع و هربار فرزندان ان با یک اولویت از قبل تعیین شده وارد صف می شود و هر باراز صف یک نود برداشته وتکرار مراحل.
در دایجسترا هم از یک صف اولویت استفاده می شود که ابتدا تمام نود ها در ان با یک ارزش زیاد(فاصله از مبدا) قرار دارندبه جز نود مبدا با ارزش صفر هر بار نود با ارزش مینیمم از صف خارج و روی فرزندان ان عمل relax( بررسی اینکه ایا فاصله فعلی بدست امده از فاصله قبلی کمتر است یا نه و در صورت نیاز اصلاح ارزش در صف) انجام می شود .حال اگر ورن تمام یال ها یکسان باشد عمل relax فقط یکبار برای هر نود باعث تغییر ارزش در صف می شود یعنی همان نردیک ترین فاصله جایگزین ارزش اولیه بسیار زیاد می شود.
البته در این تست که فاصله برحست کمترین تعداد یال را می خواهد که از اول سطح استفاده می شود.
۰
ارسال: #۴
  
RE: مسیر ساده با کمترین تعداد یال - IT 86
BFS کابردش اینه که کوتاه ترین مسیرهایی رو که از یک مبدا یکسان سرچشمه گرفتن رو بر حسب کوتاه ترین یال شناسایی کنه.
کروسکال به همراه پریم (که اینجا تو گزینه ها نیست) واسه پیدا کردن درخت پوشای کمینه هستن.
دایکسترا هم واسه SSSP هستش . منظور از SSSP کوتاه ترین مسیر وزن دار از یک راس هستش. single-source shortest-path
مساله ای که اینجا عرض میکنم این هستش : تو صورت سوال اشاره شده و به محض دیدن این تیپ تست های میشه جواب داد " مسیر ساده با کمترین تعداد یال " هستش. که DFS و BFS الگوریتم هایی برای پیمایش ساده گراف هستند.
کروسکال به همراه پریم (که اینجا تو گزینه ها نیست) واسه پیدا کردن درخت پوشای کمینه هستن.
دایکسترا هم واسه SSSP هستش . منظور از SSSP کوتاه ترین مسیر وزن دار از یک راس هستش. single-source shortest-path
مساله ای که اینجا عرض میکنم این هستش : تو صورت سوال اشاره شده و به محض دیدن این تیپ تست های میشه جواب داد " مسیر ساده با کمترین تعداد یال " هستش. که DFS و BFS الگوریتم هایی برای پیمایش ساده گراف هستند.
۰
ارسال: #۵
  
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?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close