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

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

Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на графах и конечных автоматах , включая минимизацию DFA , алгоритм Коффмана – Грэма для параллельного планирования и лексикографический поиск графов в ширину . ^{[1] [2] [3]}

Структура данных [ править ]

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

Такой алгоритм может быть эффективно реализован за счет поддержки структур данных, представляющих следующую информацию: ^{[4] [5]}

• Упорядоченная последовательность наборов S _i в семействе в такой форме, как двусвязный список, который позволяет вставлять новые наборы в середину последовательности.
• Связанный с каждым набором 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 последним элементом S _i, а затем уменьшения конечного индекса S _i и начального индекса нового набор. Наконец, после того, как все элементы X были обработаны таким образом, алгоритм проходит через L , отделяя каждый текущий набор S _i от второго набора, который был отделен от него, и сообщает, что оба этих набора были вновь сформированы в результате уточнения. операция.

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

Приложения [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]