Быстрый поиск наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
(+картинки +комментарии +пример)
Строка 2: Строка 2:
  
 
{{Задача
 
{{Задача
|definition = Дана {{Acronym | перестановка | на самом деле может быть и мультиперестановкой }} <tex>\pi</tex> <tex>\{1, 2,~\dots,~n\}</tex> Найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> - длина НВП.
+
|definition = Дана {{Acronym | перестановка | на самом деле может быть и мультиперестановкой }} <tex>\pi</tex> <tex>\{1, 2,~\dots,~n\}</tex>. Требуется найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> длина НВП.
 
}}
 
}}
  
 +
[[Файл:Task.jpg]]
 
== Алгоритм <tex>O(n\operatorname{log}\operatorname{log}n)</tex> ==
 
== Алгоритм <tex>O(n\operatorname{log}\operatorname{log}n)</tex> ==
 
=== Нахождение длины НВП ===
 
=== Нахождение длины НВП ===
 
==== Основная идея ====
 
==== Основная идея ====
Пусть <tex>\pi(n)</tex> - входная перестановка.
+
Пусть <tex>\pi(n)</tex> входная перестановка.
  
 
Для каждой длины <tex>l = 1, 2, \dots</tex> предполагаемой НВП находим наименьший {{Acronym | элемент| назовем его лучшим элементом для заданной длины }}, что может быть последним в возрастающей подпоследовательности длины <tex>l</tex>, запишем их в массив <tex>B[l]</tex>.
 
Для каждой длины <tex>l = 1, 2, \dots</tex> предполагаемой НВП находим наименьший {{Acronym | элемент| назовем его лучшим элементом для заданной длины }}, что может быть последним в возрастающей подпоследовательности длины <tex>l</tex>, запишем их в массив <tex>B[l]</tex>.
Строка 17: Строка 18:
  
 
* Если <tex>\pi(i)</tex> больше {{Acronym | <tex>\pi(1), \pi(2),~\dots~,\pi(i-1)</tex> | всех уже полученных значений B }}, значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец <tex>B</tex>
 
* Если <tex>\pi(i)</tex> больше {{Acronym | <tex>\pi(1), \pi(2),~\dots~,\pi(i-1)</tex> | всех уже полученных значений B }}, значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец <tex>B</tex>
* Иначе <tex>\pi(i)</tex> становится лучшим элементом для такой длины <tex>l</tex>, что: {{Acronym | <tex>B[l]</tex> | предыдущее значение}}<tex> = \min \{ B[j] > \pi(i),~j < i \}</tex>  
+
* Иначе <tex>\pi(i)</tex> становится лучшим элементом для такой длины <tex>l</tex>, что: {{Acronym | <tex>B[l]</tex> | предыдущее значение}}<tex> = \min \{ B[1..j] > \pi(i) \}</tex>  
  
Следует отметить, что полученный массив также образует возрастающую последовательность, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени.
+
Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции <tex>insert, next, delete</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени на одну операцию.
 
==== Пример ====
 
==== Пример ====
 
Типы операций:
 
Типы операций:
  
Последовательность:
+
[[Файл:Operation1.jpg]]
 +
 
 +
[[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]]
 +
 
 +
{{Acronym |Последовательность: | именно она будет рассматриваться далее}}
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
|-align="center"
 
|-align="center"
! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex>
+
! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex> || <tex>\pi_{10}</tex> || <tex>\pi_{11}</tex> || <tex>\pi_{12}</tex>
 
|-align="center"
 
|-align="center"
|  9 || 2 || 1 || 3 || 7 || 5 || 6 || 8 || 4
+
|  9 || 3 || 10 || 4 || 8 || 1 || 2 || 12 || 6 || 5 || 7 || 11
 
|}
 
|}
 
Состояние очереди при каждом добавлении:
 
Состояние очереди при каждом добавлении:
Строка 35: Строка 40:
 
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
 
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 9 ||  ||  ||  ||  || style="background:#9886ff"|9
+
| style="background:#FFCC00"| 9 ||  ||  ||  ||  || style="background: #77A9F4"| 9
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 2 ||  ||  ||  ||  || style="background:#9886ff"|2
+
| style="background:#FFCC00"| 3 ||  ||  ||  ||  || style="background: #77A9F4"| 3
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 1 ||  ||  ||  ||  || style="background:#9886ff"|1
+
| 3 || style="background:#FFCC00"| 10 ||  ||  ||  || style="background: #77A9F4"| 10
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"| 3 ||  ||  ||  || style="background:#9886ff"|3
+
| 3 || style="background:#FFCC00"| 4 ||  ||  ||  || style="background: #77A9F4"| 4
 
