Раскраска графов с помощью простого поиска с возвратом. Часть 3

Article
10/07/2010

Итак, у нас готовы базовые структуры данных.

Раскраска графа – это очень хорошо изученная задача. Известно, что это NP-полная задача для произвольных графов, так что (предполагая, что P != NP) мы не стремимся находить эффективный алгоритм для раскрашивания произвольного графа. Однако, для типовых графов, с которыми мы сталкиваемся в реальной жизни, следующий простой алгоритм вполне подходит. Начинается он с того, что мы предполагаем, что каждый узел может быть каждого возможного цвета. Затем:

Если мы имеем один возможный цвет для каждого узла графа, то работа алгоритма успешно завершена!
Если у нас есть хотя бы один узел, которому не подходит ни один цвет, то работа алгоритма завершилась неудачно!
В противном случае, у нас должен быть узел, как минимум с двумя возможными цветами.
У некоторых узлов может быть только один возможный цвет, тогда этот цвет нужно удалить из списка возможных цветов его соседних узлов.
Эта операция может привести к тому, что у соседей может остаться только один единственный цвет. Если это так, то нужно удалить эти цвета из возможных цветов соседних узлов.
И так далее; нужно продолжать уменьшать количество возможных вариантов до тех, пока это будет возможно.
Если количество возможных цветов уменьшено, то мы либо получили решение, либо его вообще нет. Возвращаемся к шагу 1.
В противном случае количество возможных вариантов не уменьшено и у нас есть узел с двумя или более возможными цветами. Выберем один возможный цвет для этого узла.
Применяем рекурсию; если следующая итерация рекурсии приводит к успеху, все, мы справились. Если следующая итерация приводит к неудаче, тогда наше гипотетическое предположение не сработало.
Если у нас есть еще неопробованный гипотетический цвет для этого узла, возвращаемся к шагу 8 и пробуем выбрать другой цвет.
В противном случае ни один из вариантов для этого «неопределенного» узла не подходит; алгоритм завершился неудачно.

Обратите внимание, что это, по сути, алгоритм перебора с возвратами (“backtracking” algorithm). Мы делаем предположение, и если наше предположение оправдывается, то хорошо, мы справились. Если ни одно предположение не оправдывается, тогда либо задача не решаема (например, мы пытаемся раскрасить карту Южной Америки тремя цветами) или предыдущее предположение неверно, так что нужно возвращаться на один шаг ранее. Мы продолжаем выполнение алгоритма до тех, пока мы не перепробуем все возможные варианты.

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

Как мы собираемся это реализовывать? Помните, что моя цель здесь создать программу, более легкую для понимания путем использования по возможности неизменяемых структур данных, но не настолько неизменяемых, чтобы это привело к снижению производительности или к созданию странного кода.

Мы создадим класс Solver, которые представляет набор возможных цветов для каждого узла. Объект класса Solver неизменяемый; когда нам нужно сделать некоторое предположение или заключение, которое изменяет возможные цвета для этого узла, мы будем создавать новый solver вместо существующего. Давайте создадим solver, который будет пытаться предоставить решение для n цветов определенного графа:

 internal sealed class Solver
{
   private enum Result { Solved, Unsolved, Busted }
   private readonly Graph graph;
   private readonly BitSet[] possibilities;
   private readonly int colours;
   public Solver(Graph graph, int colours)
   {
       this.colours = colours;
       this.graph = graph;
       this.possibilities = new BitSet[graph.Size];
       BitSet b = BitSet.Empty;
       for (int i = 0; i < colours; ++i)
           b = b.Add(i);
       for (int p = 0; p < this.possibilities.Length; ++p)
           this.possibilities[p] = b;
    }

}

Пока что достаточно просто. Класс является внутренним и закрытым; мы не предполагаем, что кто-либо будет от него наследовать или использовать его за пределами сборки. Позднее мы собираемся реализовать первые несколько строк алгоритма, получив ответ на вопрос: «Мы нашли решение, решения нет или нам нужно проделать дополнительную работу?». Ответ на этот вопрос я возвращаю с помощью перечисления. Этот класс хранит граф, количество цветов, которое он будет использовать для раскраски графа и битовый набор возможных цветов для каждого узла. Набор возможных цветов для каждого узла представляет собой массив; как мы увидим позднее, использование изменяемой структуры данных в этом случае имеет свои преимущества и недостатки.

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

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

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

 private Solver(Graph graph, int colours, BitSet[] possibilities)
    {
        this.graph = graph;
        this.colours = colours;
        this.possibilities = possibilities;
    }

У нас должна быть возможность создать новый объект solver с единственным цветом, взятым из набора возможных цветов.

 // Создать новый solver с одним известным цветом.
public Solver SetColour(int node, int colour)
    {
        BitSet[] newPossibilities = (BitSet[])this.possibilities.Clone();
        newPossibilities[node] = BitSet.Empty.Add(colour);
        return new Solver(this.graph, this.colours, newPossibilities);
    }

