الگوریتمی تقریبی برای حل مسالهی خوشهبندی همبستگی با استفاده از عملیات ماتریسی
Volume 11, 1(Persian Issue), April 2024, Pages 91-110
https://doi.org/10.22072/wala.2023.1988384.1411
علی شکیبا
Abstract مسالهی خوشهبندی همبستگی، یکی از شهودیترین مدلهای افراز یک گراف مشابهت به اجتماعی از خوشهها است. متاسفانه این مساله در ردهی مسائل NP-سخت قرار دارد. به همین دلیل، ارائهی یک الگوریتم کارآ از زمان چندجملهای که یک افراز دقیق و بهینه را برای گرافهای دلخواه ایجاد نماید، بعید بهنظر میرسد. در این مقاله، ابتدا یک فرمولبندی جدید از این مساله با استفاده از رویکردی حریصانه به منظور محاسبهی پاسخی تقریبی در زمان چندجملهای ارائه خواهیم داد. سپس، با استفاده از عملیات پایهی ماتریسی، فرمولبندی معادل از الگوریتم ارائه شده را ارائه خواهیم کرد که در هر زبان برنامهنویسی مبتنی بر عملیات ماتریسی، به سادگی قابل پیادهسازی است. علاوه بر این، فرمولبندی ارائه شده امکان استفاده از توازی موجود در عملیات ماتریسی پایه را فراهم مینماید.