Уточнение разбиения

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

Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на графах и конечных автоматах, включая минимизацию ДКА, алгоритм Коффмана – Грэма для параллельного планирования и лексикографический поиск в ширину.

Структура данных

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

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

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

Чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества X. Для каждого такого элемента x он находит множество S_i которое содержит x, и проверяет, произведено ли пересечение S_i ∩ X. Если нет, он создает второе множество и добавляет S_i в список L множеств, разделенных операцией. Затем, независимо от того, было ли сформировано новое множество, алгоритм удаляет x из S_i и добавляет его к S_i ∩ X В представлении, в котором все элементы хранятся в одном массиве, перемещение x из одного множества в другое может выполняться путем обмена x местами c последним элементом S_i а затем уменьшения концевого индекса S_i и начального индекса нового множества. Наконец, после того, как все элементы X были обработаны таким образом, алгоритм проходит через L, разделяя каждое текущее множество S_i на два, рассматривая оба этих множества как сформированные в результате операции уточнения.

Оценка времени для выполнения одной операции уточнения таким образом составляет O(|X|), независимо от количества элементов в семействе множеств, а также независимо от общего количества множеств в структуре данных. Поэтому время исполнения последовательности уточнений пропорционально общему размеру множеств, заданных алгоритму на каждом этапе уточнения.

Применение

Одно из первых применений уточнение разбиения нашло в алгоритме Хопкрофта для минимизации ДКА. В этой задаче на входе задается детерминированный конечный автомат, и он должен найти эквивалентный автомат с как можно меньшим количеством состояний. Алгоритм Хопкрофта поддерживает разделение состояний входного автомата на подмножества с тем свойством, что любые два состояния в разных подмножествах должны отображаться в разные состояния выходного автомата. Изначально существует два подмножества, одно из которых содержит все принимающие состояния автомата, а другое — остальные. На каждом шаге выбираются одно подмножество S_i и один из входных символов x автомата, и подмножества состояний уточняются до состояний, для которых переход, помеченный x, приведет в S_i, и состояний, для которых x приведет в другое место. Когда выбранное множество S_i разделяется уточнением, только одно из двух результирующих множеств (меньшее из двух) нужно рассмотреть снова; таким образом, каждое состояние участвует в множествах X в течение O(s log n) шагов уточнения, а общая оценка времени алгоритма составляет O(ns log n), где n — количество начальных состояний, а s — размер алфавита.

Уточнение разделения было применено Sethi в эффективной реализации алгоритма Коффмана — Грэма для параллельного планирования. Сетхи показал, что его можно использовать для построения лексикографически упорядоченной топологической сортировки заданного ориентированного ациклического графа за линейное время; такое лексикографическое топологическое упорядочение является одним из ключевых шагов алгоритма Коффмана — Грэма. В этом приложении элементы непересекающихся множеств являются вершинами входного графа, а множества X используемые для уточнения разбиения, являются множествами соседей вершин. Поскольку общее количество соседей всех вершин — это просто количество ребер в графе, алгоритм требует времени, линейного по количеству ребер.

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

См. также

• Уточнение (сигма-алгебра)