تجزیه زوج خوب جدا شده WSPD (فصل 4 هارپلد)

چند برش و k-برش (فصل 4 وزیرانی)

الگوریتم های تقریبی برای تعمیم هایی از مساله برش کمینه بررسی می شوند که np-hard هستند.

یک گراف بدون جهت همبند با یالهای وزندار داریم، یک برش با کمک افراز مجموعه رئوس به دو زیرمجموعه، مجموعه ی همه ی یالهایی است که هیچ دو سر آن در یک مجموعه نیستند (یعنی هر سر آن در یکی از مجموعه ها است). بدیهی است حذف برش از گراف آن را ناهمبند می کند.

ترمینالهای s و t را از مجموعه رئوس در نظر بگیرید: افرازی از رئوس را در نظر بگیرید که s در یک مجموعه و t در مجموعه دیگر باشد. برشی که با این افراز تعریف شود یک برش s-t نامیده می شود. مساله پیدا کردن برش با کمترین وزن و برش s-t با کمترین وزن به کمک الگوریتم شارش بیشینه به صورت کارا قابل حل هستند. این دو مساله را تعمیم می دهیم:

مساله چند برش: یک مجموعه ترمینال {S={s_1,...,s_k از رئوس داده شده، یک چند برش مجموعه ای از یالهاست که حذف آنها این ترمینالها را از هم ناهمبند می کند. مساله چندبرش مجموعه یال با کمترین وزن را می خواهد.

کمترین k-برش: مجموعه ای از یالها که حذف آنها k مولفه همبندی ایجاد می کند، k-برش نامیده می شود. مساله k-برش به دنبال k-برش با کمترین وزن است.

در این فصل الگوریتم های با ضریب زیر برای این دو مساله ارائه می دهیم:

2-2/k

--------------------------------------------------------------------------

مساله چند برش

یک برش ایزوله برای s_i را مجموعه ای از یالها تعریف می کنیم که حذف آنها s_i را از بقیه ترمینالها جدا می کند.

الگوریتم:

1- برای هر i از 1 تا k، برش ایزوله برای s_i با کمترین وزن را حساب کن (C_i).

2- از بین این برشها سنگین ترین آنها را حذف کن و اجتماع بقیه را برگردان (C).

--------

هر محاسبه در مرحله 1 با تشخیص ترمینالهای S-{s_i} به شکل یک گره و پیدا کردن برش مینیمم با محاسبه ی شارش بیشینه از s_i به گره اجتماع بقیه ترمینالها انجام می شود. بدیهی است حذف C از گراف هر زوج ترمینالی را ناهمبند می کند، پس یک چند برش است. (چون در الگوریتم همه ی راسها به جز یکی را از بقیه جدا کردیم و آن آخری هم چون بقیه از آن جدا هستند از بقیه جداست.)

قضیه: الگوریتم بالا ضریب تقریب زیر را دارد:

2-2/k

اثبات: فرض کنید A چندبرش بهینه باشد. می توانیم A را به صورت اجتماع k تا برش ببینیم: حذف A از گراف k مولفه همبندی ایجاد می کند که هر کدام یک ترمینال دارند (چون A چند برش با کمترین هزینه است، بیش از k مولفه ساخته نمی شود). قرار دهید A_i را به عنوان برشی که مولفه شامل s_i را از بقیه گراف جدا می کند. پس اجتماع A_i ها A می شود.

چون هر یال A مجاور دو مولفه است، هر یال در دو برش A_i ظاهر می شود. پس جمع وزن یالهای A_i ها دو برابر جمع وزن یالهای A است.

بدیهی است A_i یک برش ایزوله برای s_i است. چون C_i یک برش ایزوله با کمترین وزن برای s_i است، پس وزن C_i از وزن A_i کمتر مساوی است. (در الگوریتم این طوری حساب کردیم). توجه کنید که این الگورتیم تا همین جا با گرفتن اجتماع k برش C_i یک الگوریتم تقریبی با ضریب 2 است. در آخر چون C با حذف سنگین ترین برش C_i به دست آمده است، داریم:

w(C) <= (1-1/k) sum_1_k w(C_i) <= (1-1/k) sum_1_k (w(A_i)) = 2(1-1/k)w(A)

(نامساوی اول را می توان از اینجا به دست آورد که میانگین یک سری عدد از ماکسیمم آنها کمتر است). پایان اثبات.

الگوریتم قبل بر اساس شمای کران پایین داده نشده است. در فصل 19 آن را با LP حل می کنیم.

مثال: یک مثال tight برای این الگوریتم: گراف با 2k راس شامل یک دور k راسی و ترمینالهای متمایز متصل شده به هر راس آن. یالهای دور وزن 1 دارند و یالهای متصل به ترمینالها وزن 2-epsilon دارند.

برای هر ترمینال s_i، برش ایزوله با کمترین وزن برای s_i، یال متصل به s_i است. پس جواب الگوریتم (C) وزن (k-1)(2-epsilon) دارد. از طرف دیگر جواب بهینه حذف یالهای دور است که وزن k دارند.

--------------------------------------------------------

مساله k-برش مینیمم

یک الگوریتم معمولی برای k-برش این است: یک برش مینیمم در هر مولفه همبندی حساب کن و کم وزن ترین آنها را حذف کن و این کار را ادامه بده تا k مولفه همبندی بماند. این الگورتیم به ضریب 

2-2/k

می رسد، اما اثبات آن سخت است. به جای این الگوریتم ساده تری با همین زمان می دهیم: بازنمایی برشهای کمینه با درخت گومری-هو ( :)) )

برشهای کمینه هم مثل برشهای تقریبا بهینه؟ (sub-optimal) در گرافهای بدون جهت ویژگی های ساختاری جالبی دارند، بر خلاف برش در گرافهای جهت دار. وجود درختهای گومری-هو یکی از نتایج این مشخصات است.

فرض کنید T درختی باشد که روی مجموعه رئوس V ساخته شده؛ یالهای T لازم نیست از E باشند. فرض کنید e یک یال درخت T باشد. حذف آن از درخت دو مولفه همبندی ایجاد می کند. فرض کنید S و S' مجموعه رئوس این مولفه ها باشند. برش در گراف G به صورت افراز (S,S') را برش متناظر یال e تعریف می کنیم. تابع وزن w' را روی یالهای T تعریف کنید. درخت T یک درخت گومری-هو است اگر:

