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

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

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

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

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

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

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

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

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

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

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 برابر جواب بهینه است.

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