4446
правок
Сортировка перестановок со знаками при помощи обращений (последовательность обращений): различия между версиями
Перейти к навигации
Перейти к поиску
Сортировка перестановок со знаками при помощи обращений (последовательность обращений) (посмотреть исходный код)
Версия от 15:25, 22 февраля 2019
, 22 февраля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
== Основные результаты == | == Основные результаты == | ||
Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле d{n) = n + 1 — с{ж) + фг) (нотация из работы [ ]), где с(ж) – количество циклов в графе разрывов, а фг) вычисляется из неориентированных компонентов перестановки (см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера d(jr): на очередном шаге алгоритма пробовать каждое возможное обращение p, до тех пор, пока не будет найдено такое, что d(ж ■ p) = сфг) - 1. Такое обращение называется безопасным. Этот подход требует O(n) вычислений для каждого возможного обращения (они занимают не более (n + 1)(n + 2)/2 = O(n2)); в результате итераций для поиска последовательности получаем алгоритм со сложностью O(n4). | |||
Первый полиномиальный алгоритм Ханненхалли и Певзнера [9] не мог обеспечить лучшую сложность, и его история началась с алгоритмических исследований процесса поиска кратчайшей последовательности обращений. | |||
'''Сценарий обращений''' | |||
Все опубликованные решения для вычисления последовательности сортировок делятся на две части, следуя разбиению формулы расстояния на два параметра: первый тип решений вычисляет последовательность обращений таким образом, что полученная перестановка не имеет неориентированных компонентов; второй тип сортирует все ориентированные компоненты. | |||
Лучшее решение для первой части предложили Каплан, Шамир и Тарьян [ ]; их алгоритм выполняется за линейное время при сочетании с линейным алгоритмом вычисления расстояния [2], он основан на ранних находках Ханненхалли и Певзнера [ ]. | |||
Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет d(jr) = n + 1 — с(ж), так что безопасным обращением будет являться такое, которое увеличивает с(ж) и не создает неориентированных компонентов (это увеличило бы фг)). | |||
Обращение, увеличивающее фг), называется ориентированным. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что это действие не увеличивает число неориентированных компонентов. | |||
Квадратичные алгоритмы, разработанные, с одной стороны, Берманом и Ханненхалли [ ], а с другой – Капланом, Шамиром и Тарьяном [10], основаны на распознавании безопасных обращений за линейное время. На данный момент не известно улучшенных алгоритмов распознавания безопасных обращений, и представляется, что нижняя граница уже была достигнута, о чем свидетельствуют Озери-Флато и Шамир в работе [14], в которой они сообщили, что «главный вопрос в исследованиях перестановок геномов заключается в том, можно ли получить субквадратичный алгоритм для сортировки при помощи обращений». Этот алгоритм был получен Танье и Сагот [17], которые доказали, что распознавание безопасного обращения на каждом этапе не является необходимым; требуется только распознавание ориентированные обращений. | |||
Алгоритм основан на следующей теореме, приведенной в работе [ ]. Последовательность ориентированных обращений Pi,.: ; , k называется максимальной, если не существует ориентированного обращения в ж • pi • • • k. В частности, последовательность сортировки является максимальной, в то же время обратное неверно. | |||
Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность S0 ориентированных обращений, такая, что S может быть разбита на две части S = S1; S2, и S1; S0; S2 является последовательностью ориентированных обращений. | |||
Это позволяет строить последовательность ориентированных обращений вместо безопасных обращений и увеличивать их размер за счет добавления обращений внутрь последовательности, а не в ее конец, получая последовательность сортировки. | |||
Этот алгоритм, с классической структурой данных для представления перестановок (например, в виде массива), также имеет сложность O(n2), поскольку на каждом этапе он должен провести проверку на наличие ориентированного обращения и применить его к перестановке. | |||
Небольшая модификация структуры данных, предложенная Капланом и Вербином [ ], позволяет выбирать и применять ориентированное обращение за время O(n log n); с ее помощью алгоритм Танье-Сагот достигает временной сложности O(n3/2plog n). | |||
Недавно Хан [8] предложил еще одну структуру данных, позволяющую выбирать и применять ориентированное обращение за время O(pn); аналогичная небольшая модификация, вероятно, поможет снизить сложность алгоритма в целом до O(n3/2). | |||
'''Пространство оптимальных решений''' | |||
Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для n < 10 их может быть несколько миллионов). Лишь несколько исследований попытались восполнить этот пробел. | |||
Алгоритм перечисления всех безопасных обращений на одном этапе был предложен и реализован Сипелем [16]. Структуру пространства оптимальных решений открыли Шаве и др. [ ]; алгоритмические подходы к этой структуре исследовались в работе [6]. | |||
== Применение == | |||