1- برای هر زوج راسهای u و v از V، وزن برش u-v کمینه برابر متناظر آن در T باشد.

2- برای هر یال e از T، وزن w'(e) وزن برش متناظر e در گراف اصلی باشد.

بدیهی است که یک برش u-v مینیمم در T همان کم وزن ترین یال در مسیر بین u و v است (فرض کنید e) و برش متناظر e در G باید u و v را جدا کند.

به صورت شهودی، پیدا کردن یک k-برش کم وزن نیازمند برداشتن برشهای کم وزن است که مولفه های زیادی ایجاد می کنند. توجه کنید که n-1 برش متناظر یالهای T شامل برشهای u-v مینیمم برای هر زوج راس از مجموعه رئوس هستند. (C(n,2)). این حقیقت و لم بعد با هم استفاده از درخت گومری-هو برای پیدا کردن یک k-برش کم وزن را اثبات می کنند.

لم: S را اجتماع برشهای گراف متناظر با L یال T در نظر بگیرید. آنگاه حذف S از گراف یک گراف با حداقل L+1 مولفه ایجاد می کند.

اثبات: حذف L یال مذکور از درخت دقیقا L+1 مولفه می سازد، آنها را V_1 و ... و V_(L+1) بنامید. بدیهی است حذف S از G زوجهای V_i و V_j را ناهمبند می کند. بنابراین ما باید حداقل L+1 مولفه همبندی به دست بیاوریم.

در نتیجه ی لم قبل، اجتماع k-1 برش برداشته شده از T یک k-برش در گراف می سازد. الگوریتم کامل به صورت زیر است:

الگوریتم k-برش:

1- یک درخت گومری-هو T برای گراف G بسازید.

2- اجتماع کم وزن ترین k-1 برش از n-1 برش متناظر یالهای T در گراف را به عنوان خروجی برگردانید. (C)

--------

طبق لم قبل حذف C از G حداقل k مولفه همبندی می سازد. اگر بیش از k مولفه ساخته شد، بعضی از یالهای حذف شده را دوباره برگردانید تا دقیقا k مولفه شود.

قضیه: الگوریتم قبل ضریب تقریب 

2-2/k

دارد.

اثبات: فرض کنید A جواب k-برش بهینه گراف باشد. همان طور که در قضیه 4.4 گفته شد، می توانیم A را به صورت اجتماع k برش ببینیم: V_1 و ...و V_k را k مولفه همبندی شکل گرفته با حذف A از G بگیرید و A_i را برشی که V_i را از بقیه جدا می کند. پس A=A_1 U ...UA_k و در نتیجه هر یال A در دو تا از این برشها می افتد.

sum_i_1_k( w(A_i) ) = 2*w(A)

بدون از دست رفتن کلیت مساله فرض کنید A_k سنگین وزن ترین این برشها باشد. ایده ی بقیه اثبات نشان دادن این است که k-1 برش متناظر یالهای T هستند که وزنشان کمتر از وزن برشهای A_1 ,..., A_(k-1) هستند. پس چون الگوریتم k-1 برش سبکتر تعریف شده توسط T را بر می دارد، قضیه درست است.

k-1 برش به صورت زیر مشخص می شوند. B را مجموعه یالهای T بگیرید که V_1 و ... و V_k را متصل می کنند. گراف با رئوس V و یالهای B را در نظر بگیرید و هر یک از مجموعه های V_i را به صورت یک ابرراس در نظر بگیرید. گراف حاصل باید همبند باشد (چون T همبند بوده است).. یالها را تا زمانی که یک درخت باقی بماند حذف کنید. B' زیر مجموعه B را مجموعه یالهای باقیمانده در نظر بگیرید. |B'|=k-1 . یالهای B' برشها (k-1 تا)ی مورد نظر ما را مشخص می کنند.

بعد ریشه درخت را V_k بگذارید (سنگین ترین برش در بین A_iها). این کار به پیدا کردن ارتباط بین یالهای B' و مجموعه های V_1,...,V_(k-1) کمک می کند: هر یال متناظر مجموعه ای است که از آن بیرون می آید. (در درخت ریشه دار).

فرض کنید یال (u,v) از B' متناظر مجموعه V_i باشد. وزن برش u-v مینیمم در گراف، w'(u,v) است. چون A_i یک برش u-v در گراف است:

w(A_i) >= w'(u,v)

پس وزن هر برش بین A_1 و ... و A_(k-1) حداقل به اندازه ی برش تعریف شده در گراف متناظر یال B' است. از این موضوع و این حقیقت که C اجتماع k-1 سبکترین برش تعریف شده توسط T است به دست می آید:

w(C) <= sum_B' (w'(e)) <= sum_i_1_k-1 w(A_i) <= (1-1/k) sum_i_1_k (w(A_i)) = 2(1-1/k)w(A)

مثال tight: برای الگوریتم چندبرش بالا با 2k راس برای این مساله هم مثال خوبی است. (البته نیازی به علامت گذاری راسها به عنوان ترمینال نداریم). در زیر مثالی برای k=4 با درخت گومری-هو متناظر آن می دهیم.

سبکترین k-1 برش در درخت گومری-هو وزن 2-epsilon دارند که متناظر برداشتن یالهای با وزن 2-epsilon از G است. پس k-برش برگردانده شده توسط الگوریتم وزن (k-1)(2-epsilon) دارند. از طرف دیگر جواب بهینه برداشتن یالهای با وزن 1 است که در مجموع k می شود.

روز اول توی آزمایشگاه

اینجا آزمایشگاهه و هیچ کس هم اینجا نیست به جز من و دوستم! :))

حس کردم این باید در تاریخ ثبت بشه!

روی همه چیزهای اینجا یه وجب خاک هست! :)

ادامه سوالات فصل 2 وزیرانی