|-align="center"  
 
|-align="center"  
| 1 || 3 || style="background:#FFCC00"| 7 ||  ||  || style="background:#9886ff"|7
+
| 3 || 4 || style="background:#FFCC00"| 8 ||  ||  || style="background: #77A9F4"| 8
 
|-align="center"  
 
|-align="center"  
| 1 || 3 || style="background:#FFCC00"| 5 ||  ||  || style="background:#9886ff"|5
+
| style="background:#FFCC00"| 1 || 4 || 8 ||  ||  || style="background: #77A9F4"| 1
 
|-align="center"  
 
|-align="center"  
| 1 || 3 || 5 || style="background:#FFCC00"| 6 ||  || style="background:#9886ff"|6
+
| 1 || style="background:#FFCC00"| 2 || 8 ||  ||  || style="background: #77A9F4"| 2
 
|-align="center"  
 
|-align="center"  
| 1 || 3 || 5 || 6 || style="background:#FFCC00"| 8 || style="background:#9886ff"|8
+
| 1 || 2 || 8 || style="background:#FFCC00"| 12 ||  || style="background: #77A9F4"| 12
 
|-align="center"  
 
|-align="center"  
| 1 || 3 || style="background:#FFCC00"| 4 || 6 || 8 || style="background:#9886ff"|4
+
| 1 || 2 || style="background:#FFCC00"| 6 || 12 ||  || style="background: #77A9F4"| 6
 
+
|-align="center"
 +
| 1 || 2 || style="background:#FFCC00"| 5 || 12 ||  || style="background: #77A9F4"| 5
 +
|-align="center"
 +
| 1 || 2 || 5 || style="background:#FFCC00"| 7 ||| style="background: #77A9F4"| 7
 +
|-align="center"
 +
| 1 || 2 || 5 || 7 || style="background:#FFCC00"| 11 || style="background: #77A9F4"| 11
 
|}
 
|}
  
 
==== Псевдокод ====
 
==== Псевдокод ====
 
<code>
 
<code>
     '''function''' LIS(<tex>\pi</tex>[])
+
     '''function''' LIS(<tex>\pi</tex>[]): int
         B = PriorityQueue()
+
         B = PriorityQueue() <font color=darkgreen>// рабочая приоритетная очередь</font>
         k = 0
+
         k = 0 <font color=darkgreen>// длина НВП</font>
 
         n = <tex>\pi</tex>.size
 
         n = <tex>\pi</tex>.size
         '''for''' i = 1..n:
+
         '''for''' i = 1 to n
 
             x = <tex>\pi</tex>[i]
 
             x = <tex>\pi</tex>[i]
             B.insert(x)            // в любом случае добавляем в очередь
+
             <font color=darkgreen>// в любом случае добавляем в очередь очередной элемент</font>
             '''if''' B.next(x) '''exists''' '''then'''
+
            <font color=darkgreen>// устаревшие будем удалять</font>
                 B.delete(B.next(x)) // удаляем предыдущее значение - заменяем {{Acronym | следующий | минимальный из бОльших}}  
+
            B.insert(x)
 +
             '''if''' B.next(x) '''exists'''
 +
                 <font color=darkgreen>// добавленный элемент — не максимальный</font>
 +
                <font color=darkgreen>// удаляем предыдущее значение заменяем {{Acronym |следующий|минимальный из бóльших}}</font>
 +
                B.delete(B.next(x))
 
             '''else'''
 
             '''else'''
                 k = k + 1          // добавляем максимальный - уже добавлен, ничего не удаляем
+
                <font color=darkgreen>// добавленный элемент - максимальный</font>
 +
                <font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font>
 +
                 k = k + 1           
 
         '''return''' k</code>
 
         '''return''' k</code>
  
=== Расширение алгоритма на нахождение НВП ===
+
=== Расширение алгоритма до нахождения НВП ===
 
==== Основная идея ====
 
==== Основная идея ====
 
Будем запоминать пары: для каждого элемента записываем его "предшественника".
 
Будем запоминать пары: для каждого элемента записываем его "предшественника".
  
Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко восстановить все НВП.
+
Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко {{Acronym | восстановить НВП | вообще говоря, не все }}.
 +
==== Общий вид алгоритма ====
 +
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 +
|-align="center"
 +
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
 +
