Задача о максимальной клике и ее приложения

<p>В своей работе мы рассматриваем три самых лучших последних алгоритма поиска оптимального выбора методом ветвей и границ для решения задачи о максимальной клике: алгоритм MCS, Томита и др. (2010) , алгоритм MAXSAT, Ли и Quan (2010a) и алгоритм BBMCXRS, Сегундо и Тапиа (2014). Мы предлагаем использовать ILS эвристику (Андраде и др., 2012) для получения начального решения высокого качества, которая используется, чтобы сократить дерево поиска в методе ветвей и границ. Вычислительные эксперименты показывают, что наш метод приводит к существенному уменьшению размера дерева поиска и значительному сокращению времени вычисления для всех рассмотренных алгоритмов. Кроме того, мы разработали наш алгоритм для решения задачи о максимальной клике (Маслов и др., 2013) и применили его к проблеме выравнивания структуры белка (для сравнения протеинов) с использованием подхода DAST, при этом проблема выравнивания структуры белка сначала водится к задаче о максимальной клике. Наш алгоритм основан на алгоритме MCS, который был недавно опубликован Томитой и др. (2010) . Мы значительно повысили производительность алгоритма MCS . Предложенный алгоритм, по меньшей мере, сопоставим с алгоритмом ACF, который применяется в инструменте DAST (он является самым быстрым точным алгоритмом) и намного лучше, чем Ostergard , MCS , MAXSAT и BBMCXRS алгоритмов</p>