9- یک الگوریتم حریصانه که ضریب تقریب H(n) برای پوشش چندگانه مجموعه ای بدهید. پوشش چندگانه مجموعه ای تعمیمی از پوشش مجموعه ای است که در آن نیازمندی های پوشش عدد صحیح هم برای هر عضو داده شده است و مجموعه ها می توانند چندین بار انتخاب شوند تا همه ی نیازمندی ها را پاسخگو باشند. فرض کنید هزینه ی برداشتن a کپی از مجموعه S_i برابر a.cost(S_i) باشد.

حل:

با تکنیک لایه ای ابتدا یک پوشش مجموعه ای برای اعضایی که تعداد لازم آنها بیشتر از یک است به دست می آوریم، بعد یکی از نیازمندی آنها کم می کنیم و راسهایی که صفر نمی شوند به مرحله بعد می روند و این کار را ادامه می دهیم تا مساله حل شود.

تکنیک لایه ای ضریب تقریب را تغییر نمی دهد.

10- با یک مثال tight مناسب نشان دهید که تحلیل الگوریتم 2.2 نمی تواند بهبود یابد، حتی در حالتی که اعضای پوشش مجموعه ای در نظر گرفته شود. یعنی هزینه ی مجموعه ها 1 باشد.

راهنمایی: الگوریتم حریصانه را روی یک نمونه پوشش راسی اجرا کنید.

حل:

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

(ضریب تقریب: H(n))

با فرض هر راس به عنوان مجموعه یالهای مجاور آن به پوشش مجموعه ای می رسیم. انتخاب حریصانه ی ما به صورت انتخاب راس با بیشترین تعداد یال جدید است. باید به نسبت جواب الگوریتم به جواب بهینه ی لگاریتمی بر حسب تعداد راسها برسیم.

مثال: همان مثال جزوه که گراف دو بخشی با r راس در قسمت بالا و r+r/2+..+1 راس در قسمت پایین بود.

11- الگوریتم زیر را برای مساله پوشش راسی وزن دار در نظر بگیرید. برای هر راس v، متغیر t(v) را با وزن آن مقدار دهی می کنیم و وقتی t(v) صفر شد راس را به پوشش اضافه می کنیم. c(e) مقداری است که به یال e نسبت داده شده است.

الگوریتم:

1- مقداردهی اولیه: C تهی، به ازای هر راس v از V قرار بده t(v) = w(v)، به ازای هر یال از E قرار بده c(e) = 0

2- تازمانی که C یک پوشش راسی نیست: یک یال پوشش داده نشده مثل (u,v) را بردار. m=min(t(u),t(v)) قرار بده.

t(u) = t(u)-m

t(v)=t(v)-m

c(u,v) = m

همه ی راسهایی که t(v) صفر دارند به C اضافه کن.

3- C را برگردان.

نشان دهید این الگوریتم ضریب تقریب 2 دارد.

راهنمایی: نشان دهید مجموع هزینه ی یالها برای جواب بهینه (OPT) یک کران پایین است و نشان دهید که وزن پوشش C حداکثر دوبرابر مقدار هزینه یالها است.

حل:

هر بار وزن حداقل یکی از دو سر یال صفر می شود (آن یال پوشش داده می شود) ولی از جمع وزن راسها دو برابر وزن یال کم می شود. وقتی همه یالها بررسی شوند یک پوشش راسی به دست می آید و الگوریتم متوقف می شود. پس هزینه ی الگوریتم بیشتر از هزینه بهینه است (این الگوریتم یک پوشش راسی می دهد).

min(t(u),t(v)) = cost(e) <= t(u) <= w(u) , cost(e) <= t(v) <= w(v) ==> sum( cost(e) ) <= OPT

می دانیم C یک پوشش راسی است یعنی حداقل یک سر هر یال در آن است. اگر دو سر یک یال در C باشد، یعنی یک سر آن به وسیله یک یال انتخاب شده و سر دیگر آن به وسیله یال دیگر انتخاب شده است. پس هرگاه راسی به C انتخاب می شود، وزن آن با وزن یک یال مساوی است. وزن فعلی راس یکبار قبلا به اندازه ی یال قبلی کم شده است، پس برابر جمع این دو یال است. هر یال دو سر دارد پس حداکثر دو بار وزن آن شمرده می شود. اگر یک سر یال در C باشد که وزن آن با وزن یال مساوی است. پس وزن پوشش C از 2 برابر وزن یالها کمتر مساوی است.

12- الگوریتم لایه ای برای پوشش راسی را در نظر بگیرید. تابع وزن دیگری که برای آن الگوریتم 2-تقریبی داریم تابع ثابت است: به سادگی از الگوریتم 2-تقریبی مساله پوشش راسی با کمترین تعداد راس استفاده می کنیم. آیا می شود با تکنیک لایه ای از این تابع به جای تابع وزن-درجه استفاده کرد؟

(تابع وزن-درجه: وزن هر راس ضریب ثابتی از درجه آن است.)

خیر، زیرا در این صورت راسی که وزن کمتری دارد انتخاب می شود و این یعنی انتخاب دلخواه رئوس!

مثال حالت بد: گراف ستاره با n برگ که همه برگها وزن n/2 داشته باشند و  راس مرکزی وزن n داشته باشد.

جواب الگوریتم: همه ی راسهای درجه 1 را بر می دارد.

جواب بهینه: فقط راس مرکزی را بردارد.

ضریب تقریب:

(n*n/2)/n=n/2

یعنی هیچ ضریب ثابتی برای تقریب آن نخواهد بود.

13- از تکنیک لایه ای استفاده کنید که الگوریتم تقریبی با ضریب f برای پوشش مجموعه ای بدهید که f تعداد تکرار پرتکرارترین عضو مجموعه مرجع است. یک مثال tight برای این الگوریتم بدهید.

برای هر عضو مجموعه مرجع مینیمم هزینه ی آن در هر مجموعه (هزینه مجموعه/تعداد اعضای مجموعه) را هزینه ی آن عضو قرار می دهیم. اعضای با هزینه مینیمم را انتخاب می کنیم. مجموعه های شامل این اعضا را حذف می کنیم و خود این اعضا را به جواب اضافه می کنیم و هزینه ی اعضای باقیمانده را حساب می کنیم.

