Статья
11/20/2015

Декабрь 2011

Том 26, номер 12

Тестовый прогон - Алгоритмы запрещенного поиска и максимальная клика

Джеймс Маккафри | Декабрь 2011

Джеймс Маккафри На этот раз я представлю более «продвинутое» решение задачи о максимальной клике графа (graph maximum clique). Решение использует так называемый алгоритм запрещенного поиска (tabu algorithm), и я расскажу, как разрабатывать и проверять такие алгоритмы. Идея задачи о максимальной клике заключается в нахождении наибольшей группы узлов в графе, которые все соединены друг с другом. Взгляните на простой граф на рис. 1. В этом графе девять узлов и 13 ребер. Граф является невзвешенным (с ребрами не сопоставлены никакие приоритеты) и ненаправленным (все ребра двунаправленные). Узлы 2, 4 и 5 образуют клику размером в три узла. Максимальная клика — это набор из узлов 0, 1, 3 и 4, образующие клику размером в четыре узла.

Рис. 1. Граф для алгоритма запрещенного поиска максимальной клики

Задача о максимальной клике интересна по нескольким причинам. Хотя это неочевидно в простом графе на рис. 1, задача о максимальной клике оказывается одной из наиболее трудных в компьютерной науке. Она возникает во многих важных практических задачах, например при анализе коммуникаций в социальных сетях, где узлы представляют людей, а ребра — сообщения или отношения. В решении этой задачи применяются такие алгоритмы, как жадные (greedy algorithms) и запрещенного поиска (tabu algorithms), которые являются важными продвинутыми методами программирования. Код, решающий задачу о максимальной клике, может оказаться полезным непосредственно вам, а понимание используемого алгоритма — полезным для решения других сложных задач программирования.

Это третья статья в серии, где задача о максимальной клике используется для иллюстрации сложных методов кодирования и тестирования, но эту статью можно читать отдельно от первых двух. В позапрошлом номере в статье «Graph Structures and Maximum Clique» (msdn.microsoft.com/magazine/hh456397) я описал, как кодировать эффективную структуру данных для хранения структуры данных графа в памяти. В прошлой статье «Greedy Algorithms and Maximum Clique» (msdn.microsoft.com/magazine/hh547104) я рассказал, как сравнительно простой алгоритм позволяет находить решение трудной задачи о максимальной клике.

В вольной трактовке жадным является алгоритм, который начинает с простого, неполного решения трудной задачи, а затем итеративно ищет лучший способ повышения качества решения. Этот процесс повторяется, пока не будет достигнуто какое-то условие прекращения. Однако у жадных алгоритмов, как правило, есть одна слабая сторона: они будут повторно генерировать одно и то же решение — снова и снова. Алгоритмы запрещенного поиска как раз и нацелены на устранение этой слабой стороны. Слово табу (tabu, которое иногда пишется как taboo) означает нечто запрещенное. В простых терминах эти алгоритмы поддерживают список запрещенных данных. Части алгоритма, занимающейся обработкой, не разрешается использовать «табуированные» данные до тех пор, пока не пройдет некое время запрета (prohibit time). Простые формы алгоритмов запрещенного поиска используют фиксированное время запрета. В более сложных алгоритмах запрещенного поиска время запрета действует динамически.

Рис. 2 иллюстрирует важные идеи алгоритма запрещенного поиска, применимого к задаче о максимальной клике, и показывает, куда я клоню в этой статье.

Рис. 2. Выполнение программы, демонстрирующей алгоритм запрещенного поиска в решении задачи о максимальной клике

У меня есть консольное приложение, которое начинает с загрузки в память графа, соответствующего тому, который приведен на рис. 1. Файл графа имеет стандартный формат DIMACS. Разработка и кодирование эффективной структуры данных графа сама по себе является сложной задачей. Код этой структуры я объяснил в первой статье цикла.

Сначала алгоритм случайным образом выбирает отдельный узел и инициализирует клику этим узлом. Затем алгоритм пытается итеративно найти и добавить лучший узел, который увеличит размер клики. Позже я поясню, что означает понятие «лучший узел». Если алгоритм не может найти узел для добавления, он пытается найти лучший узел для удаления из клики. На внутреннем уровне алгоритм запоминает последнее время, в которое каждый узел добавлялся в текущую клику или удалялся из нее. На основе этой информации алгоритм запрещает добавление или удаление недавно использовавшихся узлов на определенный период времени. Это запрещающая часть алгоритма.

