پرش به محتویات

تمرین ۶

ددلاین تحویل: ۱۷ تیر ۲۳:۵۹

ثبت اولویت ویدیوی حلاگر می‌خواهید برای این تمرین ویدیوی حل ضبط کنید، اولویت سوال‌ها را ثبت کنید.
ثبت اولویت
نمایش:

میو

سوال ۱ — معنی کاهش

صورت سوال

فرض کنید یک کاهش چندجمله‌ای (polynomial reduction) از مسئله‌ی \(1\) به مسئله‌ی \(2\) داریم. درستی یا نادرستی هرکدام از گزاره‌های زیر را در یک یا دو جمله توضیح دهید.

  • اگر مسئله‌ی \(1\) NP-complete باشد، آنگاه حتما مسئله‌ی \(2\) نیز NP-complete است.
  • اگر مسئله‌ی \(1\) NP-complete باشد، آنگاه حتما مسئله‌ی \(2\) NP-hard است.
  • اگر مسئله‌ی \(1\) NP-complete باشد، آنگاه ممکن است مسئله‌ی \(2\) نیز NP-complete باشد.
  • اگر مسئله‌ی \(2\) NP-hard باشد، آنگاه حتما مسئله‌ی \(1\) نیز NP-hard است.

سوال ۲ — دو راهی

صورت سوال

ثابت کنید پیدا کردن دو جواب متمایز برای صادق شدن یک \(\text{3-CNF}\) یک مسئله NP-complete است.

می‌توانید در گام اول ثابت کنید این مسئله یک راه حل NP دارد، سپس ثابت کنید \(\text{3-SAT}\) به آن کاهش می‌یابد.

سوال ۳ — جمع زیرمجموعه

صورت سوال

مسئله‌ی Subset-Sum می‌پرسد که آیا چندمجموعه از اعداد صحیح مثبت، تعدادی زیرمجموعه دارد که مجموع آن دقیقاً برابر مقدار \(T\) باشد.

  • (الف) نشان دهید که چگونه متغیرها و clauseهای یک نمونه‌ی 3-SAT را می‌توان به صورت ارقام انتخاب‌شده‌ی خاصی از اعداد در مبنای \(B\) انکود کرد، به‌طوری‌که انتخاب یک عدد \(\iff\) نسبت‌دادن مقدار True به گزاره‌ی مربوطه باشد.
  • (ب) به‌طور خلاصه استدلال کنید که وجود یک زیرمجموعه با مجموع \(T\) \(\iff\) فرمول اولیه satisfiable است.
  • (پ) دقیقاً بیان کنید که این کاهش چه چیزی را درباره‌ی وضعیت پیچیدگی مسأله‌ی Subset-Sum می‌گوید.

سوال ۴ — پوشش راسی

صورت سوال

در مسئله‌ی vertex cover به ما یک گراف \(G = \langle V,E \rangle\) داده می‌شود و ما به دنبال کوچک‌ترین مجموعه از رئوس مثل \(S\) هستیم به طوری که به ازای هر یال مثل \((u,v) \in E\) حداقل یکی از رئوس \(u\) یا \(v\) عضو \(S\) باشند. با کاهش مسئله‌ی 3-SAT به مسئله‌ی vertex cover ثابت کنید که این مسئله NP-complete است.

پاسخ - پوریازارعی

سوال ۵ — پوشش مستطیلی

صورت سوال

مسئله‌ی Rectangle Tiling را در نظر بگیرید که در آن باید تشخیص داد آیا یک ناحیه \(R\) را می‌توان با استفاده از کاشی‌هایی از یک مجموعه \(T\) پوشاند، به طوری که هر کاشی فقط یک‌بار استفاده شود. در این مسئله، هم \(R\) و هم کاشی‌های موجود در \(T\) همگی مستطیل هستند. نشان دهید که Rectangle Tiling زمانی که ارتفاع و عرض مستطیل‌ها به صورت دودویی (binary) داده شده باشند، یک مسئله‌ی NP-complete است.

راهنمایی: می‌توان از NP-complete بودن مسائل partition یا subset-sum استفاده کرد.

پاسخ - کسری منتظری