اثبات ضریب تقریب: هر عضو حداکثر در f مجموعه می تواند انتخاب شود (اگر همه ی این مجموعه ها با هم انتخاب شوند) پس هزینه ی آن حداکثر f برابر می شود.

مثال حالت بد: 

{a,b,c} cost: 1

{a,b,c} cost: 1

alg=2*1=2, OPT=1, f=2

14- یک تورنمنت یک گراف جهتدار است که به ازای هر زوج راس u و v از آن دقیقا یکی از دو یال (u,v) و (v,u) در گراف هست. یک مجموعه راس فیدبک برای گراف زیرمجموعه ای از رئوس است که حذف آنها یک گراف بدون دور ایجاد می کند. یک الگوریتم با ضریب 3 برای پیدا کردن مجموعه رئوس فیدبک مینیمم در یک گراف جهتدار بدهید.

راهنمایی: نشان دهید کافی است همه ی دورهای به طول سه را از بین ببریم. از پوشش مجموعه ای ضریب f برای این کار استفاده کنید.

حل: یک دور با طول بیش از سه در نظر بگیرید. می خواهیم ثابت کنیم که اگر دورهای با طول 3 را نابود کرده باشیم، این دور حذف شده است. (برهان خلف). دو راس را که در دور متوالی نیستند در نظر بگیرید. حتما از یکی از آنها به دیگری یال هست. درون دور می دانیم یک مسیر از هر کدام از این دو راس به دیگری هست. (یعنی دو مسیر یکی از اولی به دومی یکی از دومی به اولی). پس با این یال یک دور تشکیل می شود که اندازه ی آن کوچکتر است. به صورت استقرایی برای این دور هم می توانیم همین استدلال را بکنیم و در نهایت به دور به طول سه می رسیم که هر سه راس در دور متوالی هستند و این با فرض نبود مثلث تناقض دارد.

اثبات ضریب تقریب: هر کدام از یالهای هر دور را که حذف کنیم جواب است، اما در بدترین حالت همه ی یالهای دور را حذف می کنیم که سه برابر حذف یک یال است و این بدترین حالت است (جواب بهینه یک یال باشد و ما سه یال حذف کنیم) پس ضریب تقریب الگوریتم 3 است.

15- مساله پوشش بیشینه: یک مجموعه مرجع U از n عضو داده شده که هر کدام وزن نامنفی دارند. همچنین مجموعه ای از زیرمجموعه های U به نامهای S_1,...,S_L و عدد صحیح k داده شده است. k تا از مجموعه ها را بردارید طوری که وزن اعضای برداشته شده ماکسیمم شود.

نشان دهید الگوریتم بدیهی که به صورت حریصانه بهترین مجموعه را در هر مرحله بر می دارد تا k مجموعه برداشته شود، به الگوریتمی با ضریب تقریب زیر می رسد:

1-(1-1/k)^k > 1-1/e

حل:

(هر عضو مجموعه مرجع یک وزن دارد، پس وزن هر مجموعه جمع وزن اعضای آن است اما وقتی اجتماع می گیریم دیگر وزن اعضای تکراری حساب نمی شود.)

انتخاب حریصانه: مجموعه ای که بیشترین جمع وزن اعضای جدید را دارد.

؟؟

16- با استفاده از پوشش مجموعه ای، الگوریتم های تقریبی برای نسخه های زیر از مساله کوتاهترین ابررشته به دست آورید.

الف) کوتاهترین رشته ای را پیدا کنید که برای هر رشته خودش و معکوسش زیررشته آن باشند.

راهنمایی: مجموعه مرجع پوشش مجموعه ای شامل 2n عضو است: خود رشته و معکوس آن.

همان طور که راهنمایی گفته است معکوس رشته را هم به مجموعه ی رشته ها اضافه می کنیم و مثل قبل حل می کنیم.

ب) کوتاهترین رشته ای را پیدا کنید که یا خود رشته یا معکوس آن را داشته باشد.

راهنمایی: به جای مجموعه ی ابررشته های هر رشته که قبلا به کار می بردیم، ابررشته های خود رشته یا معکوس آن را در نظر بگیرید. خود این ابررشته را به طور مناسب انتخاب کنید.

ابررشته های خود رشته که شامل معکوس آن نیستند یا ابررشته های شامل معکوس رشته که شامل خود رشته نیستند.

(؟)

دوگان LP

دقت کنید که ضریبهای a و b و c در هر دو LP مقدارهای مشخص هستند.

ادامه تمرینهای فصل 1 وزیرانی

5- یک تطابق ماکسیمال را می توان با یک الگوریتم حریصانه به دست آورد: یک یال را بردارید و دو سر آن را حذف کنید، این کار را ادامه بدهید تا هیچ یالی باقی نماند. آیا این کار باعث می شود الگوریتم 1.2 حریصانه شود؟

(الگوریتم 1.2: پوشش راسی با  بیشترین اعضا: یک تطابق ماکسیمال در گراف پیدا کنید و راسهای تطابق یافته را به عنوان خروجی اعلام کنید.)

بله، چون در آن از یک الگوریتم حریصانه استفاده کرده ایم.

6- یک کران پایین برای مساله پوشش راسی با هزینه دلخواه بدهید.

راهنمایی: اگر از دوگان LP استفاده نکنید ساده نیست.

پوشش راسی را با LP بخواهیم بیان کنیم متغیرهای آن را راسها می گیریم که 0 یعنی در پوشش راسی نیست و 1 یعنی هست. قیود ما یالها هستند که جمع دو متغیر راس هستند که باید از 1 کمتر باشند. تابع هدف ما هم مینیمم کردن جمع متغیرها است.

IP --> LP:

minimize sum(cost(i)*xi)

s.t. xi+xj <= 1 (i,j) in E

xi in {0,1} --> xi >= 0, xi <= 1

LP:

minimize sum(cost(i)*xi)

s.t. -xi-xj >= -1

-xi >= -1

xi >= 0

dual LP:

maximize sum_i_E(-yi)+sum_j_1_n(-yj)

s.t. yi <= cost(i)

yi >= 0

که این جمع هزینه یالها و راسها را مینیمم می کند که هزینه هیچ یال یا راسی از هزینه اولیه بیشتر نشود.

