Уточнение раздела

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

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

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

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

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

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

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

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

Приложения

Раннее применение уточнения разделения было в алгоритме Хопкрофта (1971) для минимизации DFA . В этой задаче в качестве входных данных дается детерминированный конечный автомат , и необходимо найти эквивалентный автомат с как можно меньшим количеством состояний. Алгоритм Хопкрофта поддерживает разделение состояний входного автомата на подмножества с тем свойством, что любые два состояния в разных подмножествах должны отображаться в разные состояния выходного автомата. Изначально имеется два подмножества: одно содержит все принимающие состояния автомата, а другое — остальные состояния. На каждом шаге выбираются одно из подмножеств Si _x и один из входных символов x автомата, а подмножества состояний уточняются до состояний, для которых переход, обозначенный , приведет к Si _, и состояний, для которых x - переход приведет куда-то еще. Когда набор S _i , который уже был выбран, разделяется посредством уточнения, только один из двух результирующих наборов (меньший из двух) необходимо выбрать снова; таким образом, каждое состояние участвует в наборах X для O ( s log n ) шагов уточнения, а весь алгоритм занимает время O ( ns log n ) , где n — количество начальных состояний, а s — размер алфавита.

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

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