Теперь мы можем увидеть преимущества и недостатки использования массива битовых массивов. BitSet был спроектирован маленьким и легковесным значимым типом, который является всего лишь оболочкой над int. Операция копирования битового массива – тривиальна; мы просто копируем int. Однако копирование массива с последующим его изменением – это более дорогая операция; мы копируем все целиком. Если эти массивы будут большого размера, то эта операция будет чрезвычайно неэффективной; каждый раз при создании нового объекта Solver по предыдущему мы получим огромное количество дублируемой информации, поскольку различия между ними в некоторых случаях будут заключаться всего в одном бите, что кажется напрасной тратой ресурсов. В таком случае вместо использования массива битовых массивов, я бы использовал что-то вроде неизменяемых коллекций битовых массивов, которые бы позволяли мне использовать повторно большую часть данных при внесении изменений. Но это значительно увеличило бы сложность, и, честно говоря, копирование небольших массивов выполняется очень быстро, а у нас массивы не такие уж и большие. Так что, предполагая, что размеры графов будут небольшими, мы остановимся на решении на основе массивов.

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

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

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

 private Result Status
{
   get
   {
       if (possibilities.Any(p => !p.Any()))
           return Result.Busted;
       if (possibilities.All(p => p.Count() == 1))
           return Result.Solved;
       return Result.Unsolved;
   }
}

Пусть простота этого кода не вводит вас в заблуждение; здесь присутствует несколько интересных проектных решения. Во-первых, мы говорим, что если есть хотя бы один узел, который не содержит ни одного возможного цвета, значит решения нет. Я решил сделать это по-умному, и возможно это неправильно. Я не люблю умный код, я люблю код, который легко читать, а этот код становится несколько запутанным. Кажется, что вложенный вызов метода Any определяет «есть ли хотя бы один пустой член в коллекции возможных цветов?», что читается весьма сложно. Я специально хотел избежать использования циклов, чтобы сделать код более декларативным и менее императивным, но здесь, кажется, я зашел слишком далеко.

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

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

 private Result Status
{
    get
    {
        foreach(var p in possibilities)
        {
            int primitiveCount = p.ZeroOneOrMany();
            if (primitiveCount == 0) return Result.Busted;
            if (primitiveCount > 1) return Result.Unsolved;
        }
        return Result.Solved;
    }
}

И затем написать метод расширения ZeroOneOrMany() который определит количество только для первых двух элементов последовательности.

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

Также обратите внимание на то, что я не кэширую результаты; вполне возможно, что Solver вызовет это свойство несколько раз, и мы будем каждый раз вычислять заново его значение. Здесь мы сталкиваемся с компромиссом между дополнительным расходом памяти и избыточности, в обмен на более высокую производительность. Но возможен ли на самом деле сценарий, при котором один и тот же объект будет несколько раз запрашивать значение статуса? Я так не думаю, так что опять, YAGNI. Давайте не вводить дополнительную сложность, которой мы не собираемся пользоваться, во всяком случае, без явных на это причин.

Основные операции этого алгоритма состоят из двух этапов. Вначале, мы делаем все заключения, которые мы можем тривиально сделать без каких-либо предположений, а затем делаем предположения. Как мы будем делать это? Опять-таки, существует противоречие между простым решением, которое заключается в изменении массива и более чистом, но более сложном решении, которое заключается в создании неизменяемого ассоциативного массива узлов и возможных цветов, и последующем изменении ассоциативного массива путем создания нового экземпляра на основе существующего. Мы инкапсулируем решение на основе изменяемой коллекции в качестве детали реализации метода Reduce. Идея решения заключается в том, что метод Reduce возвращает либо null, если уменьшить количество возможных цветов невозможно, или новый неизменяемый экземпляр класса Solver с уменьшенным количеством возможных цветов.

 private Solver Reduce()
{
    BitSet[] newPossibilities = (BitSet[])this.possibilities.Clone();
// Запрос отвечает на следующий вопрос: «Какие возможные цвета я должен удалить?» 
    var reductions =
        from node in Enumerable.Range(0, newPossibilities.Length)
        where newPossibilities[node].Count() == 1
        let colour = newPossibilities[node].Single()
        from neighbour in graph.Neighbours(node)
        where newPossibilities[neighbour].Contains(colour)
        select new { neighbour, colour };
     bool progress = false;
     while(true)
     {
         var list = reductions.ToList();
         if (list.Count == 0)
             break;
         progress = true;
         foreach (var reduction in list)
             newPossibilities[reduction.neighbour] = newPossibilities[reduction.neighbour].Remove(reduction.colour);
// Это может привести к созданию нового узла, только с одним возможным цветом,
// который можно использовать для дальнейшего уменьшения возможных цветов соседних узлов. 
// Продолжаем выполнение цикла до тех пор, пока не останется больше возможных цветов, которые можно удалить.
     }
     return progress ? new Solver(graph, colours, newPossibilities) : null;
}