فکر کنم باید این در میومد که هزینه ی یالها را مینیمم کند که معادل تطابق ماکسیمال با کمترین هزینه بشود. :)

7- فرض کنید A={a1,...,an} مجموعه متناهی باشد که رابطه ای بازتابی، نامتقارن و ترایا روی آن تعریف شده است. این رابطه یک ترتیب جزئی روی A نام دارد. دو عضو ai و aj از A را قابل مقایسه می گویند اگر ai R aj باشد یا aj R ai باشد. دو عضو غیرقابل مقایسه به دو عضوی می گویند که قابل مقایسه نباشند. یک زیر مجموعه S از A را زنجیره می نامند اگر اعضای آن دو به دو قابل مقایسه باشند. اگر اعضای S دو به دو غیرقابل مقایسه باشند به آن ضدزنجیره می گویند. یک پوشش زنجیره (ضد زنجیره) مجموعه ای از زنجیره ها (ضد زنجیره ها) است که دو به دو مجزا هستند و A را پوشش می دهند. اندازه این پوشش تعداد زنجیره ها (ضد زنجیره ها)ی آن است. ثابت کنید نتیجه min-max زیر درست است: اندازه طولانی ترین زنجیره به اندازه کوچکترین پوشش ضدزنجیره است.

راهنمایی: اندازه طولانی ترین زنجیره را m فرض کنید. برای هر a عضو A، تابع f(a) را اندازه طولانی ترین زنجیره که در آن a کمترین عضو است قرار دهید. حالا افراز A را به مجموعه های A_i در نظر بگیرید که اعضای آنها زنجیره های به طول i از اعضای A هستند. i بین 1و m.

حل:

طول بزرگترین زنجیره از هر عضو A یکتا است پس A_i ها A را افراز می کنند. از هر عضو A_i دقیقا حداقل یکی در پوشش ضد زنجیره است، چون به هیچ کدام از این زنجیره ها نمی توان عضو دیگری اضافه کرد (چون هر کدام ماکسیمم هستند). پس طول کوتاهترین پوشش ضدزنجیره m می شود. (ضدزنجیره های با طول بیشتر هم می توانند باشند ولی ما کمترین را می خواهیم.)

8- ثابت کنید در هر ترتیب جزئی، اندازه ی بزرگترین ضدزنجیره مساوی کوتاهترین پوشش زنجیره ای است.

راهنمایی: از قضیه ... استفاده کنید. یک ترتیب جزئی روی یک مجموعه n عضوی داده شده است، گراف دوبخشی U و V و E را در نظر بگیرید که |U|=|V|=n و اگر و تنها اگر a_i <a_j باشد یال (u_i,v_j) عضو E است.

حل:

یک ضدزنجیره یک پوشش راسی از این گراف است، پس پوشش راسی کمینه بزرگترین ضدزنجیره است. اندازه ی آن با تطابق بیشینه مساوی است که کوتاهترین پوشش زنجیره ای است.

*بقیه سوالات فصل مربوط به ضمیمه بودند.

کوتاهترین ابررشته - اصلاحیه

S: مجموعه رشته های ورودی

M: مجموعه شامل همه ی ابررشته های بهینه هر دو رشته (از اعضای S)

Set(x): مجموعه اعضای S که زیررشته ی x هستند. (=x ابررشته ی آنهاست)

هزینه ی Set(x) طول رشته x است یعنی |x|.

OPTs: جواب بهینه ی پوشش مجموعه ای که در آن اعضای مجموعه مرجع رشته ها و مجموعه ها Set(x) ها هستند که x اجتماع M و S است.

OPT: طول کوتاهترین ابررشته شامل همه ی رشته ها (جواب بهینه مساله)

الگوریتم:

1- با استفاده از الگوریتم تقریبی پوشش مجموعه ای یک جواب پیدا کن. (به تعریف OPTs نگاه کنید.)

فرض کنید رشته هایی که این الگوریتم برگرداند a_1,...,a_k باشند.

2- این رشته ها را با هر ترتیبی به هم بچسبانید. (دلخواه)

3- رشته ی حاصل را به عنوان جواب برگردانید.

تحلیل:

(چون هزینه ای که مینیمم می کند، طول رشته ها است احتمالا جواب خوبی به دست می آید.)

لم: OPT <OPTs <2.OPTs

(جواب بهینه ی مساله ی پوشش مجموعه ای جواب تقریبی برای این مساله با ضریب 2 است.)

اثبات نامساوی اول ساده است: طول جواب بهینه کمتر از طول جوابی است که پوشش مجموعه ای بر می گرداند. (در واقع فقط باید ثابت کنیم جواب پوشش مجموعه ای یک جواب برای این مساله است.) می دانیم جوابی که پوشش مجموعه ای بر می گرداند حاصل اتصال رشته های a_i است که برای هر رشته ی S حداقل یک a_i هست که ابررشته ی آن باشد.

اثبات نامساوی دوم: کافی است ثابت کنیم جواب الگوریتم پوششی با هزینه ی کمتر از 2 برابر جواب بهینه است. اولین مکانی که هر رشته ی S در جواب الگوریتم ما ظاهر می شود علامت بزنید. این مکان ها متمایزند چون هیچ رشته ای زیر مجموعه ی رشته ی دیگر نیست. (اگر دو رشته مکان شروع یکسان داشته باشند رشته ای که زودتر تمام می شود زیررشته ی رشته ی دیگر می شود). با استدلال مشابه پایان این رشته ها هم متمایز است. آنها را به این ترتیب شماره گذاری می کنیم. این لیست را روی رشته های a_i افراز می کنیم (جزء مساله). (اشتراک a_i ها کمتر از یک رشته در S است در غیر این صورت بهینه نمی شدند.). هزینه ی جواب الگوریتم ما جمع طول ابررشته های a_i است. بدیهی است که a_i و a_i+2 با هم اشتراک ندارند. پس هر رشته حداکثر در دو تا از ابررشته ها (a_i و a_i+1) آمده است پس هزینه کمتر از دو برابر جمع طول a_i ها است که آن هم از جواب بهینه بیشتر است.

تمرین های فصل 3

