• Статья

Ноябрь 2011

Том 26 НОМЕР 11

Алгоритмы - Жадные алгоритмы и максимальная клика

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

Исходный код можно скачать по ссылке.

Джеймс Маккафри

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

 

Граф для решения задачи максимальной клики жадным алгоритмом
Рис. 1. Граф для решения задачи максимальной клики жадным алгоритмом

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

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

Демонстрация жадного алгоритма для решения задачи максимальной клики
Рис. 2. Демонстрация жадного алгоритма для решения задачи максимальной клики

У меня есть консольное приложение, которое начинает с загрузки в память графа, соответствующего показанному на рис. 1. Проектирование и кодирование эффективной структуры данных графа — важная задача сама по себе. Я объяснял код структуры данных графа в прошлой статье из этой рубрики. Алгоритм сначала выбирает случайным образом один узел (в данном случае — узел 2) и инициализирует клику с этим узлом. Затем алгоритм ищет лучший узел для добавления в клику. Если вы обратитесь к рис. 1, то увидите, что клику большего размера образуют все два узла — 4 и 5. Вскоре я поясню, что означает понятие «лучший узел».

Алгоритм выбирает и добавляет узел 4 в клику, поэтому теперь она представляет собой {2, 4}. В этот момент в графе всего один узел (5), который увеличит размер клики, так что алгоритм выбирает узел 5 и добавляет его в клику. После этого нет никаких узлов, которые увеличили бы размер клики. Алгоритм выкидывает лучший узел из клики в надежде, что можно добавить новый другой узел и это позволит продвинуться дальше. Алгоритм удаляет из клики узел 4. Как видно по графу, способа продвинуться дальше нет. Эта ситуация довольно распространенная в жадных алгоритмах, поэтому должен быть предусмотрен способ выхода из тупиковых решений.

Алгоритм отслеживает, сколько времени прошло с момента последнего продвижения, т. е. нахождения клики большего размера. По истечении определенного времени в отсутствие продвижения алгоритм перезапускает сам себя. Клика очищается. На этот раз алгоритм случайным образом выбирает узел 3 в качестве начального. Используя тот же итеративный процесс для нахождения лучшего узла, подлежащего добавлению или удалению, алгоритм в конечном счете обнаруживает максимальную клику {0, 1, 3, 4}. В большинстве задач, где применяются жадные алгоритмы, оптимальное решение не известно, поэтому алгоритм продолжает работу, пока не встретит какое-то условие, прекращающее его выполнение. В данном случае алгоритм настроен на прекращение после 20 итераций. В этот момент отображается лучшая найденная клика.

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

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

Общая структура программы с рис. 2 представлена на рис. 3. Программа имеет зависимости от пространств имен System, System.Collections.Generic (клика представлена типом List<int>), System.IO (для загрузки исходного графа из текстового файла) и System.Collections (определенный в программе класс MyGraph использует класс BitArray). Я переименовал класс Program, сгенерированный шаблоном Visual Studio, в в более описательный GreedyMaxCliqueProgram. Я использую объект Random с именем random на уровне класса для инициализации клики случайным узлом и ее сброса, а также для разрыва связей, когда имеется более одного лучшего узла для добавления или удаления.

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

using System;
using System.Collections.Generic;
using System.IO;
using System.Collections;
 
namespace GreedyMaxClique
{
  class GreedyMaxCliqueProgram
  {
    static Random random = null;

    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine(
          "\nBegin greedy maximum clique demo\n");

        string graphFile = "..\\..\\DimacsGraph.clq";
        Console.WriteLine("Loading graph into memory");
        Console.WriteLine("Graph loaded and validated\n");
        MyGraph graph = new MyGraph(graphFile, "DIMACS");

        int maxTime = 20;
        int targetCliqueSize = graph.NumberNodes;

        List<int> maxClique = FindMaxClique(graph, maxTime,
          targetCliqueSize);
        Console.WriteLine("\nMaximum time reached");
        Console.WriteLine("\nSize of best clique found = " +
          maxClique.Count);

        Console.WriteLine("\nBest clique found:");
        Console.WriteLine(ListAsString(maxClique));

        Console.WriteLine(
          "\nEnd greedy maximum clique demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    } // Main

    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> possibleAdd)
    {
      // ...
    }

    static int GetNodeToDrop(MyGraph graph, List<int> clique,
      List<int> oneMissing)
    {
      // ...
    }

    static List<int> MakeOneMissing(MyGraph graph,
      List<int> clique)
    {
      // ...
    }

    static string ListAsString(List<int> list)
    {
      // ...
    }
  } // класс Program

  public class MyGraph
  {
    // ...
  }
} // ns