سوال ۶ — پوشش مجموعه‌ای

صورت سوال

مجموعه‌های \(\{S_1, S_2, \dots, S_n\}\) داده شده‌اند. می‌خواهیم زیرمجموعه‌ای با کمترین تعداد عضو از اجتماع \(S_i\)ها را بیابیم که با هر یک از \(S_i\)ها اشتراک ناتهی داشته باشد. ثابت کنید این مسئله NP-complete است.

پاسخ - محمدامین حیدری

سوال ۷ — پوشش یالی

صورت سوال

در مسئله‌ی edge cover به ما یک گراف \(G = \langle V,E \rangle\) داده می‌شود و ما به دنبال کوچک‌ترین مجموعه از یال‌ها مثل \(S\) هستیم به طوری که به ازای هر راس مثل \(v \in V\) حداقل یکی از یال‌های مجاور آن عضو \(S\) باشند. ثابت کنید \(\text{edge cover} \in P\).

سوال ۸ — مکمل بازی

صورت سوال

ثابت کنید اگر \(\text{coNP} \neq \text{NP}\) در آن صورت \(P \neq NP\).

سوال ۹ — کاهش بی‌ملاحظه

صورت سوال

یک عبارت بولی به شکل DNF است اگر از ترکیب فصلی تعدادی بند عطفی (AND clause) تشکیل شده باشد. به طور مثال، یک عبارت DNF در زیر آمده است.

\[ (\bar{a} \land b \land \bar{c}) \lor (b \land c) \lor (a \land \bar{b} \land \bar{c}) \]

در مسئله‌ی DNF-SAT سؤال تعیین صدق‌پذیری یک عبارت DNF است، بدین معنی که آیا می‌توان طوری مقادیر True و False را به متغیرها نسبت داد که نتیجه‌ی نهایی عبارت True باشد.

  • (الف) نشان دهید مسئله‌ی DNF-SAT در زمان چندجمله‌ای قابل حل است.
  • (ب) با استفاده از قانون توزیع‌پذیری نشان دهید هر عبارت به فرم CNF را که هر بند آن از حداکثر سه لیترال تشکیل شده می‌توان به شکل DNF نوشت. به عنوان مثال:
\[ (a \lor b \lor \bar{c}) \land (\bar{a} \lor \bar{b}) = (a \land \bar{b}) \lor (b \land \bar{a}) \lor (\bar{c} \land \bar{a}) \lor (\bar{c} \land \bar{b}) \]
  • (ج) برای حل مسئله‌ی 3-SAT ابتدا با توجه به قسمت (ب) عبارت CNF داده‌شده را به یک عبارت DNF تبدیل می‌کنیم و سپس از الگوریتم قسمت (الف) برای حل آن استفاده می‌کنیم. بنابراین می‌توانیم ادعا کنیم که مسئله‌ی 3-SAT را که یک مسئله‌ی NP-complete است در زمان چندجمله‌ای حل کرده‌ایم و در نتیجه \(P = NP\)! به نظر شما کجای این استدلال اشکال دارد.
پاسخ - غزاله کریمی
فایل‌های همراه

سوال ۱۰ — ضرر شرکت پست

صورت سوال

یک شرکت پستی باید \(n\) مرسوله با وزن‌های \(a_1, a_2, \dots, a_n\) کیلوگرم را بین دو شهر جابه‌جا کند و برای این‌کار ماشین‌هایی با ظرفیت \(B\) کیلوگرم بار در اختیار دارد. نشان دهید مسئله‌ی پیدا کردن کمترین تعداد ماشین لازم برای این‌کار NP-complete است.

پاسخ - امیرحسین اسفندیاری

سوال ۱۱ — گراف رنگی رنگی

صورت سوال

می‌خواهیم راس‌های یک گراف را با رنگ‌های قرمز، آبی و زرد به گونه‌ای رنگ کنیم که رئوس مجاور آن ناهمرنگ باشند. ثابت کنید اگر مسئله‌ی 3-CNF را بتوانیم در زمان چندجمله‌ای حل کنیم، این مسئله را نیز می‌توان در زمان چندجمله‌ای حل کرد.

پاسخ - حسنا شاه حیدری