1- سختی مساله درخت اشتاینر در مشخص کردن زیرمجموعه بهینه از راسهای اشتاینر است که باید در درخت باشند. نشان دهید که اگر این مجموعه داده شده باشد، مساله ی درخت اشتاینر به صورت بهینه در زمان چند جمله ای قابل محاسبه است.

راهنمایی: یک MST روی اجتماع این مجموعه و مجموعه رئوس "لازم" پیدا کنید.

گراف جدیدی می سازیم و فقط این راسها و یالهای بین آنها را نگه می داریم چون بقیه راسها نمی توانند در جواب وجود داشته باشند. درخت با کمترین هزینه که این راسها را داشته باشد همان MST گراف است. زمان حذف یالها و راسهای اضافی و به دست آوردن MST گراف جدید هم چند جمله ای است. چون تعریف MST و درخت اشتاینر در این حالت یکی می شود دیگر اثبات هم نمی خواهد.

2- گراف با یالهای وزندار نامنفی داده شده است. S مجموعه ی فرستنده ها و R مجموعه گیرنده ها دو زیرمجموعه مجزا از رئوس هستند. مساله پیدا کردن زیر گراف با کمترین هزینه است که هر گیرنده را به حداقل یک فرستنده وصل کند. نمونه ها را به دو مجموعه تقسیم کنیم: آنهایی که اجتماع این دو مجموعه تمام رئوس می شود و حالتی که نمی شود. نشان دهید این دو مساله به ترتیب در P و NP-hard هستند. برای حالت دوم الگوریتم تقریبی با ضریب 2 بدهید.

راهنمایی: یک راس جدید اضافه کنید که به هر فرستنده با یال با هزینه ی 0 وصل شده باشد. راس جدید و همه ی گیرنده ها را "لازم" و بقیه رئوس را اشتاینر در نظر بگیرید. درخت اشتاینر با کمترین هزینه را پیدا کنید.

حالتی که اجتماع این دو مجموعه کل رئوس شود: همه ی راسهای فرستنده را با هم ادغام می کنیم و یک ابر راس می سازیم. در این گراف MST را حساب می کنیم. چون هدف سوال وصل کردن این راسها با هزینه ی مینیمم است جواب بهینه MST است پس مساله در P است.

حالتی که اجتماع این مجموعه کل رئوس نشود: چون مجموعه ای از رئوس هستند که حضور آنها لازم نیست مساله به درخت اشتاینر تبدیل می شود که در NP-Hard است. برای حل آن راهنمایی سوال را اجرا می کنیم و الگوریتم با ضریب تقریب 2 به دست می آوریم.

3- کاهشی با حفظ ضریب تقریب از مساله پوشش مجموعه ای به مساله بعد بدهید و نشان دهید که این مساله نمی تواند ضریب تقریب بهتر از O(log n) داشته باشد.

درخت اشتاینر جهت دار: یک گراف جهت دار با یالهای با هزینه ی نامنفی داده شده است. مجموعه رئوس V به دو زیرمجموعه "لازم" و "اشتاینر" افراز شده است. یکی از راسهای لازم (r) یک راس ویژه است. مساله پیدا کردن درخت با کمترین هزینه است که ریشه ی آن r باشد و شامل همه ی راسهای لازم و هر زیر مجموعه ای از راسهای اشتاینر باشد.

راهنمایی: یک گراف سه لایه بسازید: لایه 1 شامل راسهای ضروری معادل هر عضو، لایه 2 شامل راسهای اشتاینر معادل هر مجموعه و لایه 3 شامل r.

همان طور که راهنمایی گفته است هر عضو مجموعه مرجع را یک راس ضروری در نظر می گیریم و هر مجموعه را یک راس اشتاینر در نظر می گیریم و با میانگین وزن اعضای آن به راسهای لازم متناظر آنها وصل می کنیم. چون این گراف همبند نیست یک راس r اضافه می کنیم و به همه ی راسهای اشتاینر آن را با هزینه 0 وصل می کنیم. (مثلا فرض کنید مجموعه تهی است). حالا با محاسبه ی درخت اشتاینر جهت دار، همه ی اعضای مجموعه مرجع انتخاب می شود و این کار با کمترین هزینه انجام می شود، پس جواب بهینه مساله پوشش مجموعه ای است. پس نمی تواند ضریب تقریب بهتری از این مساله که ضریب تقریب O(log n) دارد داشته باشد.

درخت اشتاینر و مساله فروشنده دوره گرد

درخت اشتاینر: یک گراف بدون جهت با یالهای وزندار نامنفی که راسهای آن به دو مجموعه ی "لازم" و "اشتاینر" تقسیم (افراز) شده اند، داده شده است. درخت با کمترین وزن را پیدا کنید که همه ی راسهای لازم را داشته باشد و هر چند تا از راسهای اشتاینر را هم داشت مهم نیست.

درخت اشتاینر متریک: درخت اشتاینری که روی یک گراف کامل ساخته شده باشد و برای وزن یالهای بین هر سه راس آن نامساوی مثلث برقرار باشد.

قضیه: می توان مساله ی درخت اشتاینر را به درخت اشتاینر متریک تبدیل کرد بدون اینکه ضریب تقریب به هم بخورد.

اثبات: در زمان چندجمله ای یک نمونه از مساله ی درخت اشتاینر را به درخت اشتاینر متریک تبدیل می کنیم.

یک گراف کامل روی مجموعه راسهای گراف اولیه می سازیم و وزن یالهای آن را طول کوتاهترین مسیر در گراف اولیه می گذاریم. به این گراف ثانویه گراف بستار متریک گراف اولیه می گویند. تقسیم راسهای لازم و اشتاینر را تغییر نمی دهیم.

برای هر یال گراف ثانویه هزینه ی آن از هزینه ی یال گراف اولیه کمتر مساوی است. پس هزینه ی جواب روی گراف ثانویه از هزینه ی جواب روی گراف اولیه کمتر مساوی است.

