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

Бадер и др. [1] представили первый алгоритм с линейным временем выполнения в худшем случае для вычисления расстояния обращения; это простой и практичный алгоритм, работающий быстрее по сравнению с ранее использовавшимися методами. Ключевым новшеством этого алгоритма является новая техника вычисления связных компонент графа перекрытий, использующая только стек, что позволило создать простой алгоритм с линейный временем выполнения для вычисления расстояния инверсии между двумя подписанными перестановками. Бадер и коллеги представили обширные экспериментальные свидетельства эффективности данного алгоритма не только в теории, но и на практике. Они реализовали его наряду с алгоритмом Бермана и Ханненхалли, используя передовые принципы разработки алгоритмов, гарантирующие максимально возможную эффективность обеих реализаций, и сравнили время выполнения на широком спектре экземпляров данных, сгенерированных посредством имитационной эволюции.

Бафна и Певзнер представили граф циклов для перестановки [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, этот алгоритм не пытается сохранить определенные параметры формы деревьев. Данный шаг является ключевым элементом алгоритма Бадера с линейным временем выполнения для вычисления расстояния инверсии между подписанными перестановками.