سوال ۱۲ — حداکثر تا حداقل

صورت سوال

فرض کنید \(G\) یک گراف بدون‌جهت باشد. مسائل زیر را در نظر بگیرید:

  • مسئله‌ی SPATH: آیا گراف \(G\) شامل یک مسیر ساده از رأس \(a\) تا رأس \(b\) با طول حداکثر \(k\) است؟

  • مسئله‌ی LPATH: آیا گراف \(G\) شامل یک مسیر ساده از رأس \(a\) تا رأس \(b\) با طول حداقل \(k\) است؟

  • (الف) نشان دهید یک الگوریتم با زمان اجرای چندجمله‌ای وجود دارد که SPATH را حل کند.

  • (ب) نشان دهید که مسئله‌ی LPATH یک مسئله‌ی NP-complete است.

سوال ۱۳ — دو تا سه

صورت سوال

مسئله‌ی \(CNF_k\) را به این صورت در نظر بگیرید: آیا یک فرمول CNF که در آن هر متغیر حداکثر در \(k\) مکان ظاهر شده است، ارضاپذیر (satisfiable) است؟ با توجه به این تعریف، به سوالات زیر پاسخ دهید:

  • (الف) نشان دهید مسئله‌ی \(CNF_2\) در مزان چندجمله‌ای قابل حل است.
  • (ب) نشان دهید که مسئله‌ی \(CNF_3\) یک مسئله‌ی NP-complete است.

سوال ۱۴ — برش بیشینه

صورت سوال

یک برش (cut) در یک گراف بدون‌جهت، یک بخش‌بندی از رئوس گراف به دو مجموعه‌ی مجزای \(S\) و \(T\) است. اندازه‌ی یک برش برابر تعداد یال‌هایی از گراف است که یک سر آن‌ها در \(S\) و دیگری در \(T\) قرار دارد.

مسئله‌ی MAX-CUT به این صورت تعریف می‌شود: آیا برای گراف \(G\) و عدد \(k\)، برشی با اندازه‌ی \(k\) یا بیشتر در گراف وجود دارد؟

با دانستن این تعاریف، نشان دهید مسئله‌ی MAX-CUT یک مسئله‌ی NP-complete است.

سوال ۱۵ — خوشه‌های بددست

صورت سوال

در نظریه‌ی گراف، یک کلیک (clique) یا زیرگراف کامل، مجموعه‌ای از رئوس است که هر دو رأس متمایز آن با یک یال مستقیماً به هم متصل شده باشند.

  • (الف) ثابت کنید مسئله‌ی CLIQUE (تشخیص وجود کلیکی با اندازه‌ی مشخص در یک گراف) یک مسئله‌ی NP-complete است.
  • (ب) مسئله‌ی HALF-CLIQUE به این صورت تعریف می‌شود: آیا گراف بدون‌جهت \(G\) با \(m\) رأس، دارای یک زیرگراف کامل (کلیک) با حداقل \(\frac{m}{2}\) رأس است؟ نشان دهید که مسئله‌ی HALF-CLIQUE یک مسئله‌ی NP-complete است.

سوال ۱۶ — تجزیه در خوشبختی

صورت سوال

نشان دهید اگر \(P=NP\) آنگاه می‌توانیم اعداد صحیح را در زمان چندجمله‌ای تجزیه کنیم.

سوال ۱۷ — دوگانگی

صورت سوال

برنامه‌ی خطی زیر را در نظر بگیرید:

\[ \max 4x_1 + x_2 \]

به شرط‌های

\[ \begin{aligned} 2x_1 + x_2 &\le 8, \\ x_1 + 2x_2 &\le 8, \\ x_1, x_2 &\ge 0. \end{aligned} \]
  • (الف) دوگان این برنامه را بنویسید.
  • (ب) یک جواب شدنی برای برنامه‌ی اولیه با مقدار \(16\) پیدا کنید.
  • (ج) یک جواب شدنی برای دوگان با مقدار \(16\) پیدا کنید و نتیجه بگیرید جواب قسمت قبل بهینه است.

سوال ۱۸ — کارخانه حریص

صورت سوال