|-align="center"
 +
| 9 ||  ||  ||  ||  || style="background: #77A9F4"| 9
 +
|-align="center"
 +
| 3 ||  ||  ||  ||  || style="background: #77A9F4"| 3
 +
|-align="center"
 +
| 3 || 10 ||  ||  ||  || style="background: #77A9F4"| 10
 +
|-align="center"
 +
| 3 || 4 ||  ||  ||  || style="background: #77A9F4"| 4
 +
|-align="center"
 +
| 3 || 4 || 8 ||  ||  || style="background: #77A9F4"| 8
 +
|-align="center"
 +
| style="background:#FFCC00"| 1 || 4 || 8 ||  ||  || style="background: #77A9F4"| 1
 +
|-align="center"
 +
| style="background:#FF7F00"|1 || style="background:#FFCC00"| 2 || 8 ||  ||  || style="background: #77A9F4"| 2
 +
|-align="center"
 +
| 1 || style="background:#FFCC00"|2 || 8 ||  12 ||  || style="background: #77A9F4"| 12
 +
|-align="center"
 +
| 1 || style="background:#FFCC00"|2 ||  6 || 12 ||  || style="background: #77A9F4"| 6
 +
|-align="center"
 +
| 1 || style="background:#FF7F00"|2 || style="background:#FFCC00"| 5 || 12 ||  || style="background: #77A9F4"| 5
 +
|-align="center"
 +
| 1 || 2 || style="background:#FF7F00"| 5 || style="background:#FFCC00"| 7 ||  || style="background: #77A9F4"| 7
 +
|-align="center"
 +
| 1 || 2 || 5 || style="background:#FF7F00"| 7 || style="background:#FF7F00"| 11 || style="background: #77A9F4"| 11
 +
 
 +
|}
 +
 
 +
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 +
|-align="center"
 +
! colspan="12" | predecessor
 +
|-align="center"
 +
! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
 +
|-align="center"
 +
|  || 1 ||  || 3 || 2 || 2 || 5 || 4 ||  || 3 || 7 || 8
 +
|}
 
==== Псевдокод ====
 
==== Псевдокод ====
 
<code>
 
<code>
     '''function''' LIS(<tex>\pi</tex>[])
+
     '''function''' LIS(<tex>\pi</tex>[])[]
 
         B = priorityQueue()
 
         B = priorityQueue()
 
         k = 0
 
         k = 0
 
         n = <tex>\pi</tex>.size
 
         n = <tex>\pi</tex>.size
         <color = 'red'>predecessors = [n]</color>
+
         <font color=blue>predecessor = [n]</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>
 
         '''for''' i = 1 to n
 
         '''for''' i = 1 to n
 
             x = <tex>\pi</tex>[i]
 
             x = <tex>\pi</tex>[i]
 
             B.insert(x)
 
             B.insert(x)
             predecessor[x] = B.prev(x)
+
             <font color=blue>predecessor[x] = B.prev(x)</font>
             '''if''' B.next(x) '''exists''' '''then'''
+
             '''if''' B.next(x) '''exists'''
 
                 B.delete(B.next(x))
 
                 B.delete(B.next(x))
 
             '''else'''
 
             '''else'''
 
                 k = k + 1
 
                 k = k + 1
         result = []
+
         <font color=darkgreen>//по цепочке от последнего элемента
 +
        //восстанавливаем НВП</font>
 +
        <font color=blue>result = []
 
         cur = B.max()
 
         cur = B.max()
 
         result += [cur]
 
         result += [cur]
Строка 96: Строка 153:
 
             result += [predecessor[cur]]
 
             result += [predecessor[cur]]
 
             cur = predecessor[cur]
 
             cur = predecessor[cur]
         '''return''' result
+
         '''return''' result</font>
 
</code>
 
</code>
 
== Переименование до <tex>O(n\operatorname{log}\operatorname{log}k)</tex> ==
 
== Переименование до <tex>O(n\operatorname{log}\operatorname{log}k)</tex> ==

Версия 22:26, 5 января 2017

Эта статья находится в разработке!


Задача:
Дана перестановка [math]\pi[/math] [math]\{1, 2,~\dots,~n\}[/math]. Требуется найти НВП [math]\pi[/math] за [math]O(n\operatorname{log}\operatorname{log}k)[/math], где [math]k[/math] — длина НВП.


Task.jpg

Алгоритм [math]O(n\operatorname{log}\operatorname{log}n)[/math]