Алгоритм перезапускает сам себя каждый раз, когда не происходит прогресса в нахождении более качественной (более крупной) клики. Алгоритм автоматически сохраняет решения (клики), которые встречались ему ранее. Эту информацию он использует для динамического изменения времени запрета. Если алгоритм продолжает встречать одно и то же решение, он увеличивает время запрета, чтобы исключить обработку ранее использовавшихся узлов. Если алгоритм не встречает те же решения, он уменьшает время запрета, чтобы увеличить пул узлов для выбора. Это адаптивная часть алгоритма запрещенного поиска.

В большинстве задач, где применяются жадные алгоритмы, оптимальное решение не известно, поэтому требуется указывать одно или несколько условий прекращения его выполнения. Когда алгоритм встречает условие прекращения, отображается лучшая найденная клика.

В последующих разделах я буду разбирать код, который создал результат, показанный на экранном снимке на рис. 2. Полный исходный код можно скачать как пакет, сопутствующий этой статье (тот же код, что и к прошлой статье). В этой статье предполагается, что вы умеете программировать хотя бы на среднем уровне на языках семейства C или на языке Visual Basic .NET. Я использую C#, но код написан так, что при желании вы сможете переработать его под другой язык, например F# или Python, без особых усилий.

Общая структура программы

Общая структура программы с рис. 2 представлена на рис. 3. Я решил для простоты поместить весь код в одно консольное приложение, использующее статические методы, но вы можете разделить код на модули, поместить их в библиотеки классов и применить объектно-ориентированный подход. Программа не столь сложна, как может показаться при взгляде на рис. 3, так как большая ее часть является короткими вспомогательными методами.

Рис. 3. Общая структура программы

using System;
using System.Collections.Generic; // List<int>
using System.Text; // StringBuilder
using System.IO; // FileStream
using System.Collections; // Hashtable
namespace TabuMaxClique
{
  class TabuMaxCliqueProgram
  {
    static Random random = null;
    static void Main(string[] args) { ... }
    static List<int> FindMaxClique(MyGraph graph, int maxTime,
      int targetCliqueSize) { ...  }
    static List<int> MakePossibleAdd(MyGraph graph,
      List<int> clique) { ... }
    static bool FormsALargerClique(MyGraph graph,
      List<int> clique, int node) { ... }
    static int GetNodeToAdd(MyGraph graph,
      List<int> allowedAdd, List<int> possibleAdd) { ... }
    static int GetNodeToDrop(MyGraph graph, List<int> clique,
      List<int> oneMissing) { ... }
    static List<int> MakeOneMissing(MyGraph graph,
      List<int> clique) { ... }
    static List<int> SelectAllowedNodes(List<int> listOfNodes,
      int time, int prohibitPeriod, int[] lastMoved) { ... }
    static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
      int bestSize, Hashtable history, int time, int prohibitPeriod,
      ref int timeProhibitChanged) { ... }
    static string ListAsString(List<int> list) { ... }
    private class CliqueInfo
    {
      // ...
    }
  }
  public class MyGraph
  {
    // ...
    private class BitMatrix
    {
      // ...
    }
  }
} // ns

В программе два высокоуровневых класса, и каждый из них имеет вспомогательный подкласс. Класс TabuMaxCliqueProgram содержит метод Main и всю логику алгоритма наряду с подклассом CliqueInfo, который используется для поддержки истории ранее встречавшихся решений. Класс MyGraph инкапсулирует эффективное представление графа и содержит подкласс BitMatrix, который применяется для хранения информации о смежных узлах в сжатой форме. Объект Random с именем random области класса используется для инициализации клики случайным узлом и для разрыва связей, когда есть несколько лучших узлов для добавления или удаления.

Метод Main выглядит так (я удалил из него ряд выражений WriteLine и код try-catch):