یک کارگاه دو نوع محصول \(A\) و \(B\) تولید می‌کند. تولید هر واحد \(A\)، دو واحد ماده‌ی اولیه و یک ساعت زمان لازم دارد و سود آن \(5\) واحد است. تولید هر واحد \(B\)، یک واحد ماده‌ی اولیه و سه ساعت زمان لازم دارد و سود آن \(6\) واحد است. کارگاه در کل \(100\) واحد ماده‌ی اولیه و \(90\) ساعت زمان دارد.

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

سوال ۱۹ — کوتاه‌ترین مسیر

صورت سوال

گراف جهت‌دار زیر داده شده است:

\[ s \to a: 2, \qquad s \to b: 5, \qquad a \to b: 1, \qquad a \to t: 2, \qquad b \to t: 2. \]

با استفاده از متغیرهای \(d_v\)، برنامه‌ی خطی زیر را برای پیدا کردن فاصله‌ی کوتاه‌ترین مسیر از \(s\) به \(t\) کامل کنید:

\[ \max d_t - d_s \]

به شرط اینکه برای هر یال \((u,v)\) داشته باشیم:

\[ d_v \le d_u + w(u,v). \]

سپس با قرار دادن \(d_s = 0\)، مقدار بهینه‌ی \(d_t\) را پیدا کنید و بگویید با کدام مسیر متناظر است.

پاسخ - نرگس کاری
فایل‌های همراه

سوال ۲۰ — شار بیشینه

صورت سوال

شبکه‌ی زیر را در نظر بگیرید:

\[ s \to a: 3, \qquad s \to b: 2, \qquad a \to b: 1, \qquad a \to t: 2, \qquad b \to t: 3. \]

ظرفیت هر یال کنار آن نوشته شده است.

  • (الف) یک برنامه‌ی خطی برای شار بیشینه از \(s\) به \(t\) بنویسید.
  • (ب) یک شار شدنی با مقدار \(5\) ارائه دهید.
  • (ج) با استفاده از یک cut ساده نشان دهید مقدار شار بیشینه بیشتر از \(5\) نمی‌شود.
پاسخ - سید محمد مهدی حسینی

سوال ۲۱ — دوگان شار بیشینه

صورت سوال

فرض کنید \(P\) مجموعه‌ی همه‌ی مسیرهای از \(s\) به \(t\) در یک شبکه‌ی جهت‌دار باشد. برای هر مسیر \(p\)، متغیر \(x_p\) نشان می‌دهد چه مقدار شار از مسیر \(p\) عبور می‌کند. برنامه‌ی خطی زیر را در نظر بگیرید:

\[ \max \sum_{p \in P} x_p \]

به شرط‌های

\[ \begin{aligned} \sum_{p: e \in p} x_p &\le c_e \quad \forall e \in E, \\ x_p &\ge 0. \end{aligned} \]
  • (الف) دوگان این برنامه‌ی خطی را بنویسید.
  • (ب) نشان دهید هر cut از \(s\) به \(t\)، یک جواب شدنی برای دوگان می‌دهد.
  • (ج) نشان دهید از هر جواب شدنی برای دوگان می‌توان یک cut با ظرفیت حداکثر برابر مقدار آن جواب ساخت.

سوال ۲۲ — هزینه تخصیص

صورت سوال

سه کارگر و سه کار داریم. هزینه‌ی انجام کار \(j\) توسط کارگر \(i\) در ماتریس زیر آمده است:

\[ C = \begin{bmatrix} 4 & 1 & 3 \\ 2 & 0 & 5 \\ 3 & 2 & 2 \end{bmatrix}. \]

یک برنامه‌ی خطی برای کمینه کردن هزینه‌ی تخصیص بنویسید و جواب بهینه را پیدا کنید.

پاسخ - سجاد عاقلی
فایل‌های همراه

سوال ۲۳ — نقطه چبیشف

صورت سوال

چندضلعی محدب زیر در صفحه داده شده است:

\[ 0 \le x \le 4, \qquad 0 \le y \le 2, \qquad x+y \le 5. \]

برنامه‌ی خطی‌ای بنویسید که بزرگ‌ترین دایره‌ی کاملاً داخل این چندضلعی را پیدا کند. سپس شعاع بهینه را به دست آورید.