حالا درخت اشتاینر روی گراف ثانویه را به دست می آوریم (حالت متریک مساله است). می خواهیم آن را به درخت اشتاینر روی گراف اولیه تبدیل کنیم. به جای هر یال این درخت، مسیری متناظر آن در گراف اولیه را می گذاریم. با این کار همبندی به هم نمی خورد، اما ممکن است دور به وجود بیاید. اگر دور به وجود آمد یک یال را از آن حذف می کنیم تا دور از بین برود. درخت به دست آمده جواب مساله است که هزینه ی آن کمتر مساوی هزینه ی حالت متریک است پس تقریب هزینه به هم نمی خورد. (پایان اثبات)

الگوریتم درخت اشتاینر متریک:

تا اینجا ثابت کردیم که حالت متریک را حل کنیم حالت معمولی هم حل می شود. حالا می خواهیم حالت متریک را حل کنیم.

MST راسهای لازم را حساب می کنیم و این یک جواب غیربهینه برای مساله است. (چون MST در P است و درخت اشتاینر در NP-hard). اما این جواب غیربهینه فاصله ی کمی تا جواب بهینه دارد (ضریب تقریب 2).

اثبات (ضریب تقریب 2): درخت اشتاینر بهینه را در نظر بگیرید. با دو برابر کردن یالهای آن یک گراف اویلری به دست می آید. (درجه همه زوج است پس یک دوری وجود دارد که همه ی یالها را یک بار ببیند.). این گراف اویلری همه ی راسهای لازم را می بیند و تعدادی هم راس اشتاینر می بیند. با مثلا یک dfs این دور اویلری را پیدا کنید. هزینه ی این دور دو برابر جواب بهینه است. بعد یک دور همیلتونی بسازید، به این صورت که راسهای اشتاینر و راسهای قبلا دیده شده را بپرید (چون گراف کامل است می توانیم از هر راس به هر راسی برویم). طبق نامساوی مثلث با پریدن هزینه ی ما بیشتر نمی شود، پس اگر یک یال از این دور را حذف کنیم یک مسیر داریم که شامل همه ی راسهای لازم هست و هزینه اش حداکثر دو برابر جواب بهینه است. این مسیر یک MST روی راسهای لازم هم هست. پس هزینه ی MST روی راسهای لازم حداکثر دو برابر جواب بهینه است.

مثال tight: گراف با n راس لازم و یک راس اشتاینر را در نظر بگیرید. یال بین راس اشتاینر و راس لازم هزینه ی یک دارد و یال بین دو راس لازم هزینه ی 2 دارد. هر MST در این گراف 2(n-1) هزینه دارد، در حالی که جواب بهینه هزینه ی n دارد.

-------------------------------------------------------------------------------------------------------------

فروشنده دوره گرد: یک گراف کامل با یالهای وزندار نامنفی داده شده است، دور با کمترین هزینه را پیدا کنید که هر راس را دقیقا یک بار ببیند. (این مساله را نمی شود تقریب زد مگر اینکه P=NP باشد)

اثبات: برهان خلف: فرض کنید که یک الگوریتم تقریبی چند جمله ای باشد و ضریب آن را a(n) بگیرید. نشان می دهیم با این الگوریتم می توان تصمیم گیری مساله دور همیلتونی (فروشنده دوره گرد بدون وزن!) را حل کرد که در زمان چندجمله ای np-hard است. ایده ی اصلی کاهش از مساله ی دور همیلتونی به فروشنده دوره گرد است که یک گراف را به یک گراف کامل وزندار تبدیل می کند، به طوری که:

الف) اگر گراف اولیه دور همیلتونی داشته باشد، هزینه ی دور فروشنده دوره گرد بهینه در گراف ثانویه n است.

ب) اگر گراف اولیه دور همیلتونی نداشته باشد، هزینه ی دور فروشنده دوره گرد بهینه در گراف ثانویه بیشتر از a(n).n است.

در حالت الف، هزینه ی جواب بهینه از a(n).n کمتر/مساوی است و در حالت ب بیشتر است. پس می توان از آن برای تصمیم گیری وجود دور همیلتونی استفاده کرد. (پس اگر چنین کاری را بتوان انجام داد مساله ی np-hard را در زمان چند جمله ای حل کردیم.)

نحوه ی کاهش (reduction) هم ساده است. به هر یال گراف اولیه وزن 1 بدهید و برای ساخت گراف ثانویه به بقیه یالهایی که نبوده اند وزن a(n).n بدهید. حالا اگر گراف اولیه دور همیلتونی داشته باشد، هزینه ی جواب در گراف ثانویه n می شود، در غیر این صورت هر دور فروشنده دوره گرد در گراف ثانویه باید از یالی بگذرد که هزینه ی a(n).n دارد و در نتیجه هزینه ی آن از این مقدار بیشتر است.

الگوریتم ساده برای تقریب مساله فروشنده دوره گرد متریک با ضریب 2:

با حذف هر یال از فروشنده دوره گرد به یک MST برای گراف می رسیم، پس کران پایین را MST می گیریم.

الگوریتم:

1- یک MST روی گراف پیدا کن.

2- هر یال را دو برابر کن (بین دو راسی که قبلا یال بوده یک یال دیگر با همان وزن بگذار) و یک گراف اویلری به دست بیاور.

3- یک دور اویلری روی این گراف پیدا کن.

4- دوری را که راسهای گراف را به ترتیب آمدن آنها در دور (با راس تکراری!) اویلری می بیند برگردان.

(فکر کنم بهش میگن گذر، توی متن اصلی tour نوشته بود.)

قدم آخر الگوریتم مثل همان عمل پریدن از راسها است که در مساله ی قبل دیدیم. (به نظر من که همه ی مرحله های الگوریتمش مثل مساله قبل است.)

قضیه: الگوریتم بالا ضریب تقریب 2 برای فروشنده دوره گرد متریک می دهد.

اثبات: (دقیقا همان اثبات مساله ی قبل!)