Граф представлен определенным в программе объектом MyGraph. Он загружается из внешнего текстового файла со стандартным форматом DIMACS. Ключевой метод в MyGraph — AreAdjacent, который возвращает true, если два узла соединены. Я присвоил maxTime значение 20, чтобы задать абсолютное условие прекращения работы жадного алгоритма. Значение targetCliqueSize указывает второе условие прекращения; если найдена клика, имеющая то же количество узлов, что и в самом графе, значит, это максимальная клика.

Метод FindMaxClique

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

Алгоритм FindMaxClique в высокоуровневом псевдокоде выглядит так:

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

  Если нет продвижения
    Перезапускаем алгоритм

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

Определение метода 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 — это счетчик цикла; поскольку ее значения дискретны, хорошее альтернативное имя этой переменной было бы tick. Я отслеживаю время, когда была найдена текущая лучшая клика, и время последнего перезапуска, чтобы контролировать момент, в который произойдет очередной перезапуск. Переменным для добавления и удаления узла я присваиваю фиктивные значения –1:

int randomNode = random.Next(0, graph.NumberNodes);
Console.WriteLine("Adding node " + randomNode);
clique.Add(randomNode);
...

Метод Random.Next(x,y) возвращает значение, большее или равное x и меньшее y. Задавая x = 0 и y = NumberNodes, я получаю случайный узел от 0 до 8 включительно (для графа-примера):

List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...

Список bestClique используется для отслеживания копии самой большой клики, найденной при поиске алгоритмом. Я применяю удобный метод AddRange для копирования элементов из текущей клики в bestClique. Переменная bestSize служит для удобства. Переменная timeBestClique позволяет определить, произойдет ли перезапуск алгоритма:

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

Вспомогательный метод MakePossibleAdd анализирует текущую клику и конструирует список всех узлов, которые могут быть добавлены в клику для увеличения размера клики на 1. Этот список является источником кандидатов на лучший узел для добавления в клику. Вспомогательный метод MakeOneMissing не столь прост. Он формирует список всех узлов, которые соединены со всеми другими узлами, кроме одного узла в текущей клике. Как вы увидите, этот список oneMissing используется для определения лучшего узла, который следует удалить из клики. Далее я начинаю основной цикл обработки:

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

Как я уже пояснял, жадным алгоритмам, как правило, требуется одно или более условий прекращения. Здесь цикл завершается, если превышено максимальное количество итераций или если размер текущей клики соответствует целевому. Переменная cliqueChanged служит для управления ветвлением логики между добавлением узлов и их удалением. Я мог бы опустить эту переменную и использовать управляющую конструкцию if-else вместо отдельных выражений if-then, но в данном случае переменная, управляющая ветвлением, по моему мнению, облегчает чтение и модификацию кода:

if (possibleAdd.Count > 0) {
  nodeToAdd = GetNodeToAdd(graph, possibleAdd);
  Console.WriteLine("Adding node " + nodeToAdd);
  clique.Add(nodeToAdd);
  clique.Sort();
  cliqueChanged = true;
  if (clique.Count > bestSize) {
    bestSize = clique.Count;
    bestClique.Clear();
    bestClique.AddRange(clique);
  }
} // добавление
...

Я проверяю, что есть хотя бы один узел, который можно добавить в клику, а затем вызываю вспомогательный метод GetNodeToAdd. Этот метод сканирует список узлов в possibleAdd и возвращает лучший узел для добавления (давно обещанное объяснение понятия «лучший» будет дано при описании GetNodeToAdd). Возвращенный узел добавляется в текущую клику. В этот момент я сортирую клику, поскольку позднее в алгоритме мне понадобится поиск по клике: если она отсортирована, можно задействовать быстрый бинарный поиск вместо линейного. Новая клика проверяется на предмет того, лучше (больше) ли она текущей лучшей клики.

Затем выполняется следующее:

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
    Console.WriteLine("Dropping node " + nodeToDrop);
    clique.Remove(nodeToDrop);
    clique.Sort();
    cliqueChanged = true;
  }
} // удаление
...

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

int restart = 2 * bestSize;
if (time - timeBestCliqueFound > restart &&
  time - timeLastRestart > restart) {
    Console.WriteLine("\nRestarting\n");
    timeLastRestart = time;
    int seedNode = random.Next(0, graph.NumberNodes);
    clique.Clear();
    Console.WriteLine("Adding node " + seedNode);
    clique.Add(seedNode);
  } // перезапуск
...

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

...
    possibleAdd = MakePossibleAdd(graph, clique);
    oneMissing = MakeOneMissing(graph, clique);
  } // цикл
  return bestClique;
}