سوال ۲۴ — فرم استاندارد

صورت سوال

برنامه‌ی خطی زیر را به فرم استاندارد

\[ \max c^T x \qquad \text{s.t.} \quad Ax \le b, \quad x \ge 0 \]

تبدیل کنید:

\[ \min 3x_1 - 2x_2 + 5x_3 \]

به شرط‌های

\[ \begin{aligned} x_1 + 2x_2 - x_3 &\ge 7, \\ -2x_1 + x_2 &= 3, \\ x_1 \ge 0, \qquad x_2 &\text{ is unrestricted}, \qquad x_3 \le 0. \end{aligned} \]
پاسخ - علی نعمت دوست

سوال ۲۵ — فرم اسلک

صورت سوال

برنامه‌ی خطی زیر را به فرم اسلک (slack form) تبدیل کنید و جواب پایه‌ای اولیه را بنویسید:

\[ \max 4x + 3y \]

به شرط‌های

\[ \begin{aligned} x + 2y &\le 8, \\ 3x + y &\le 9, \\ x, y &\ge 0. \end{aligned} \]
پاسخ - مهدی نعمتی

سوال ۲۶ — بی‌کرانی

صورت سوال

نشان دهید برنامه‌ی خطی زیر بی‌کران است:

\[ \max x_1 - x_2 \]

به شرط‌های

\[ \begin{aligned} -2x_1 + x_2 &\le -1, \\ -x_1 - 2x_2 &\le -2, \\ x_1, x_2 &\ge 0. \end{aligned} \]

سوال ۲۷ — نشدنی

صورت سوال

نشان دهید برنامه‌ی خطی زیر نشدنی (infeasible) است:

\[ \max x_1 + x_2 \]

به شرط‌های

\[ \begin{aligned} x_1 + x_2 &\le 2, \\ -2x_1 - 2x_2 &\le -10, \\ x_1, x_2 &\ge 0. \end{aligned} \]

سوال ۲۸ — دوگان بازی

صورت سوال

برای یک گراف دوبخشی \(G = (L \cup R, E)\)، برنامه‌ی خطی کمینه‌سازی پوشش رأسی را بنویسید. سپس دوگان آن را حساب کنید و توضیح دهید چرا دوگان، همان برنامه‌ی خطی تطابق است.

پاسخ - علی مقدسی
فایل‌های همراه

سوال ۲۹ — فلش‌بک

صورت سوال

تعدادی بازه‌ی زمانی به صورت \((s_i, f_i)\) داده شده‌اند.

مسئله‌ی اول: می‌خواهیم بیشترین تعداد بازه‌ی سازگار را انتخاب کنیم؛ یعنی هیچ دو بازه‌ی انتخاب‌شده هم‌پوشانی نداشته باشند.

مسئله‌ی دوم: می‌خواهیم کمترین تعداد نقطه را انتخاب کنیم، به طوری که هر بازه شامل حداقل یک نقطه‌ی انتخاب‌شده باشد.

نشان دهید جواب این دو مسئله برابر است.

سوال ۳۰ — جام جهانی

صورت سوال

برنامه‌ی زمانی بازی‌های جام جهانی مشخص شده اما هنوز محل برگزاری اون مشخص نیست. در کل \(n\) تا بازی داریم که هر بازی در یک بازه‌ی زمانی مشخص برگزار میشه. (برای روی گل سوال طول بازه‌ها لزوما برابر نیستن). منطقا دو تا بازی که تداخل زمانی دارند نمی‌تونن توی یه استادیوم برگزار بشن. اما اگه یکیشون ۹ شب تموم بشه اون یکی ۹ شب تازه شروع بشه کاملا اوکیه که تو یه استادیوم برگزار بشن. شما اینفانتینو هستید و باید حساب کنید که کمترین تعداد استادیومی که نیاز دارید تا همه‌ی مسابقه‌ها رو برگزار کنید چند تاست. الگوریتمی از \(\mathcal{O}(n\ log\ n)\) ارائه دهید که این تعداد را محاسبه کند.

سوال ۳۱ — اثاث‌کشی پیچیده

