مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.
====== کوتاهترین مسیر در گراف ======
در این مسایل هدف پیدا کردن کوتاهترین مسیر بین رأسهای گراف است.
===== کوتاهترین مسیر با یک مبدأ =====
اگر رأس مبدأ مشخص باشد و کوتاهترین رأس از این مبدأ تا سایر رأسها مورد نظر باشد، مسأله کوتاهترین مسیر با یک مبدأ است.
==== الگوریتم دایکسترا ====
این الگوریتم از نوع [[الگوریتم:حریصانه|حریصانه]] است و برای گرافهای با وزن یالهای نامنفی کار می‌کند. ابتدا به رأس مبدأ فاصله ۰ می‌دهیم، یعنی در آرایه $dist$ مقدار رأس شروع را ۰ می‌گذاریم. سپس به ازای یالهای خروجی از این رأس، اگر مجموع فاصله این رأس تا مبدأ ($dist$) و یال طی شده از فاصله قبلی آن رأس کمتر شد، مقدار جدید را جایگزین می‌کنیم. این کار را ادامه می‌دهیم تا یالهای خروجی همه‌ی رأسها بررسی شده باشند.

دلیل درستی این الگوریتم، این است که کوتاهترین فاصله یک رأس تا مبدأ، کوتاهترین فاصله رأس قبل از آن به علاوه یال بین آنها است؛ که این همان انتخاب حریصانه است.

زمان این الگوریتم $O(|V|^2)$ است چون به ازای هر رأس، می‌تواند $|V|-1$ همسایه داشته باشد و به ازای گراف کامل این اتفاق می‌افتد. برای بهبود زمان این الگوریتم از صف اولویت استفاده می‌شود تا هر بار نزدیک‌ترین همسایه را در نظر بگیرد. با این کار زمان الگوریتم به $O(|E|+|V|\log |V|)$ کاهش می‌یابد.

[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AF%DB%8C%DA%A9%D8%B3%D8%AA%D8%B1%D8%A7|مطالب بیشتر در مورد الگوریتم دایکسترا]]
==== الگوریتم بلمن-فورد ====
این الگوریتم هم از نوع [[الگوریتم:حریصانه|حریصانه]] و شبیه به الگوریتم دایکسترا است. در این الگوریتم در هر مرحله، همه‌ی یالهای گراف را با همان شرط بهبود فاصله بررسی می‌کنیم. حداکثر طول یک مسیر $|V|-1$ است، پس حداکثر تعداد مراحل الگوریتم $|V|-1$ است. این تفاوت با الگوریتم دایسکترا باعث می‌شود که زمان الگوریتم $O(|V||E|)$ شود، اما مزیت آن این است که برای گرافهای جهت‌دار با یالهای با وزن منفی هم کار می‌کند. همچنین اگر یک بار دیگر هم الگوریتم را اجرا کنیم ($|V|$ بار)، اگر تغییری در فاصله ایجاد شد یعنی دور منفی در گراف وجود دارد.
[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%A8%D9%84%D9%85%D9%86%E2%80%93%D9%81%D9%88%D8%B1%D8%AF|مطالب بیشتر در مورد الگوریتم بلمن-فورد]]
===== کوتاهترین مسیر با مبدأ تمامی رأسها =====
اگر بخواهیم کوتاهترین مسیر از هر رأس گراف به هر رأس دیگر آن را به دست بیاوریم، مسأله کوتاهترین مسیر با مبدأ تمامی رأسها است.
==== الگوریتم فلوید-وارشال ====
این الگوریتم با روش [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] و از نوع بالا به پایین است. ابتدا مقدار اولیه کوتاهترین مسیرها را بینهایت (یا علامتی مثل $-1$) می‌گذاریم، به جز فاصله هر رأس تا خودش که آن را ۰ می‌گذاریم. در مرحله‌ی $i$-ام مسیرهای با رأسهای غیر پایانی در $v_j, j\leq i$ را به کمک رابطه زیر به دست می‌آوریم:
\[
dist[u,v] = \min(dist[u,v_i]+dist[v_i,v])
\]
هر مرحله از این الگوریتم زمان $O(|V|^2)$ می‌برد و تعداد مراحل حداکثر به اندازه‌ی تعداد رأسها است، پس زمان کل الگوریتم $O(|V|^3)$ است.
[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D9%81%D9%84%D9%88%DB%8C%D8%AF-%D9%88%D8%A7%D8%B1%D8%B4%D8%A7%D9%84|مطالب بیشتر در مورد الگوریتم فلوید-وارشال]]
===== مسایل نمونه =====
۱- حسن تعدادی چراگاه دارد که بین بعضی از آنها یالهای وزن‌دار است. هر چراگاه متعلق به یک گاو است و همه‌ی گاوها می‌خواهد در یک چراگاه جمع شوند. چراگاهی را پیدا کنید که گاوها در آن جمع شوند و جمع مسافت طی شده توسط آنها کمینه شود.

جواب: مسأله را برعکس حل کنید. فرض کنید چراگاه محل تجمع را دارید و می‌خواهید گاوها به جای اول خود برگردند. این مسأله‌ی کوتاه‌ترین مسیر است. برای حل سوال کوتاهترین مسیر را از هر رأس حساب کنید و به ازای مکان‌های گاوها با هم جمع کنید. رأس با کمترین مجموع جواب است.