Метод FindMaxClique заново вычисляет списки possibleAdd и oneMissing на основе новой клики. Когда основной цикл обработки завершается, этот метод возвращает лучшую найденную клику.

Добавление лучшего узла

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

static List<int> MakePossibleAdd(MyGraph graph,
  List<int> clique)
{
  List<int> result = new List<int>();
  for (int i = 0; i < graph.NumberNodes; ++i) {
    if (FormsALargerClique(graph, clique, i) == true)
      result.Add(i);
  }
  return result;
}

Метод MakePossibleAdd сканирует каждый узел в графе. Если анализируемый узел соединен со всеми узлами в текущей клике (определяется вспомогательным методом FormsALargerClique), то узел рассматривается как возможный кандидат на добавление и включается в список результатов. Заметьте, что результатом может быть пустой список, но он никогда не равен null:

static bool FormsALargerClique(MyGraph graph,
  List<int> clique, int node)
{
  for (int i = 0; i < clique.Count; ++i) {
    if (graph.AreAdjacent(clique[i], node) == false)
      return false;
  }
  return true;
}

Метод FormsALargerClique сравнивает один узел со всеми узлами в текущей клике. Если узел-кандидат не является смежным хотя бы с одним из узлов в клике, тогда его нельзя добавить в текущую клику. Заметьте: поскольку AreAdjacent возвращает false, когда узел сравнивается сам с собой, узлы в текущей клике не будут добавляться в список узлов possibleAdd.

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

Далее выполняется следующее:

static int GetNodeToAdd(MyGraph graph, List<int> possibleAdd)
{
  if (possibleAdd.Count == 1)
    return possibleAdd[0];
...

Метод GetNodeToAdd предполагает, что в списке possibleAdd есть хотя бы один узел. Если в нем ровно один узел, он и является лучшим:

int maxDegree = 0;
for (int i = 0; i < possibleAdd.Count; ++i) {
  int currNode = possibleAdd[i];
  int degreeOfCurrentNode = 0;
  for (int j = 0; j < possibleAdd.Count; ++j) {
    int otherNode = possibleAdd[j];
    if (graph.AreAdjacent(currNode, otherNode) == true)
      ++degreeOfCurrentNode;
  }
  if (degreeOfCurrentNode > maxDegree)
    maxDegree = degreeOfCurrentNode;
}
...

В списке possibleAdd могло бы быть несколько узлов, которые связаны с другими как имеющие наибольшее количество соединений с прочими узлами в списке. Допустим, что анализируемый граф — тот, что изображен на рис. 1, и что в текущей клике есть только узел 0. Узлы possibleAdd — {1, 3, 4}. Узел 1 соединен с двумя из узлов в possibleAdd, а значит, с узлами 3 и 4. Поэтому для определения максимального количества доступных соединений выполняется предварительное сканирование:

List<int> candidates = new List<int>();
for (int i = 0; i < possibleAdd.Count; ++i) {
  int currNode = possibleAdd[i];
  int degreeOfCurrentNode = 0;
  for (int j = 0; j < possibleAdd.Count; ++j) {
    int otherNode = possibleAdd[j];
    if (graph.AreAdjacent(currNode, otherNode) == true)
      ++degreeOfCurrentNode;
  }
  if (degreeOfCurrentNode == maxDegree)
    candidates.Add(currNode);
}
...

Как только становится известным максимальное количество соединений, алгоритм повторяет сканирование списка possibleAdd и добавляет каждый из улов в possibleAdd, имеющих максимальное количество соединений, в список узлов-кандидатов. Заметьте, что двойное сканирование можно было бы исключить, используя дополнительные хранилища данных для отслеживания числа соединений у каждого узла в possibleAdd:

...
  return candidates[random.Next(0, candidates.Count)];
}

К этому моменту в списке кандидатов есть один или более лучших узлов для добавления в клику. Кандидаты должны иметь значение счетчика не менее единицы, так как предполагается, что в списке possibleAdd присутствует хотя бы один узел. Алгоритм случайным образом выбирает один из узлов-кандидатов и возвращает его. Я мог бы поместить здесь проверку на предмет того, содержит ли список кандидатов равно один узел, и, если да, возвращать в candidates единственный узел.

Удаление лучшего узла

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

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

Метод MakeOneMissing представлен на рис. 4. Он сканирует каждый узел в графе. Идея в том, чтобы подсчитать, сколько узлов в клике соединены с текущим анализируемым узлом. Если общее количество соединенных узлов ровно на 1 меньше размера текущей клики, значит, анализируемый узел относится к списку oneMissing. Работа метода сокращается, если текущий анализируемый узел имеет меньшее необходимого число соседей. Этот метод должен отфильтровывать узлы, уже находящиеся в клике, так как они соединены со всеми, кроме одного узла в своей клике (т. е. самих себя). Поскольку текущая клика сортируется (после каждого добавления или удаления), вместо медленного линейного поиска можно применять быстрый бинарный поиск (см. рис. 4).