صورت سوال

فرض کنید \(n\) جعبه داریم که می‌خواهیم در اثاث‌کشی آن‌ها را جا به جا کنیم. جعبه‌ها دو بعدی هستند.

جعبه‌ی \(i\) ام ابعاد \(a_i \times b_i\) دارد. شرکت باربری به نرخ تعداد وسیله هزینه می‌گیره. برای اینکه هزینه‌ی باربری رو کمتر کنیم می‌خوایم یه سری از این جعبه‌ها رو بذاریم توی هم. برای جلوگیری از آسیب به جعبه‌ها در حین جا‌به‌جایی، جعبه‌ها را فقط موازی محور مختصات درون هم قرار داده و درون هر جعبه حداکثر یک جعبه‌ی دیگر مستقیما قرار داده می‌شود. با این تفاسیر شرط قرار دادن جعبه‌ی \(i\) درون جعبه‌ی \(j\) ام می‌شود:

\[ (a_i < a_j \land b_i < b_j) \lor (a_i < b_j \land b_i < a_j) \]

الگوریتمی از \(O(n \log n)\) ارائه دهید که کمترین تعداد شئ که باید به شرکت باربری تحویل دهیم را محاسبه کند.

راهنمایی‌ها

سوال ۱) قاب‌های تو در تو از تمرین ۱ و سوال ۲۲) مستطیل‌ها از تمرین ۲ را بررسی کنید.

پاسخ - روژین تقی‌زادگان

سوال ۳۲ — تطابق خطی

صورت سوال

گراف دوبخشی زیر را در نظر بگیرید:

\[ L = \{a, b\}, \qquad R = \{1, 2, 3\}, \]
\[ E = \{(a, 1), (a, 2), (b, 2), (b, 3)\}. \]

یک برنامه‌ی خطی برای پیدا کردن بزرگ‌ترین تطابق در این گراف بنویسید و مقدار بهینه‌ی آن را پیدا کنید.

پاسخ - فاطیما تیمارچی
فایل‌های همراه

سوال ۳۳ — رفع ابهام

صورت سوال

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

سوال ۳۴ — نرم بازی

صورت سوال

مسائل زیر را به صورت برنامه‌ریزی خطی (LP) فرمول‌بندی کنید. رابطه‌ی بین جواب بهینه‌ی هر مسئله و جواب LP معادل آن را توضیح دهید.

  • (آ) (تقریب با نرم \(\ell_\infty\))
\[ \text{minimize} \ \|Ax - b\|_\infty \]
  • (ب) (تقریب با نرم \(\ell_1\))
\[ \text{minimize} \ \|Ax - b\|_1 \]
  • (ج)
\[ \begin{cases} \text{minimize} & \|Ax - b\|_1 \\ \text{subject to} & \|x\|_\infty \le 1 \end{cases} \]
  • (د)
\[ \begin{cases} \text{minimize} & \|x\|_1 \\ \text{subject to} & \|Ax - b\|_\infty \le 1 \end{cases} \]
  • (ه)
\[ \text{minimize} \ \|Ax - b\|_1 + \|x\|_\infty \]

در تمام مسائل، \(A \in \mathbb{R}^{m \times n}\) و \(b \in \mathbb{R}^m\) داده شده‌اند.

سوال ۳۵ — تقسیم بار

صورت سوال

تعدادی بار با جرم‌های مختلف \(M_1, \dots, M_k\) در مکان‌های مختلف \(P_1, \dots, P_k\) قرار دارند. همچنین تعدادی انبار در نقاط \(Q_1, \dots, Q_n\) قرار دارند، به‌طوری که ظرفیت انبار \(i\)ام برابر با \(C_i\) است (یعنی چنانچه ظرفیت انبار \(2\) تن باشد، بیش از \(2\) تن را نمی‌توان در آن ذخیره‌سازی نمود). هدف انتقال بهینه بارها به این انبارها است، به‌طوری‌که کل کار لازم برای انتقال بارها کمینه شود. میزان انرژی مصرف شده را برابر حاصل ضرب جرم بار انتقالی در طول مسیر طی شده آن در نظر می‌گیریم.

  • (آ) یک شرط لازم بدیهی برای امکان‌پذیر بودن انتقال بارها بیان کنید.
  • (ب) .فرض کنید بارها مایع و قابل تقسیم به اجزای کوچک‌تر باشند و می‌توان قطعات کوچک‌تر را به انبارهای متفاوتی ارسال نمود. مسئله را با یک برنامه‌ریزی خطی مدل کنید
