پنج شنبه 28 تیر 1397 | Thursday 19 th of July 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-3-1-1-1 ساخت مجموعه غالب با استفاده از درخت پوشا

اولین ایده این الگوریتم ساختن یک مجموعه غالب توسط یک درخت پوشا است که با اضافه کردن مداوم گره‌ها و یالها کاری می‌کند که کل گره‌ها تحت پوشش قرار گیرند. این الگوریتم با استفاده از تغییر دادن رنگ گره‌ها شکل گرفته است و گره‌هایی که سفید هستند، هنوز مورد پردازش قرار نگرفته‌اند. گره‌های سیاه مجموعه غالب و گره‌های خاکستری اعضای تحت حاکمیت انها می‌باشند. قطعه کد زیر ابتدا گراف G=(V,E)، مجموعه یالهای Tکه متعلق به مجموعه غالب درخت مانند هستند و رنگهای گره‌ها را در نظر می‌گیرد. نتیجه یک بار اجرای این کد در تصویر 12 امده است.

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

initialize all nodes ’ color to white

pick an arbitrary node and color it gray

while (there are white nodes) {

 pick a gray node v that has white neighbors

 color the gray node v black

 foreachwhite neighbor u of v {

  color u gray

  add (v,u) to tree T

 }

}


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

قضاوت در انتخاب گره‌های خاکستری: یک ابتکار حریص راه حلی را برای مثال 11پیدا می‌کند ولی چند گراف وجود دارند که این راه حل در انها با شکست مواجه می‌شود. یکی از انها در شکل 10 نشان داده شده است. در اینجا الگوریتم از گره uشروع می‌شود و هر گره ایی که مستقیماً به uمتصل باشد را اضافه می‌کند و بعد باید ارتباط بین گره‌های متناظر uانتخاب کند که مستقیماً به vوصل شده است. اگر گره u، dتا همسایه داشته باشد، بدترین حالت برای الگوریتم حریص این است که مجموعه غالب در صورتی که ارتباط مجموعه غالب نیاز نباشد کافی خواهد بود.

شکل 10 گراف نمونه که در ان ابتکار حریص یک گامی مبتنی بر عملکرد شکست می‌خورد

دلیل این عملکرد غیربهینه این است که الگوریتم نمی‌تواند بین انتخاب گره خاکستری خط اول و دوم تمایز قائل شود. هر عملیات باعث کم شدن یک گره سفید می‌شود. این نزدیک بینی مانع فهم الگوریتم در این مورد که به محض انتخاب یک گره از ردیف دوم، گره زیرین vخاکستری است و می‌تواند به سیاه تبدیل گردد، با تولید مجموعه غالب مورد نیاز به عنوان گره vتمام گره‌های باقیمانده سفید در خط دوم پوشش داده خواهد شد. این نزدیک بینی با اجازه دادن به الگوریتم برای یک گام جلوتر را دیدن، برطرف می‌گردد[30]، به علاوه با در نظر گرفتن تبدیل گره‌های قهوه‌ای به سیاه الگوریتم می‌تواند به ‌هر دو گره خاکستری gو گره کناری سفید ان wنگاه کرده و فکر کند که در صورتیکه این گره wدر گام بعدی سیاه شود چه اتفاقی خواهد افتاد. ابتکار این خواهد بود که گره‌های خاکستری تک و یا گره‌های قهوه‌ایی و سفید را به صورت جفت انتخاب کرده تا بیشترین بازده را داشته باشد. این ایده در تصویر 11 نشان داده شده است قسمت بالا نشان دهنده مدل ابتکاری است که با تبدیل گره‌های خاکستری در ردیف بالا را به سیاه یکی پس از دیگری بدون هیچ فرایندی تبدیل کرده و شکست می‌خورد، انتخاب هر گره خاکستری به تنهایی بدون توجه به گره در ردیف دوم نتیجه 1 را خواهد داد.

 

 

 

 

 

 

 

 

شکل 11 ساخت مجموعه غالب حریص با و بدون نگاه به جلو

در قسمت دوم نگاه به جلو در گره‌هایی که به نام gو wنامگذاری شده‌اند(پس از مرحله اول الگوریتم) نتیجه 1 + ( d -1)را می‌دهد و گره‌های سفید به خاکستری تبدیل می‌شوند و یقیناً این بهتر از انتخاب گره‌ها به تنهایی است.

این مثال نشان می‌دهد که ابتکار نگاه به جلو امیدوار کننده است و ترجیحاً قدرتمندتر است

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26