RE: الگوریتم بران-کرباش چی هست؟

                       

در موضوع پایان نامه‌ام به این الگوریتم برخورده ام، کسی میداند این الگوریتم چیست و چطور‌ کار میکند؟

افزودن نظر

الگوریتم بران-کرباش یکی از سریعترین الگوریتم‌ها برای پیدا کردن گروهک‌های بیشین است که در مواردی مانند خوشه‌بندی در شبکه‌های پویا، تجزیه و تحلیل آماری شبکه‌های مالی و تحلیل سیستم‌های اجتماعی کاربرد دارد.

نسخه‌ی اولیه‌ی الگوریتم بران-کرباش، همانطور که در شکل زیر مشخص است، به صورت یک الگوریتم بازگشتی پس‌گرد است. این الگوریتم سه مجموعه‌ی P، X و R را به عنوان ورودی می‌گیرد و تمام گروهک‌های بیشین گراف را به عنوان خروجی برمی‌گرداند. مجموعه‌ی R مجموعه‌ی تمام رئوسی هستند که عضو گروهک بیشین درحال بررسی هستند و به عنوان نتیجه‌ی موقتی در هربار اجرای الگوریتم، جمع‌آوری می‌شوند. مجموعه‌ی P مجموعه‌ی تمام رئوسی هستند که به عنوان نامزدهای احتمالی جهت اضافه شدن به گروهک بیشین مورد بررسی و به طور خاص مجموعه‌ی R معرفی می‌شوند. مجموعه‌ی X نیز شامل تمام گره‌هایی است که قبلا بررسی شده‌اند. یعنی مجموعه‌ای از تمام رئوسی که قبلا عضو مجموعه‌ی P بوده‌اند و گروهک‌های بیشین حاوی آن‌ها، گزارش شده است

RE: الگوریتم بران-کرباش چی هست؟

در اولین فراخوانی الگوریتم، مجموعه‌های R و X مجموعه‌های تهی هستند. اما مجموعه‌ی P حاوی تمام رئوس گراف ورودی است. در هر بار فراخوانی بازگشتی، الگوریتم رئوس موجود در مجموعه‌ی P را به ترتیب در نظر می‌گیرد. درصورتیکه مجموعه‌ی P تهی باشد، یعنی هیچ راس دیگری در آن نباشد، و همچنین مجموعه‌ی X نیز تهی باشد، یعنی هیچ عنصر دیگری در شبکه وجود نداشته باشد که بتواند به R اضافه شود، رئوس موجود در مجموعه‌ی R به عنوان یک گروهک بیشین گزارش می‌شوند. در غیر اینصورت، الگوریتم برای هر راس v که از P انتخاب شده است، یکبار دیگر تابع بازگشتی را فراخوانی می‌کند که در آن فراخوانی، راس v به مجموعه‌ی R اضافه شده و مجموعه‌های P و X محدود به مجموعه‌ی رئوس همسایه‌ی راس v می‌شوند. این مهم برای بررسی تمام رئوس مرتبط با v انجام می‌شود تا مجموعه‌ی تمام گروهک‌های بیشین حاوی v در R مشخص شود. پس از پایان فراخوانی، راس v از مجموعه‌ی P به مجموعه‌ی X منتقل می‌شود تا این راس از فرآیند بررسی گروهک‌های آینده حذف شود. به این ترتیب الگوریتم با راس بعدی در P ادامه می‌یابد.

پاسخ داده شده در ۱۳۹۹/۱۰/۰۶.
افزودن نظر

پاسخ شما

برای ارسال پاسخ, شما باید شرایط و ضوابط و قوانین و حریم خصوصی را قبول کنید