مثال حالت بد: گراف کامل n راسی که یالهای آن وزنهای 1 و 2 دارند. یالهای بین یک راس v و بقیه راسها را وزن یک می دهیم و بقیه راسها هر کدام به دقیقا یک راس دیگر (به جز راس v) یال با وزن یک دارند و بقیه یالها وزن 2 دارند. پس تعداد یالهای با وزن 1 می شود 2(n-1) که یک ستاره و دور n-1 راسی می سازند. جواب بهینه روی دور حرکت می کند و قبل از اینکه به راس شروع برگردد از راس وسطی عبور می کند. این جواب هزینه ی n دارد. جواب الگوریتم ما MST است که مثلا می تواند گراف ستاره باشد، در این حالت گراف اویلری که از روی آن می سازیم دو یال با وزن 1 دارد و بقیه وزن 2 دارند، که در مجموع هزینه ی 2(n-1) دارد که دو برابر  جواب بهینه است.

بهبود الگوریتم به ضریب 3/2:

می خواهیم کار بهتری از دو برابر کردن یالها انجام بدهیم تا درجه ی راسها زوج شود و گراف اویلری شود. می توانیم فقط درجه های فرد را به هم وصل کنیم، یعنی یک تطابق (matching) کامل با کمترین هزینه انجام بدهیم.

لم: هزینه ی تطابق کامل یالهای درجه ی فرد (که تعدادشان زوج است چون جمع درجات زوج است) کمتر مساوی جواب بهینه است.

یک دور فروشنده دوره گرد بهینه را در نظر بگیرید، اگر از روی راسهای درجه زوج بپریم، دوری به دست می آوریم که هزینه ی آن کمتر است (طبق نامساوی مثلث در هنگام پرش!). این دور اجتماع دو تطابق کامل راسهای درجه فرد است که تطابق با وزن کمتر را که در نظر بگیریم هزینه ی آن کمتر مساوی نصف هزینه ی جواب بهینه است.

قضیه: این الگوریتم ضریب تقریب 3/2 برای فروشنده دوره گرد متریک دارد.

هزینه ی دور اویلری کمتر از هزینه ی MST + هزینه ی تطابق کامل راسهای فرد است؛ که این خودش کمتر مساوی جواب بهینه فروشنده دوره گرد + 1/2 جواب بهینه ی فروشنده دوره گرد است که می شود جمعا 3/2 جواب بهینه.

مثال tight: برای تعداد راس فرد، یک مسیر بسازید بعد هر راس را به راس بعدی نه راس بعدیش (دو تا راس جلوتر) وصل کنید همین کار را از راس آخر به اول هم انجام بدهید. همه ی این یالها را وزن 1 بدهید بعد از راس آخر به راس اول یک یال با وزن ceil(n/2) وصل کنید. MST که الگوریتم پیدا می کند همان مسیر است که هزینه ی n-1 دارد. تنها راسهای فردش هم راس اول و آخر هستند که با یال به وزن ceil(n/2) وصل می شوند. پس جواب الگوریتم می شود (n-1)+ceil(n/2). جواب بهینه هزینه ی n دارد: یال اول را برویم بعد یالهای پرشی را برویم. هزینه جواب الگوریتم 3/2 برابر جواب بهینه است.

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

کوتاهترین ابر رشته (فصل 2)

مجموعه متناهی از الفبا و n رشته s_i از این الفبا داده شده، کوتاهترین رشته s را بیابید که همه ی رشته های s_i زیر رشته آن باشند. بدون از دست رفتن عمومیت مساله فرض کنید هیچ رشته ای زیر رشته ی دیگری نباشد.

راه حل حریصانه: دو رشته با بیشترین اشتراک را اول قرار بدهیم، بقیه رشته ها را چک کنیم و رشته ای که پیشوند آن با پسوند رشته ی فعلی اشتراک بیشتری دارد انتخاب کنیم و همین کار را ادامه بدهیم.

تحلیل: رشته ها را از نقاط اشتراک آنها با رشته ی بعدی بازه بندی می کنیم. در این صورت هر رشته به حداکثر سه زیر رشته تقسیم می شود: قسمتی که با رشته ی قبل از خود اشتراک دارد، قسمتی که با کسی اشتراک ندارد و قسمت بعد که با رشته ی بعدی خود اشتراک دارد. جوابی که برای هر رشته به دست می آید حداکثر دو برابر جواب بهینه ی این دو رشته است. (مثال حالت بد: سه رشته ی cb...b و b...ba و b...b را که طول مساوی دارند در نظر بگیرید، اگر دو رشته اول را به هم بچسبانیم و بعد رشته ی فقط b را بگذاریم جواب cb..bab...b است که دو برابر حالتی است که اول فقط b را به یکی از رشته های دیگر بچسبانیم یعنی cb..ba.)

از اینجا نتیجه می شود الگوریتم حریصانه ی قبلی ضریب 2 دارد و خوب نیست. حالا سعی می کنیم آن را بهبود بدهیم.

راه حل حریصانه 2: با حذف ترتیب انتخاب مجموعه ها می توانیم انتخاب حریصانه ی بهتری انجام بدهیم. همه ی ابررشته های ممکن را برای هر دو رشته ورودی حساب می کنیم (نه فقط دو تا ابر رشته ی بهینه ی آنها را، نمی دانم چرا؟؟).

طبق تعریف ابر رشته ی بهینه، همه ی رشته های دیگر زیر رشته ی آن هستند و این ابررشته کمترین طول را دارد. پس ما می توانیم هزینه ی هر ابررشته ی زوج رشته {همان اجزای مساله که می گفتم} را تعداد زیرمجموعه های آن بگیریم. با این کار هنگام ادغام دو جواب مرحله ی قبل، با اجتماع گرفتن مجموعه ها به مجموعه ای می رسیم که زیر رشته های رشته های سازنده ی چند ابررشته است.

پس به حالتی از مساله ی پوشش مجموعه ای رسیده ایم که تعدادی مجموعه داریم (ابر رشته ی زوج رشته ها) که شامل زیر رشته های این ابررشته ها هستند و می خواهیم مجموعه ی مرجع همه ی زیرمجموعه های همه ی رشته ها را بپوشانیم. هزینه ی هر مجموعه هم تعداد زیر رشته های درون آن است.

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

(توی کتاب نگفته که چرا ابر رشته ها رشته مشترک ندارند یا اگر دارند چطور رشته های مشترک را حذف می کند و کاری می کند که یک رشته بیش از دو بار نیامده باشد.)

جواب نهایی شده ضرب ضریب تقریب این دو مساله: 2 * H(n)