http://online.stanford.edu/course/general-game-playing-sp14
بعد از شروع یک بازی قوانین آن به صورت زبان فرمال به این عاملهای نرم افزاری داده می شود و آنها خودشان روش بازی مناسب را پیدا می کنند.
هدف کلی کار به دست آوردن روش کلی برای بازی کردن است که وابسته به یک بازی خاص نباشد. در حال حاضر برنامه هایی مثل شطرنج از یک الگوریتم خاص از قبل طراحی شده برای حل مساله استفاده می کنند.
زمینه: هوش مصنوعی، الگوریتم
دانشگاه ارائه دهنده درس: استنفورد (آنلاین)
الگوریتم های تقریبی برای تعمیم هایی از مساله برش کمینه بررسی می شوند که 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 می شود.
اینجا آزمایشگاهه و هیچ کس هم اینجا نیست به جز من و دوستم! :))
حس کردم این باید در تاریخ ثبت بشه!
روی همه چیزهای اینجا یه وجب خاک هست! :)
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 عضو است: خود رشته و معکوس آن.
همان طور که راهنمایی گفته است معکوس رشته را هم به مجموعه ی رشته ها اضافه می کنیم و مثل قبل حل می کنیم.
ب) کوتاهترین رشته ای را پیدا کنید که یا خود رشته یا معکوس آن را داشته باشد.
راهنمایی: به جای مجموعه ی ابررشته های هر رشته که قبلا به کار می بردیم، ابررشته های خود رشته یا معکوس آن را در نظر بگیرید. خود این ابررشته را به طور مناسب انتخاب کنید.
ابررشته های خود رشته که شامل معکوس آن نیستند یا ابررشته های شامل معکوس رشته که شامل خود رشته نیستند.
(؟)
دقت کنید که ضریبهای a و b و c در هر دو LP مقدارهای مشخص هستند.
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 است.
حل:
یک ضدزنجیره یک پوشش راسی از این گراف است، پس پوشش راسی کمینه بزرگترین ضدزنجیره است. اندازه ی آن با تطابق بیشینه مساوی است که کوتاهترین پوشش زنجیره ای است.
*بقیه سوالات فصل مربوط به ضمیمه بودند.
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) دارد داشته باشد.
