ПРИМЕНЕНИЕ СВОЙСТВ МЕТРИЧЕСКИХ ПРОСТРАНСТВ В РАЗРАБОТКЕ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

М.А. Тренина
Download PDF
Аннотация: Для решения задач дискретной оптимизации широко применяются эвристические методы принятия решений. При этом эвристические алгоритмы обычно не гарантируют получение оптимального решения – однако с приемлемо большой вероятностью дают решение, близкое к оптимальному. Самым простым примером эвристических алгоритмов являются жадные алгоритмы, которые последовательно строят решение за несколько шагов, на каждом шаге включая ту «часть допустимого решения», которая в данный момент представляется наиболее выгодной. Но при этом жадный алгоритм может давать решения, стоимости которых сколь угодно больше оптимальных. Для исключения этой ситуации при разработке эвристических алгоритмов решения задач дискретной оптимизации, а именно, псевдогеометрической задачи коммивояжёра и задачи минимизации недетерминированных конечных автоматов, мы предлагаем использовать свойства метрических пространств. Для решения псевдогеометрической задачи коммивояжёра рассматривается несколько случайно сгенерированных перестановок всего множества точек – и для каждой из них применяется алгоритм псевдовосстановления их расположения. Выбор единственного варианта расположения каждой точки возможен после решения оптимизационной задачи – заключающейся в повороте сгенерированного множества точек на некоторый угол и смещения на некоторый вектор. На множестве всех возможных размещений для данного частного случая сформулированы различные метрики и изучены их свойства, на основании которых разработан эвристический алгоритм локального поиска. Для минимизации недетерминированных конечных автоматов применяются алгоритмы кластеризации подзадач в специальном мультиэвристическом подходе к задачам дис-кретной оптимизации. На полученном множестве подзадач рассматриваются дискретные метрики и изучаются их свойства. Следующая задача связана с расчётом метрики между строками ДНК различных видов организмов. Очевидным недостатком при расчёте расстояния между одной и той же парой строк ДНК является получение различных результатов при использовании различных алгоритмов для расчёта метрик. В связи с этим возникает задача, заключающаяся в разработке метода сравнительной оценки таких алгоритмов, а также сравнительной оценки различных восстановлений матрицы расстояний.
Ключевые слова: дискретная оптимизация, эвристика, метрика, полнота, компактность.

Контакты

Россия, 659305, Алтайский край, г. Бийск,
ул. Трофимова, 27, к. 404Б
Тел. +7-923-162-93-27
(ответственный секретарь -
Голых Роман Николаевич)
e-mail: info@s-sibsb.ru

Свидетельство