چهارشنبه 28 شهریور 1397 | Wednesday 19 th of September 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-4-2ملاحظات عملکردی در مورد خوشه‌بندی

رتبه بندی دیگری علاوه بر شناسه‌ها و درجه‌های گره‌ها قابل انجام است. باساگانی[1] و همکاران وزن هر گره را در نظر گرفته و مسئله‌ایی به نام حداکثر وزن مجموعه مستقل[2] (MWIS)را درخوشه‌بندی معرفی نمودند.در اینجا هدف یافتن مجموعه مستقلی از گره‌هاست، به نحوی که مجموع وزن گره‌های داخل مجموعه حداکثر ممکن باشد و چون این روش تعمیم یافته مسئله یافتن حداکثر خوشه‌هایی مستقل است تبدیل به یک مسئله NP-Completeشده است الگوریتم توضیح داده شده در مرجع [21]بسیار ساده و شبیه به الگوریتم مشروحه فوق است این الگوریتم متمرکز در هر نوبت گره‌ایی که بیشترین وزن را دارد را به عنوان سرخوشه انتخاب می‌کند، سپس تمام گره‌های همسایه این سرخوشه را تعیین می‌کند و همه این گره‌ها، از مجموع گره‌هایی که باید در نظر گرفته شوند حذف می‌گردند، نتیجه کار مجموعه‌ایی از سرخوشه‌های مستقل برتر با خوشه‌های غیر هم پوشان خواهد بود.

عملکرد خوب این الگوریتم بستگی به انتخاب واقعی و درست وزنها دارد ممکن است یک حد پایین در مورد عملکرد ان قائل شویم به این دلیل که وزن ها همگی مثبت هستند و منفی نمی‌شوند. برای این کار ایده پیاده‌سازی الگوریتم خوشه‌بندی باید بسیار با دقت طراحی شود، واضح است که باید نحوه تقریب و براورد مجموعه‌ایی که حداکثر وزن را دارد بررسی گردد، به عبارت دیگر نرخ حداکثر وزن بهترین مجموعه مستقل، و وزن مجموعه ساخته شده توسط الگوریتمی که در گراف Gامده، و وزن گره‌ها با Wنشان داده شده چقدر است؟ با استفاده از این تعریف، شیوه باساگانی و همکاران نشان داد که الگوریتم تعمیم داده شده‌ همواره مجموعه غالبی پیدا می‌کند که حداقل وزن ان عبارت است از  D/ حداکثر وزن که در این حالت Dحداکثر درجه گراف می‌باشد



[1] Basagni

[2] Maximun Weight Independent Set(MWIS)

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