Здесь нужно обратить внимание на несколько моментов.

Я хочу избежать ситуации, при которой мы изменяем объект, по которому выполняем итерирование. В принципе, нам это может сойти с рук в данном случае; мы можем запустить запрос и изменить массив во время выполнения запроса. Но это плохое решение, которое впоследствии будет сложно изменить, в зависимости от того решим ли мы использовать изменяемую или неизменяемую коллекцию для представления возможных цветов. Вместо этого я выполняю запрос один раз, кэширую результаты и перебираю элементы уже этого списка.

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

С другой стороны, я использую List.Count вместо метода расширения Any(), поскольку знаю, что вызов List.Count обходится дешевле вызова метода Any().

Обычно, вызов метода расширения Any() обходится дешевле вызова Count(), поскольку вычисление количества элементов коллекции может включать перебор всех ее элементов, в то время как Any потребуется один вызов метода MoveNext.

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

Обычно я не являюсь большим поклонником использования нулевых ссылок для сигнализации выполнения некоторого условия, но в этом случае это оправдано. А какие альтернативы? Возвращать пару значений (bool, Solver), которая будет говорить о том, был ли прогресс или нет? Такое решение выглядит странным. Этот вопрос более интересен в следующем фрагменте кода.

Что приводит нас к самому алгоритму решения:

 public IEnumerable<int> Solve()
{
// Базовый случай: мы либо нашли решение, либо нет.
    var status = this.Status;
    if (status == Result.Solved)
         return this.possibilities.Select(x => x.Single());
    if (status == Result.Busted)
         return null;
// Простой случай: уменьшаем количество возможных цветов и пытаемся решить заново.
    var reduced = Reduce();
    if (reduced != null)
        return reduced.Solve();
// Сложный случай: простое уменьшение не подходит.
// Делаем предположение о цвете узла и смотрим, 
// приведет ли оно к решению или нет.
    int node = this.possibilities.FirstIndex(p => p.Count() > 1);
    var solutions =
        from colour in this.possibilities[node]
        let solution = this.SetColour(node, colour).Solve()
        where solution != null
        select solution;
    return solutions.FirstOrDefault();
}

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

 public static int FirstIndex<T>(this IEnumerable<T> items, Func<T, bool> predicate)
{
    int i = 0;
    foreach (T item in items)
    {
       if (predicate(item))
       return i;
       i++;
    }
    throw new Exception();
}

Обратите внимание, что этот метод требует, чтобы хотя бы один элемент удовлетворял предикату! Это может быть не лучшим решением в общем случае, но оно удовлетворяет моим потребностям. Более общее решение может возвращать Nullable<int>.

В любом случае, теперь у нас есть открытый интерфейс класса Solver; он возвращает последовательность цветов для каждого узла, если решение найдено, или null, если такой последовательности не существует. Это демонстрирует важный принцип последовательностей: null и пустая последовательность – это не одно и то же. Null говорит о том, «что такой последовательности нет», а не то о том, «что такая последовательность есть и она пуста».

Хотя я не уверен, что последовательность – это хороший выбор в этом случае. Ведь мы хотим выразить, что существует ассоциация между номером узла и номером цвета. Но как пользователь может спросить «Какой цвет у узла номер 12?» Он ведь не может индексировать последовательность! Вызывающий код почти наверняка вызовет метод ToArray, или ToList, или ToLookup и, возможно, вместо него это разумно сделать нам. С другой стороны, могут быть пользователи, которым нужен массив, или список, или словарь или что-то еще, так что, возможно мы не должны принимать решение за него. Пока что я оставлю все как есть.

Я уже говорил, что для первого рекурсивного случая, рекурсия нам, на самом деле, не нужна. Мы можем переписать первую часть следующим образом:

 public IEnumerable<int> Solve()
{
    var current = this;
    while(true)
    {
        var status = current.Status;
        if (status == Result.Solved)
            return current.possibilities.Select(x => x.Single());
        if (status == Result.Busted)
            return null;
        var reduced = Reduce();
        if (reduced == null)
            break;
        current = reduced;
    }

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

Основной рекурсивный этап интересным образом использует выражение запроса. Мы создаем запрос, который создает последовательность для всех возможных предположений первого узла, который может быть разного цвета. Но нас интересует только «существует ли хотя бы одно решение или нет?» Метод FirstOrDefault вернет первое решение, если такое существует, и вернет null в противном случае. Мы воспользуемся преимуществом отложенного выполнения запросов и не будем вычислять все возможные решения до тех пор, пока не будем перебирать результаты выполнения всего запроса.

Также заметьте, что мы можем модифицировать код таким образом, чтобы получать первые два решения, если они существуют. В таком случае мы сможем сказать, является ли решение уникальным или нет! Но сейчас мы ищем любое решение.

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

Оригинал статьи

Раскраска графов с помощью простого поиска с возвратом. Часть 3

Additional resources