Console.WriteLine("\nBegin tabu algorithm maximum clique demo\n");
string graphFile = "..\\..\\DimacsGraph.clq";
MyGraph graph = new MyGraph(graphFile, "DIMACS");
int maxTime = 50;
int targetCliqueSize = graph.NumberNodes;
List<int> maxClique = FindMaxClique(graph, maxTime, targetCliqueSize);
Console.WriteLine("\nSize of best clique found = " + maxClique.Count);
Console.WriteLine(ListAsString(maxClique));

Граф представляется определенным в программе объектом MyGraph. Он загружается из внешнего текстового файла, имеющего формат DIMACS. Ключевой метод в MyGraph — AreAdjacent, который возвращает true, если два узла соединены. Я установил maxTime на 50 итераций, и это абсолютное условие прекращения для жадного алгоритма. Данное значение искусственно занижено. В настоящей задаче о максимальной клике maxTime обычно находится в диапазоне от 1000 до 100 000. Я также задал размер targetClique, чтобы ввести второе условие прекращения; если обнаруживается клика, которая имеет то же количество узлов, что и в самом графе, значит, найдена максимальная клика. Большая часть работы выполняется методом FindMaxClique, использующим жадный, адаптивный алгоритм запрещенного поиска наибольшей из возможных клик. Вспомогательный метод ListAsString просто создает строковое представление объекта List<int>.

Метод FindMaxClique

Метод FindMaxClique вызывает несколько вспомогательных методов, которые я вскоре опишу. В высокоуровневом псевдокоде алгоритм FindMaxClique представлен на рис. 4. В этом псевдокоде пропущен ряд важных деталей для большей ясности, но он отражает суть алгоритма.

Рис. 4. Адаптивный алгоритм запрещенного поиска максимальной клики

Инициализируем клику одним узлом
Получаем список узлов-кандидатов на добавление
Цикл, пока не сработает условие прекращения
  if есть узлы, которые можно добавить,
    получаем список разрешенных узлов
    if есть разрешенные для добавления узлы,
      находим лучший узел и добавляем в клику
      помечаем добавленный узел как недавно использовавшийся
      регистрируем текущую клику
  else
    получаем список разрешенных для удаления узлов
    if есть разрешенные для удаления узлы,
      находим лучший узел и удаляем из клики
      помечаем удаленный узел как недавно использовавшийся
      регистрируем текущую клику
  else
    выбираем случайный узел и удаляем из клики
    помечаем удаленный узел как недавно использовавшийся
    регистрируем текущую клику

  if нет прогресса
    перезапуск алгоритма

    обновляем список узлов-кандидатов
    обновляем время запрета
Конец цикла
Возвращаем наибольшую найденную клику

Определение метода FindMaxClique начинается с:

static List<int> FindMaxClique(MyGraph graph, int maxTime,
  int targetCliqueSize)
{
  List<int> clique = new List<int>();
  random = new Random(1);
  int time = 0;
  int timeBestClique = 0;
  int timeRestart = 0;
  int nodeToAdd = -1;
  int nodeToDrop = -1;
...

Локальный объект clique является текущим решением. Экземпляр объекта random создается с произвольным зародышевым значением 1. Переменная time — это счетчик основного цикла обработки в алгоритме. Переменные timeBestClique и timeRestart используются для определения того, отсутствовал ли прогресс, чтобы алгоритм мог перезапустить сам себя. Далее:

int prohibitPeriod = 1;
int timeProhibitChanged = 0;
int[] lastMoved = new int[graph.NumberNodes];
for (int i = 0; i < lastMoved.Length; ++i) {
  lastMoved[i] = int.MinValue;
}
Hashtable history = new Hashtable();
...

Период запрета (prohibitPeriod) инициализируется значением 1. Это означает, что — по крайней мере, изначально — после того, как узел был задействован алгоритмом, его нельзя использовать в течение одной итерации. Если бы я указал значение 0, это привело бы к тому, что периода запрета вообще не было бы. В большинстве «табуированных» алгоритмов применяют фиксированное значение для периода запрета, но проблема с таким подходом в том, что, как показали исследования, лучшее значение для фиксированного периода запрета варьируется от задачи к задаче. Представленный мной адаптивный подход обеспечивает обновление периода запрета в процессе выполнения алгоритма на основе истории предыдущих решений. Я называю этот метод адаптивным запрещенным поиском, но в некоторых исследовательских статьях он фигурирует как реактивный или динамический.

Массив lastMoved позволяет в любой момент определять, является узел разрешенным или запрещенным. Индекс массива представляет узел, а соответствующее значение в массиве — это время, в котором узел перемещался в последний раз (добавлялся или удалялся). С помощью массива lastMoved я избегаю необходимости в явном создании списка разрешенных узлов (или эквивалентного списка запрещенных узлов). Я инициализирую все ячейки lastMoved значением int.MinValue, чтобы потом можно было определить, использовался ли вообще какой-то узел.

Объект Hashtable с именем history хранит набор ранее встречавшихся решений. Каждый элемент в хеш-таблице является объектом CliqueInfo, который я подробно опишу позже. Я мог бы задействовать обобщенный объект Dictionary вместо не обобщенного объекта Hashtable. FindMaxClique продолжает следующим образом:

int randomNode = random.Next(0, graph.NumberNodes);
clique.Add(randomNode);
List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...

Я инициализирую текущее решение клики случайным узлом из графа и создаю экземпляр списка bestClique для отслеживания лучшей (самой крупной) клики, найденной алгоритмом. Потом выполняется такой код:

List<int> possibleAdd = MakePossibleAdd(graph, clique);
List<int> oneMissing = MakeOneMissing(graph, clique);
...

Метод MakePossibleAdd конструирует список всех узлов, которые можно добавить в текущую клику, чтобы увеличить ее размер на 1. Другими словами, этот метод создает список узлов, не находящихся в клике, но соединенных с каждым узлом в клике. Этот список possibleAdd может иметь счетчик, равный 0, или содержать запрещенные узлы. MakePossibleAdd вызывает вспомогательный метод FormsALargerClique.

Метод MakeOneMissing конструирует список всех узлов, соединенных со всеми, кроме ровно одного из узлов в текущей клике. Эта операция неочевидна, но, как оказывается, поддержка такого списка обеспечивает «интеллектуальный» способ определения того, какой узел в текущей клике является лучшим для удаления (поясню позже). Основной цикл обработки начинается так:

while (time < maxTime && bestSize < targetCliqueSize)
{
  ++time;
  bool cliqueChanged = false;
...

Основной цикл обработки завершится, когда будет достигнуто максимальное число итераций или если будет найдено лучшее решение с целевым размером клики. С помощью переменной cliqueChanged я управляю логикой ветвления между добавлением и удалением узлов. Логика для добавления разрешенного узла показана на рис. 5.

Рис. 5. Логика для добавления разрешенного узла

if (possibleAdd.Count > 0) {
  List<int> allowedAdd = SelectAllowedNodes(possibleAdd, time,
    prohibitPeriod, lastMoved);
  if (allowedAdd.Count > 0) {
    nodeToAdd = GetNodeToAdd(graph, allowedAdd, possibleAdd);
    clique.Add(nodeToAdd);
    lastMoved[nodeToAdd] = time;
    clique.Sort();  cliqueChanged = true;
    if (clique.Count > bestSize) {
      bestSize = clique.Count;
      bestClique.Clear();
      bestClique.AddRange(clique);
      timeBestClique = time;
    }
  }
}
...

Алгоритм проверяет, есть ли какие-нибудь узлы, которые увеличат размер текущей клики. Если да, метод SelectAllowedNodes создает список разрешенных узлов из списка узлов, которые можно добавить.

Ключевой строкой в SelectAllowedNodes является:

if (time > lastMoved[currNode] + prohibitPeriod)
  result.Add(currNode); // разрешен

Узел currNode — один из находящихся в списке possibleAdd. Логика проверяет, достаточно ли прошло времени с момента последнего использования этого узла, т. е. закончен ли период запрета. Если да, узел добавляется в список узлов allowedAdd.

Теперь, если есть любые разрешенные узлы, которые увеличат размер клики, метод GetNodeToAdd определяет лучший узел для добавления в клику. Лучшим является узел из списка allowedAdd, который соединен в наибольшей мере с узлами из списка possibleAdd. Идея в том, чтобы добавить узел, который даст вам самые большие шансы на нахождение узла для добавления на следующей итерации алгоритма. В списке allowedAdd может быть несколько узлов, в наибольшей мере соединенные с узлами в possibleAdd. Если это так, один из связанных узлов выбирается случайным образом. После добавления лучшего узла текущее решение сортируется с учетом остальных решений по причине, о которой я расскажу позже. Код для удаления узла выглядит так:

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    List<int> allowedInClique = SelectAllowedNodes(clique, time,
      prohibitPeriod, lastMoved);
    if (allowedInClique.Count > 0) {
      nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
      clique.Remove(nodeToDrop);
      lastMoved[nodeToDrop] = time;
      clique.Sort();  cliqueChanged = true;
    }
  }
}
...