Рис. 4. Создание списка узлов oneMissing

static List<int> MakeOneMissing(
  MyGraph graph, List<int> clique)
{
  int count;
  List<int> result = new List<int>();
  for (int i = 0; i < graph.NumberNodes; ++i) {
    count = 0;
    if (graph.NumberNeighbors(i) < clique.Count - 1) continue;
    if (clique.BinarySearch(i) >= 0) continue;
    for (int j = 0; j < clique.Count; ++j) {
      if (graph.AreAdjacent(i, clique[j]))
        ++count;
    }
    if (count == clique.Count - 1)
      result.Add(i);
  }
  return result;
}

Метод GetNodeToDrop начинает с:

static int GetNodeToDrop(MyGraph graph, List<int> clique,
  List<int> oneMissing)
{
  if (clique.Count == 1)
    return clique[0];
...

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

int maxCount = 0;
for (int i = 0; i < clique.Count; ++i) {
  int currCliqueNode = clique[i];
  int countNotAdjacent = 0;
  for (int j = 0; j < oneMissing.Count; ++j) {
    int currOneMissingNode = oneMissing[j];
    if (graph.AreAdjacent(currCliqueNode,
      currOneMissingNode) == false)
        ++countNotAdjacent;
  }
  if (countNotAdjacent > maxCount)
    maxCount = countNotAdjacent;
}
...

Как только становится известным максимальное количество размыканий (disconnections), метод повторяет сканирование клики, чтобы найти эти имеющие минимальное число соединений узлы и добавить каждый из них в список кандидатов. Как и в случае метода GetNodeToAdd, GetNodeToDrop мог бы избежать повторного сканирования, поддерживая дополнительные хранилища данных:

List<int> candidates = new List<int>();
for (int i = 0; i < clique.Count; ++i) {
  int currCliqueNode = clique[i];
  int countNotAdjacent = 0;
  for (int j = 0; j < oneMissing.Count; ++j) {
    int currOneMissingNode = oneMissing[j];
    if (graph.AreAdjacent(currCliqueNode,
      currOneMissingNode) == false)
        ++countNotAdjacent;
  }
  if (countNotAdjacent == maxCount)
    candidates.Add(currCliqueNode);
}
...

Метод GetNodeToDrop завершается возвратом случайно выбранного узла из списка лучших узлов для удаления:

...
  return candidates[random.Next(0, candidates.Count)];
} // GetNodeToDrop

Заключительные соображения

Насколько эффективны жадные алгоритмы? Несмотря на их относительную простоту, жадные алгоритмы оказываются весьма эффективными во многих задачах. Однако эффективность может определяться по нескольким критериям, в том числе по скорости нахождения решения и его качеству. Я выполнял этот алгоритм в нескольких крайне трудных эталонных задачах, связанных с графами и поддерживаемых исследовательской организацией DIMACS, и данный алгоритм был вполне эффективным, работая быстро и создавая максимальные клики, которые в целом укладывались в пределы 5% лучших известных решений.

Тестирование жадных алгоритмов может оказаться дело весьма хитрым. В дополнение ко всем обычным методам тестирования, таким как модульное тестирование, тестирование в пограничных условиях (boundary-condition testing) и т. д., и из-за того, что жадные алгоритмы дают со временем все больше решений, эффективная стратегия тестирования — написание вспомогательных методов, итеративно проверяющих состояние структур данных, используемых алгоритмом. Например, тестируя алгоритм максимальной клики, представленный здесь, я написал методы, которые проверяют отсутствие дублирующихся узлов в текущей клике, удостоверяются в том, что ни один узел в текущей клике не присутствует в текущем списке possibleAdd или oneMissing, и т. п.

Жадный алгоритм максимальной клики, рассмотренный здесь, можно модифицировать в нескольких отношениях для получения более качественных результатов. Один из методов, распространенных в большинстве жадных алгоритмов, — добавление так называемого функционала запрета (tabu feature). Алгоритмы с поддержкой запрета (tabu algorithms) ведут список недавно использовавшихся данных и, возможно, список недавно появлявшихся решений. Данные в списке запрета (tabu list) не используются для конструирования новых решений. Кроме того, жадные алгоритмы зачастую применяют стратегию, называемую поиском плато (plateau search). Когда жадный алгоритм не в состоянии улучшить свое текущее решение, поиск плато дает новое решение без возврата назад, такого как удаление узла в задаче максимальной клики. Я расскажу об этих интересных и полезных методах в следующем выпуске этой рубрики.

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

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