Забелин С.Л.
СРАВНИТЕЛЬНЫЙ АНАЛИЗ «ПЕРВОГО ПОДХОДЯЩЕГО», ВЕРОЯТНОСТНОГО И ГЕНЕТИЧЕСКОГО АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО ГЕОМЕТРИЧЕСКОГО ПОКРЫТИЯ
Сибирский государственный университет телекоммуникации и информатики
В докладе рассматриваются решения задач оптимизации геометрического покрытия двумерных поверхностей различной формы с помощью «Первого подходящего», вероятностного и генетического алгоритмов. Принадлежность таких задач к классу NP-трудных, требует построения приближенных оптимизационных методов и алгоритмов.
Ключевые слова: NP-трудные задачи; проблема геометрического покрытия; вероятностный алгоритм; генетический алгоритм.
The report examines decisions of problems of optimization of a geometrical covering of two-dimensional surfaces of the various forms with the help «the First fit», probabilistic and genetic algorithms. That problem belongs to a class of NP-Completeness problem. Therefore such problem demands construction of the approached optimizing methods and algorithms.
Key words: NP-Completeness problem; problem of geometric covering; probabilistic algorithm; genetic algorithm.
Области применения задач максимального геометрического покрытия охватывают большое количество сфер деятельности человека. Они появляются в системах воздушного и космического наблюдения, системах безопасности, агротехнических системах, системах проектирования и других.
Актуальность данной задачи обусловлена также её принадлежностью к классу NP-трудных задач, сложность которых очень быстро возрастает с увеличением размерности. Для решения задач малой размерности можно использовать точные алгоритмы. Однако для задач большей размерности точные методы требуют значительных временных затрат и не дают хороших результатов. Эффективным является использование метаэвристических методов.