Если алгоритм не может добавить узел, он пытается удалить разрешенный узел в надежде, что поиск с возвратом (backtracking) даст решение, которое позволит добавить новый узел на следующей итерации. Список узлов текущей клике фильтруется методом SelectAllowedNodes, чтобы получить узлы, не попавшие под запрет. GetNodeToDrop выбирает лучший из этих узлов для удаления, используя список узлов oneMissing.

Идея в том, чтобы удалить разрешенный узел в текущей клике, что приведет к самому большому увеличению списка узлов possibleAdd. Один из способов сделать это — проверить каждый узел в списке разрешенных узлов, реально удаляя его из текущей клики, а затем вычисляя размер полученного списка possibleAdd. Но существует гораздо более эффективный подход, где используется список узлов, которые соединены со всеми, кроме ровно одного из узлов в текущей клике. Применить список узлов oneMissing можно следующим образом. Просканировать каждый узел в клике из числа разрешенных и подсчитать, сколько узлов в списке oneMissing не соединено с узлом клики. Узел в списке разрешенных в клике, имеющий наименьшее число соединений с узлами в списке oneMissing, является лучшим для удаления. После его удаления все узлы в списке oneMissing, которые не были соединены с удаленным узлом, станут полностью соединенными с оставшимися узлами в клике, а значит, будет новыми узлами possibleAdd.

В этой точке может оказаться невозможным добавить или удалить разрешенный узел. Чтобы выйти из этого тупика, алгоритм удаляет случайный узел из текущей клики:

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    nodeToDrop = clique[random.Next(0, clique.Count)];
    clique.Remove(nodeToDrop);
    lastMoved[nodeToDrop] = time;
    clique.Sort();
    cliqueChanged = true;
  }
}
...

Затем алгоритм проверяет, отсутствует ли прогресс, и, если да, перезапускается:

int restart = 100 * bestSize;
if (time - timeBestClique > restart && time - timeRestart > restart) {
  timeRestart = time;
  prohibitPeriod = 1;
  timeProhibitChanged = time;
  history.Clear();
...

Переменная restart — это число итераций, допустимых в отсутствие улучшения или с момента последнего перезапуска. Здесь я указываю значение в 100 раз большее размера текущего лучшего решения. Значение для интервала restart недостаточно исследовано, и вы можете предпочесть попробовать какие-то альтернативы. (Я использовал произвольное значение 2 для более частого перезапуска на экранном снимке на рис. 2.) Однако на практике это значение отлично сработало для меня. Если происходит перезапуск, алгоритм сбрасывает время запрета и очищает историю в хеш-таблице, хранящей встречавшиеся решения. Заметьте, что алгоритм пока не обновлял историю в хеш-таблице. Но код перезапуска не сбрасывает массив lastVisited, который хранит информацию о том, когда в последний раз добавлялись или удалялись узлы из текущего решения (клики). Далее идет такой код:

int seedNode = -1;
List<int> temp = new List<int>();
for (int i = 0; i < lastMoved.Length; ++i) {
  if (lastMoved[i] == int.MinValue) temp.Add(i);
}
if (temp.Count > 0)
  seedNode = temp[random.Next(0, temp.Count)];
else
  seedNode = random.Next(0, graph.NumberNodes);
...

Алгоритм пытается заново инициализировать клику решения узлом, который никогда до этого не использовался. Если таких узлов несколько, один из них выбирается случайным образом. Если неиспользовавшихся узлов нет, выбирается случайный узел. Вместо применения случайного узла есть неисследованная альтернатива — выбор узла, который дольше других не перемещался. Код перезапуска заканчивается так:

...
  clique.Clear();
  clique.Add(seedNode);
}