۲-حسن می‌خواهد به یک مزرعه‌ی دیگر نقل مکان کند که مسافتی که هر روز طی می‌کند را کمینه کند. جایی که حسن به آن می‌رود $N\ (1\leq N \leq 10000)$ شهر دارد. $M$ جاده‌ی دوطرفه $(1\leq M \leq 50000)$ این شهرها را به هم وصل کرده‌اند. همه‌ی شهرها از یکدیگر با دنباله‌ای از جاده‌ها قابل دسترس هستند. حسن باید بهترین شهر را به عنوان خانه‌ی جدیدش انتخاب کند. $K$ فروشگاه در شهرها هستند $(1\leq K \leq 5)$ که حسن باید هر روز به آنها برود. به علاوه هر روز حسن می‌خواهد از خانه‌اش به این $K$ شهر برود و به خانه‌اش برگردد. حسن با هر ترتیب دلخواه می‌تواند فروشگاه‌ها را ببیند. وقتی یک شهر را به عنوان خانه (محل ساخت مزرعه جدید) انتخاب می‌کند، می‌خواهد فقط خانه‌اش از بین $N-K$ شهری باشد که فروشگاه ندارند، چون قیمت خانه در این شهرها کمتر است.

به حسن کمک کنید که کمترین فاصله‌ای که هر روز باید طی کند را کمینه کند؛ اگر بخواهد مزرعه‌ی جدیدش را در بهترین مکان بسازد و ترتیب دیدن مغازه‌ها را هم تا حد امکان هوشمندانه انتخاب کند.

جواب: کوتاهترین مسیر را از این $K$ شهر پیدا می‌کنیم. به ازای هر شهر از $N-K$ شهر به عنوان خانه جدید و دو شهر از $K$ شهر فاصله‌ی این دو شهر از خانه جدید و مسافت کمترین ترتیب $K$ شهر طوری که این دو شهر دو سر گشت قرار بگیرند؛ را حساب می‌کنیم. کمینه‌ی اینها جواب مسأله است. (به ازای هر ترتیب $K$ شهر باید کوتاهترین مسیر را حساب کنیم. می‌توانیم همه‌ی کوتاهترین مسیرها بین $K$ رأس با خودشان را به دست بیاوریم که کار ساده‌تر باشد.)

۳-علی و امیر می‌خواهند از قم به مشهد بروند و چون مسیر طولانی است، می‌خواهند نوبتی رانندگی کنند و در هر استراحتگاه میان‌راهی جای خود را عوض کنند. چون علی حس جهت‌یابی بهتری دارد، باید در شهرهای مبدأ و مقصد او رانندگی کند و امیر فقط در جاده رانندگی می‌کند. نقشه‌ی مسیر به شکل یک گراف وزن‌دار جهت‌دار داده شده است که وزن یالهای آن مثبت است و رأسهای آن استراحتگاه‌ها و یالهای آن جاده‌های بین آنها هستند. الگوریتمی ارائه دهید که در صورت امکان، کوتاهترین مسیر بین قم و مشهد را پیدا کند، طوری که علی و امیر بتوانند نوبتی رانندگی کنند.

جواب: کوتاهترین مسیرها بین همه‌ی زوج رأسها را حساب می‌کنیم و تعداد یالهای آنها را هم علاوه بر طول آنها نگه می‌داریم. کوتاهترین مسیر با طول فرد بین قم و مشهد را در صورت وجود برمی‌گردانیم و اگر کوتاهترین مسیرها همه طول زوج داشتند جواب خیر (غیرممکن) است.

۴-در یک شهر قوانین رانندگی عجیبی وجود دارد. این شهر تعدادی تقاطع دارد که بین آنها راه‌های دوطرفه بین تقاطع‌های متمایز است. چراغ‌های راهنمایی در هر تقاطع وجود دارند که رنگ آنها به صورت تناوبی مدتی آبی و مدتی قرمز است. در صورتی می‌شود در یک راه تردد کرد که وقتی به آخر آن می‌رسیم چراغ راهنمایی همرنگ وقتی باشد که در ابتدای آن هستیم (اگر چراغ همان لحظه عوض شود رنگ جدید آن ملاک است). در نقشه‌ی شهر زمان طی کردن همه‌ی جاده‌ها، زمان هر رنگ هر چراغ راهنمایی و رنگ اولیه هر چراغ راهنمایی و زمان باقیمانده تا تغییر رنگ آن داده شده‌اند. (همه‌ی این اعداد صحیح هستند). شما باید مسیری را پیدا کنید که کمترین زمان برای رسیدن از یک مبدأ داده شده به یک مقصد داده شده را بدهد. اگر بیش از یک مسیر با چنین خصوصیاتی وجود دارد، یکی از آنها را پیدا کنید. در ضمن ماشین‌ها می‌توانند در یک تقاطع توقف کنند.

جواب: الگوریتم کوتاهترین مسیر بین همه‌ی رأسها را تغییر بدهید تا توقف در تقاطع‌ها را هم حساب کند. درایه متناظر مبدأ و مقصد جواب مسأله است.

[[http://activities.tjhsst.edu/sct/lectures/1314/dijkstra_10_30_13.pdf|منبع سوالات]]
مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه
