Сортировка перестановок со знаками при помощи обращений (расстояние обращения): различия между версиями

Бафна и Певзнер представили граф циклов для перестановки [3], ставший базовой структурой данных для вычисления расстояния инверсии. После этого Ханненхалли и Певзнер разработали базовую теорию для выражения расстояния инверсии в легко вычисляемых терминах (количество точек разрывов минус количество циклов плюс количество препятствий плюс поправочный коэффициент для укреплений [3, 15] – укрепления и препятствия можно легко обнаружить при помощи анализа связных компонентов). Они также предложили первый алгоритм с полиномиальным временем выполнения для сортировки подписанных перестановок при помощи обращений [9] и <math>O(n^4)</math>-реализацию этого алгоритма, которая в случае ограничения вычисления только расстоянием выполняется за квадратичное время. Этот алгоритм требует вычисления связных компонент графа перекрытий, что является узким местом при вычислении расстояний. Впоследствии Берман и Ханненхалли применили некоторые комбинаторные свойства графа циклов, получив алгоритм с временем выполнения <math>O(n \alpha(n))</math> для вычисления связных компонент и реализацию алгоритма сортировки с временем выполнения <math>O(n^2 \alpha(n))</math> [6], где <math>\alpha</math> – обратная функция Аккермана. (Более поздний алгоритм Каплана, Шамира и Тарьяна (Kaplan-Shamir-Tarjan, KST) [10] сокращает время выполнения, необходимое для вычисления кратчайшей последовательности инверсий, но использует тот же подход для вычисления длины этой последовательности).

Ни один из алгоритмов, строящих граф перекрытий, не может выполняться за линейное время, поскольку этот граф может иметь квадратичный размер. Ключевое новшество Бадера заключается в построении ''леса перекрытий'', такого, что две вершины принадлежат к одному и тому же дереву леса точно в том случае, когда они принадлежат к одной и той же связной компоненте графа перекрытий. Лес перекрытий (композиция его деревьев уникальна, но их структура произвольна) содержит ровно одно дерево для каждой связной компоненты графа перекрытий и в силу этого имеет линейный размер. Шаг алгоритма с линейным временем выполнения, вычисляющий связные компоненты, сканирует перестановку дважды. Первое сканирование строит тривиальный лес, в котором каждая вершина является своим собственным деревом и помечена началом своего цикла. Второй скан выполняет итеративное уточнение этого первичного леса при помощи добавления ребер и слияния таким образом деревьев друг с другом; однако, в отличие от Union-Find, этот алгоритм не пытается сохранить определенные параметры формы деревьев. Данный шаг является ключевым элементом алгоритма Бадера с линейным временем выполнения для вычисления расстояния обращения между подписанными перестановками.