Основной цикл обработки и FindMaxClique завершаются следующим образом:

...
    possibleAdd = MakePossibleAdd(graph, clique);
    oneMissing = MakeOneMissing(graph, clique);
    prohibitPeriod = UpdateProhibitPeriod(graph, clique, bestSize,
      history, time, prohibitPeriod, ref timeProhibitChanged);
  } // основной цикл обработки
  return bestClique;
}

Списки possibleAdd и oneMissing генерируются заново. Альтернатива — поддерживать вспомогательные структуры данных и обновлять эти два списка вместо повторного их создания с нуля. Метод UpdateProhibitPeriod является ключевым компонентом адаптивной части алгоритма запрещенного поиска, и я вскоре опишу его.

Запоминание предыдущих решений

Метод UpdateProhibitPeriod использует хеш-таблицу ранее встречавшихся решений для динамического увеличения или уменьшения времени запрета. Вспомните, что решение — это клика, которая является List<int> узлов, полностью соединенных друг с другом. Но мне также нужно хранить время, когда было найдено последнее решение. Поэтому я инкапсулирую решение и последнее время, в которое оно встречалось, в классе CliqueInfo (рис. 6).

Рис. 6. Класс CliqueInfo

private class CliqueInfo
{
  private List<int> clique;
  private int lastSeen;
  public CliqueInfo(List<int> clique, int lastSeen)
  {
    this.clique = new List<int>();
    this.clique.AddRange(clique);
    this.lastSeen = lastSeen;
  }
  public int LastSeen
  {
    get { return this.lastSeen; }
    set { this.lastSeen = value; }
  }
  public override int GetHashCode()
  {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < clique.Count; ++i) {
      sb.Append(clique[i]);
      sb.Append(" ");
    }
    string s = sb.ToString();
    return s.GetHashCode();
  }
  public override string ToString()
  {
    string s = "";
    for (int i = 0; i < clique.Count; ++i)
      s += clique[i] + " ";
      return s;
  }
}

Поскольку элемент CliqueInfo будет добавлен к объекту Hashtable истории решений, мне нужна своя хеш-функция GetHashCode. Написание собственных хеш-функций — дело на удивление сложное, и полное обсуждение всех проблем, связанных с ними, потребовало бы отдельной статьи. В этой ситуации я использую простейший, но не самый эффективный подход. Я создаю строковое представление узлов в поле clique, разделяемых пробелами, а затем вызываю встроенный String.GetHashCode. Например, если клика содержит узлы {3 5 8}, я генерирую "3 5 8 " (с концевым пробелом), а затем создаю хеш-код из этой строки. Вспомните, что клики всегда поддерживаются в отсортированном порядке, поэтому невозможно, чтобы одна клика была {3 5 8}, а другая — {8 3 5}. Я помещаю пробелы между узлами, чтобы отличать клику {3 5 8} от клики {3 58}.

Обновление периода запрета

Метод UpdateProhibitPeriod адаптивно изменяет период запрета на основе ранее встречавшихся решений. Метод начинается с:

