МЕТОД СТРИБАЮЧИХ ЖАБ ДЛЯ ЗАДАЧІ ПРО МАКСИМАЛЬНУ КЛІКУ ГРАФУ

Анотація

Задача пошуку максимальної кліки в графі виникає в багатьох додатках теорії графів. Незважаючи на простоту формулювання ця задача відноситься до розряду задач, що важко розв’язуються в обчислювальному сенсі. Тому для цієї задачі виправдане застосування метаеврістік. У статті описана оригінальна метаеврістіка, яка заснована на фрагментарній моделі задачі про максимальну кліку. Наводиться визначення та основні поняття теорії фрагментарних структур. Дається загальний опис фрагментарного алгоритму. Доведено, що задача про максимальну кліку може бути зведена до задачі пошуку оптимальної перестановки вершин графа. Для цієї мети пропонується фрагментарна модель задачі про максимальну кліку. Показано, що будь-який оптимальний розв’язок задачі можна досягти в рамках цієї моделі. Алгоритм пошуку субоптимальних рішень будується як комбінація фрагментарного алгоритму на фрагментарній структурі і алгоритму перемішаних стрибаючих жаб. Пропонований підхід до вирішення задачі про максимальну кліку є універсальним. Він може бути легко поширений і на інші класи задач комбінаторної оптимізації, що важко розв’язуються.