Нахождение длины НВП

Основная идея

Пусть [math]\pi(n)[/math] — входная перестановка.

Для каждой длины [math]l = 1, 2, \dots[/math] предполагаемой НВП находим наименьший элемент, что может быть последним в возрастающей подпоследовательности длины [math]l[/math], запишем их в массив [math]B[l][/math].

Если обрабатываемый элемент [math]\pi(i)[/math] больше последнего элемента какой-нибудь возрастающей последовательности, он может ее увеличить.

Будем последовательно обрабатывать элементы [math]\pi(1), \pi(2),~\dots,~\pi(n)[/math]:

  • Если [math]\pi(i)[/math] больше [math]\pi(1), \pi(2),~\dots~,\pi(i-1)[/math] , значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец [math]B[/math]
  • Иначе [math]\pi(i)[/math] становится лучшим элементом для такой длины [math]l[/math], что: [math]B[l][/math] [math] = \min \{ B[1..j] \gt \pi(i) \}[/math]

Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции [math]insert, next, delete[/math], соответственно целесообразно использовать приоритетную очередь, реализованную через Дерево ван Эмде Боаса. Таким образом получаем [math]O(\operatorname{log}\operatorname{log} n)[/math] амортизированного времени на одну операцию.

Пример

Типы операций:

Operation1.jpg

Operation2 1.jpg [math]\longrightarrow[/math] Operation2 2.jpg

Последовательность:

[math]\pi_1[/math] [math]\pi_2[/math] [math]\pi_3[/math] [math]\pi_4[/math] [math]\pi_5[/math] [math]\pi_6[/math] [math]\pi_7[/math] [math]\pi_8[/math] [math]\pi_9[/math] [math]\pi_{10}[/math] [math]\pi_{11}[/math] [math]\pi_{12}[/math]
9 3 10 4 8 1 2 12 6 5 7 11

Состояние очереди при каждом добавлении:

[math]B_1[/math] [math]B_2[/math] [math]B_3[/math] [math]B_4[/math] [math]B_5[/math] [math]~\pi_i~[/math]
9 9
3 3
3 10 10
3 4 4
3 4 8 8
1 4 8 1
1 2 8 2
1 2 8 12 12
1 2 6 12 6
1 2 5 12 5
1 2 5 7 7
1 2 5 7 11 11

Псевдокод

   function LIS([math]\pi[/math][]): int
       B = PriorityQueue() // рабочая приоритетная очередь
       k = 0 // длина НВП
       n = [math]\pi[/math].size
       for i = 1 to n
           x = [math]\pi[/math][i]
           // в любом случае добавляем в очередь очередной элемент
           // устаревшие будем удалять
           B.insert(x)
           if B.next(x) exists
               // добавленный элемент — не максимальный
               // удаляем предыдущее значение — заменяем следующий
               B.delete(B.next(x))
           else
               // добавленный элемент - максимальный
               // предыдущие значения не трогаем, очередь увеличилась
               k = k + 1           
       return k

Расширение алгоритма до нахождения НВП

Основная идея

Будем запоминать пары: для каждого элемента записываем его "предшественника".

Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко восстановить НВП .

Общий вид алгоритма

[math]B_1[/math] [math]B_2[/math] [math]B_3[/math] [math]B_4[/math] [math]B_5[/math] [math]~\pi_i~[/math]
9 9
3 3
3 10 10
3 4 4
3 4 8 8
1 4 8 1
1 2 8 2
1 2 8 12 12
1 2 6 12 6
1 2 5 12 5
1 2 5 7 7
1 2 5 7 11 11
predecessor
1 2 3 4 5 6 7 8 9 10 11 12
1 3 2 2 5 4 3 7 8

Псевдокод

   function LIS([math]\pi[/math][])[]
       B = priorityQueue()
       k = 0
       n = [math]\pi[/math].size
       predecessor = [n] // резервируем [math]n[/math] позиций
       for i = 1 to n
           x = [math]\pi[/math][i]
           B.insert(x)
           predecessor[x] = B.prev(x)
           if B.next(x) exists
               B.delete(B.next(x))
           else
               k = k + 1
       //по цепочке от последнего элемента 
       //восстанавливаем НВП
       result = []
       cur = B.max()
       result += [cur]
       while predecessor[cur] exists
           result += [predecessor[cur]]
           cur = predecessor[cur]
       return result

Переименование до [math]O(n\operatorname{log}\operatorname{log}k)[/math]