МЕТАЕВРІСТИКИ НА БАЗІ ФРАГМЕНТАРНИХ МОДЕЛЕЙ ДЛЯ ЗАДАЧІ ПОКРИТТЯ МНОЖИН ТОЧОК НА ПЛОЩИНІ

Анотація

Задача покриття кінцевих множин точок на площині фігурами різних типів належить до складних задач дискретної оптимізації. Існує досить багато варіантів цієї задачі, більшість яких належать до класу NP-важких задач. Для пошуку точних розв’язків задач покриття відсутні алгоритми поліноміальної трудомісткості. Звичайно, існують точні алгоритми для цієї задачі, але всі вони зводяться до повного перебору варіантів. Навіть більше, невідомі й наближені алгоритми розв’язку таких задач із заданими оцінками точності. Тому значний інтерес становлять розроблення та дослідження евристичних методів оптимізації. Одним із перспективних напрямів є розроблення алгоритмів, заснованих на відомих метаеврістичних підходах, які з успіхом використовуються для вирішення багатьох задач дискретної оптимізації. Одним зі слабких місць використання метаевристик є наявність обмежень у багатьох задачах точкового покриття. Зокрема, це всілякі перепони, обмеження розміщення точок, обмеження, пов’язані з можливими перетвореннями точок у координатному просторі (зрушення, повороти). Тому найчастіше доводиться модифікувати відомі алгоритми. Це призводить до великої різноманітності метаевристик, які відомі за однією назвою (генетичний алгоритм, мурашиний алгоритм), але насправді орієнтовані на чітко визначене коло задач. Це призводить до труднощів у створенні програмних продуктів, які стають індивідуальними для різних задач. Основна мета даної роботи – розробити універсальний підхід до розв’язання складних в обчислювальному сенсі задач, який дозволяє використовувати відомі метаеврістики для різних класів задач покриття без суттєвих змін алгоритмів. Для цього запропоновано метод побудови гібридних алгоритмів, що є комбінацією фрагментарного алгоритму, який є індивідуальним для кожного виду задачі покриття, і метаеврістики, яка вже не прив’язана до конкретного класу задач. Такий метод може бути легко перенесений і на інші класи задач дискретної оптимізації, для яких можна побудувати фрагментарну модель.