static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
  int bestSize, Hashtable history, int time, int prohibitPeriod,
  ref int timeProhibitChanged)
{
  int result = prohibitPeriod;
  CliqueInfo cliqueInfo = new CliqueInfo(clique, time);
. . .

Этот метод будет возвращать время запрета, которое могло бы быть одинаковым с текущим временем запрета. Поэтому создается экземпляр объекта CliqueInfo, хранищего текущую клику и текущее время:

if (history.Contains(cliqueInfo.GetHashCode())) {
  CliqueInfo ci = (CliqueInfo)history[cliqueInfo.GetHashCode
  int intervalSinceLastVisit = time - ci.LastSeen;
  ci.LastSeen = time;
  if (intervalSinceLastVisit < 2 * graph.NumberNodes - 1) {
    timeProhibitChanged = time;
    if (prohibitPeriod + 1 < 2 * bestSize) return prohibitPeriod + 1;
    else return 2 * bestSize;
  }
}
else history.Add(cliqueInfo.GetHashCode(), cliqueInfo);
...

Код проверяет, встречалось ли текущее решение (в виде объекта CliqueInfo) ранее, т. е. находится ли клика в хеш-таблице history? Если текущая клика уже встречалась, алгоритм вычисляет, сколько времени прошло с момента, когда эта клика уже была найдена. Если интервал достаточно короток, время запрета увеличивается (но не более верхней границы). Идея в том, что, поскольку времени с момента последнего обнаружения текущей клики прошло не очень много, алгоритм генерирует дубликатные решения. Если время запрета увеличивается, появится больше запрещенных узлов и соответственно меньше разрешенных, что снизит вероятность генерации дубликатных решений. Если текущее решение не встречалось, оно добавляется в хеш-таблицу history.

«Достаточно короткий» интервал — это число узлов, помноженное на два, минус один. Он используется для определения того, когда увеличиваться время запрета. Здесь его лучшее значение является еще одним открытым вопросом в исследованиях задач о максимальной клике. «Верхний предел» для времени запрета в два раза больше размера текущего лучшего из известных решений. Лучшее значение верхнего предела — это, как вы теперь, вероятно, догадываетесь, еще один открытый вопрос, подлежащий исследованию.

В этот момент либо текущая клика еще не встречалась, либо все же встречалась, но интервал, необходимый для увеличения времени запрета, не был достаточно малым. Поэтому алгоритм теперь проверяет, можно ли уменьшить период запрета, что уменьшит количество запрещенных улов и соответственно увеличит число разрешенных, а это в свою очередь предоставит алгоритму больше узлов для добавления или удаления:

...
  if (time - timeProhibitChanged > 10 * bestSize) {
    timeProhibitChanged = time;
    if (prohibitPeriod - 1 > 1)
      return prohibitPeriod - 1;
    else
      return 1;
  }
  else {
    return result; // нет изменений
  }
} // UpdateProhibitTime

Вместо того чтобы явно проверять, прошло ли «относительно много» времени с того момента, когда текущая клика уже встречалась, алгоритм неявно проверяет, сколько времени прошло с момента предыдущего нахождения текущей клики, анализируя время, в которое последний раз изменялся период запрета. И вновь лучшее значение для «относительно много» не совсем понятно. Я использовал значение, десятикратно превышающее размер текущего лучшего решения. Заметьте, что время запрета нельзя уменьшать ниже 1.

Дополнительные исследования

Данные исследований по задаче о максимальной клике предполагают, что жадный алгоритм с функционалом адаптивного запрещенного поиска дает, в целом, лучшие результаты, если принимать во внимание как производительность, так и качество решения. DIMACS является исследовательской организацией, которая создала набор трудных эталонных задач для поиска максимальной клики в графах. Я прогнал представленный здесь код применительно к одной из трудных задач DIMACS (C2000.9), и он быстро (менее чем за две секунды) нашел клику размеров в 76 узлов, что всего на 1,5% отстает от размера лучшего известного решения, равного 77.

В этой статье я несколько раз упоминал о результатах исследований задачи о максимальной клике. Если вас интересуют эти исследования, советую поискать в Интернете академические статьи следующих авторов: R. Battiti et al., W. Pullan et al. и K. Katayama et al (et al означает «с сотрудниками»). Несколько статей этих трех авторов и их коллег послужили мне основными источниками.

Многообещающая неисследованная область в алгоритме нахождения максимальной клики, представленном здесь, — включение какой-то формы поиска плато (plateau search). Вспомните, что алгоритм нахождения максимальной клики сначала пытается добавить незапрещенный узел в текущее решение. Затем, если это невозможно, алгоритм удаляет какой-нибудь узел из текущего решения. Идея поиска плато в том, чтобы найти один узел в текущем решении, который можно обменять с узлом, не находящимся в клике. Хотя это не увеличивает размер текущей клики, но и не уменьшает его.

Джеймс Маккафри (Dr. James McCaffrey) — работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Полу Коху (Paul Koch), Дэну Либлингу (Dan Liebling), Энн Лумис Томпсон (Ann Loomis Thompson) и Шейну Уильямсу (Shane Williams).