پاسخ - نیکی رشیدیان

سوال ۳۶ — ساده‌سازی

صورت سوال

در یک برنامه‌ی خطی بولی (Boolean linear program)، متغیر \(x\) طوری محدود شده است که درایه‌های آن برابر با صفر یا یک باشند:

\[ \min c^T x \]

به شرط‌های

\[ \begin{aligned} Ax &\preceq b \\ x_i &\in \{0, 1\}, \quad i = 1, \dots, n. \end{aligned} \qquad \]

به طور کلی حل چنین مسائلی بسیار دشوار است، هرچند که مجموعه‌ی جواب‌های شدنی (feasible set) متناهی است (حداکثر دارای \(2^n\) نقطه است).

در یک روش کلی به نام relaxation، قید صفر یا یک بودن \(x_i\) با نامعادله‌های خطی \(0 \le x_i \le 1\) جایگزین می‌شود:

\[ \min c^T x \]

به شرط‌های

\[ \begin{aligned} Ax &\preceq b \\ 0 \le x_i &\le 1, \quad i = 1, \dots, n. \end{aligned} \qquad \]

ما به این مسئله LP relaxationِ مسئله‌ی Boolean LP می‌گوییم. حل مسئله‌ی LP relaxation بسیار ساده‌تر از Boolean LP اولیه است.

  • (الف) نشان دهید که مقدار بهینه‌ی LP relaxation یک کران پایین (lower bound) روی مقدار بهینه‌ی Boolean LP است. اگر LP relaxation نشدنی (infeasible) باشد، درباره‌ی Boolean LP چه می‌توان گفت؟
  • (ب) گاهی اوقات پیش می‌آید که LP relaxation دارای جوابی به صورت \(x_i \in \{0, 1\}\) است. در این حالت چه می‌توان گفت؟ آیا پاسخ حالت ساده شده برابر حالت اولیه است؟

سوال ۳۷ — تقریب مفید

صورت سوال

مسئله‌ی vertex cover یک مسئله‌ی NP-complete است. حال الگوریتم زیر را برای این مسئله در نظر بگیرید:

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

البته که این الگوریتم یک الگوریتم تقریبی است، اما اکنون در زمان چندجمله‌ای اجرا می‌شود.

ثابت کنید الگوریتم معرفی شده، یک الگوریتم 2-approximation است.

سوال ۳۸ — تقریب پوشش مجموعه‌ای

صورت سوال

مسئله‌ی پوشش مجموعه (Set Cover) به این صورت تعریف می‌شود: یک مجموعه‌ی مرجع (Universe) به نام \(U\) با اندازه‌ی \(|U| = n\) و کلکسیونی از زیرمجموعه‌های آن \(S_1, S_2, \dots, S_m\) داده شده است. هدف پیدا کردن کمترین تعداد از این زیرمجموعه‌هاست که اجتماع آن‌ها برابر با کل مجموعه‌ی مرجع \(U\) شود.

یک الگوریتم \(\ln n\)-approximation برای این مسئله ارائه دهید.

پاسخ - سروش داوران

سوال ۳۹ — جهانگرد تقریبی

صورت سوال

در این نسخه از مسئله‌ی TSP، گراف کامل است و فواصل بین شهرها در نامساوی مثلثی (triangle inequality) صدق می‌کنند.

یک الگوریتم 2-approximation برای حل این مسئله ارائه دهید و درستی ضریب تقریب آن را ثابت کنید.

پاسخ - ایلیا یزدانی

سوال ۴۰ — مجموعه غالب

صورت سوال

مسئله‌ی مجموعه‌ی احاطه‌گر (Dominating Set) به این صورت تعریف می‌شود: کمترین تعداد از رئوس را پیدا کنید به طوری که هر رأس در گراف، یا خودش انتخاب شده باشد و یا مجاور یک رأس انتخاب‌شده باشد.

یک الگوریتم تقریبی برای این مسئله ارائه دهید که ضریب تقریب (Approximation Ratio) آن در اوردر \(O(\log n)\) باشد.

سوال ۴۱ — پوشش راسی ابتکاری

صورت سوال

روش ابتکاری زیر را برای مسئله‌ی vertex cover در نظر بگیرید: یک درخت جستجوی اول عمق (DFS tree) از گراف بسازید و تمام برگ‌ها را از این درخت حذف کنید.

  • (الف) نشان دهید رئوس باقی‌مانده حتماً یک پوشش رأسی (vertex cover) برای گراف تشکیل می‌دهند.
  • (ب) ثابت کنید اندازه‌ی این پوشش پیدا شده، حداکثر دو برابر اندازه‌ی پوشش بهینه (optimal) است (یعنی این الگوریتم یک 2-approximation است).
پاسخ - ایلیا فرصتی

سوال ۴۲ — تطابق سرعتی

صورت سوال

مسئله‌ی تطابق (Matching) را در نظر بگیرید: - (الف) الگوریتمی با مرتبه زمانی \(O(|E|)\) طراحی کنید که یک تطابق بیشینه (maximal matching) در گراف \(G\) پیدا کند. - (ب) فرض کنید \(M\) یک تطابق ماکزیمم (maximum matching) در گراف \(G\) باشد. ثابت کنید برای هر تطابق بیشینه‌ای (maximal matching) مانند \(M'\)، رابطه‌ی \(|M'| \ge \frac{|M|}{2}\) برقرار است. به عبارت دیگر، ثابت کنید الگوریتم بخش الف، یک الگوریتم 2-approximation برای مسئله‌ی تطابق ماکزیمم است.

(دقت کنید که مسئله‌ی تطابق ماکزیمم NP-hard نیست و برای آن الگوریتم چندجمله‌ای دقیق وجود دارد، اما در اینجا هدف تحلیل یک روش تقریبی سریع است.)

پاسخ - زهرا قصابی

سوال ۴۳ — بی دوری

صورت سوال

یک گراف جهت‌دار \(G = (V, E)\) داده شده است. هدف ما پیدا کردن بزرگ‌ترین زیرمجموعه از یال‌ها مانند \(E' \subseteq E\) است، به طوری که زیرگراف \(G' = (V, E')\) (گرافی روی همان مجموعه‌ی رئوس \(G\) که توسط زیرمجموعه یال‌های \(E'\) القا شده است) هیچ دور جهت‌داری (directed cycle) نداشته باشد.

راهنمایی: رئوس را به صورت دلخواه مرتب کنید و یال‌های رو به جلو (forward) و رو به عقب (backward) را در نظر بگیرید (یال \((v_i, v_j)\) یک یال رو به جلو است اگر در ترتیب در نظر گرفته شده \(i < j\) باشد). زیرمجموعه‌ای از یال‌ها را پیدا کنید که شامل حداقل نیمی از یال‌ها باشد و هیچ دوری ایجاد نکند.

سوال ۴۴ — استاندار بی‌حوصله

صورت سوال

در یک کشور \(n\) شهر و بین هر دو شهر یک جاده وجود دارد (گراف کامل). می‌خواهیم این کشور را به \(k\) استان تقسیم کنیم و هر استان یک مرکز استان داشته باشد، به طوری که بیشترین فاصله‌ی شهرها تا مرکز استان‌شان، کمترین مقدار ممکن باشد (مسئله‌ی \(k\)-center). فرض کنید جواب بهینه \(d\) باشد؛ یعنی روشی برای تقسیم‌بندی وجود داشته باشد که هر شهر تا مرکز استان آن حداکثر فاصله‌ی \(d\) را داشته باشد و با هیچ روش دیگری این حداکثر فاصله کمتر نشود.

الگوریتمی ارائه دهید که \(k\) مرکز استان را پیدا کند به طوری که فاصله‌ی هر شهر تا مرکز استان آن حداکثر \(2d\) شود (یک الگوریتم 2-approximation). سپس درستی الگوریتم خود را اثبات کنید.