Редактирование: Алгоритм Хьюи

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition=Дано [[Основные определения теории графов#oriented_grath|ориентированное]] [[Дерево, эквивалентные определения#tree|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
+
|definition=Дано ориентированное дерево, вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1..k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
  
 
__TOC__
 
__TOC__
  
==Простое решение==
+
==Алгоритм решения==
Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</tex> количество цветов. Если количество цветов меньше размера машинного слова, то сложность составит <tex>O(V)</tex>.
+
Для начала в каждой вершине поставим 1. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в ее детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать. Для этого запустим [[Обход в глубину, цвета вершин|обход в глубину]]. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим: если вершина с таким цветом еще не встречалась, то просто записываем в <tex>last[col]\ i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] данной вершины и последней вершины с таким цветом и вычитаем из их предка 1, и записываем в <tex>last[col]\ i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны. Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Алгоритм Фарака-Колтона и Бендера|алгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex>
 +
 
 +
Пример:
 +
 
 +
Шаг 0:
 +
[[Файл:algo_0.png|200px]]
  
==Алгоритм решения==
+
Шаг 1:
Будем в каждой вершине дерева хранить по числу, так, чтобы для каждого поддерева ответом была сумма всех значений в вершинах в данном поддереве. Для начала каждой вершине в качестве значения присвоим <tex>1</tex>. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в её детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать.  
+
[[Файл:algo_1.png|200px]]
  
Для этого запустим обход в глубину. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим: если вершина с таким цветом еще не встречалась, то просто присваиваем <tex>last[col]=i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] данной вершины и последней вершины с таким цветом и вычитаем из их предка <tex>1</tex>, присваиваем <tex>last[col]=i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны.
+
Шаг 2:
 +
[[Файл:algo_2.png|200px]]
  
Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Алгоритм Фарака-Колтона и Бендера|алгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex>.
+
Шаг 3:
 +
[[Файл:algo_3.png|200px]]
  
==Пример==
+
Шаг n:
 +
[[Файл:algo_n-1.png|200px]]
  
{| class = "wikitable"
+
Окончательное суммирование
! № шага !! Изображение !! Описание
+
[[Файл:algo_n.png|200px]]
|-align="center"
 
| 0
 
| [[Файл:algo_0.png|300px]]
 
| Расставим у каждой вершины <tex>1</tex>.
 
|-align="center"
 
| 1
 
| [[Файл:algo_1.png|300px]]
 
| Выходим из <tex>8</tex>-ой вершины. Так как желтых вершин еще не было, запоминаем её как последнюю желтую.
 
|-align="center"
 
| 2
 
| [[Файл:algo_2.png|300px]]
 
| <tex>4</tex>-ая вершина. Последняя желтая <tex>-\ 8</tex>-ая. Их LCA <tex>\ -4</tex>-ая вершина. Вычитаем из значения <tex>4</tex>-ой вершины <tex>1</tex> и запоминаем текущую как последнюю желтую.
 
|-align="center"
 
| 8
 
| [[Файл:8.png|300px]]
 
| Пропустим несколько тривиальных шагов. Выходим из <tex>11</tex>-ой вершины. Последней посещенной зеленой была <tex>5</tex>-ая (не <tex>3</tex>-я). Вычитаем из их LCA (<tex>1</tex>-ой вершины) <tex>1</tex> и запоминаем <tex>11</tex>-ую как последнюю зеленую.
 
|-align="center"
 
| 9
 
| [[Файл:9.png|300px]]
 
| Выходим из <tex>7</tex>-ой вершины. Последней синей была <tex>2</tex>-ая. Вычтем из их LCA <tex>1</tex> и запомним <tex>7</tex>-ую как последнюю синюю.
 
|-align="center"
 
| суммирование
 
| [[Файл:algo_12.png|300px]]
 
|Пропустим еще два шага. В результате суммирования получаем в каждой вершине ответ на задачу для поддерева.
 
|-
 
|}
 
  
 
==Псевдокод==
 
==Псевдокод==
'''int''' col[MAX_COL], used[MAX_N], sum[MAX_N]
+
  '''func''' dfs (Node v)''':'''
+
     used[v] := true
  '''func''' dfs('''Node''' v)''':'''
+
     '''for''' <tex>u \in v.children</tex>
     used[v] = ''true''
 
     '''for''' <tex>u \in</tex> v.children
 
 
         '''if''' !used[u]
 
         '''if''' !used[u]
 
             dfs(u)
 
             dfs(u)
         sum[v] += sum[u]
+
         sum[v] := sum[v] + sum[u]
 
     '''if''' last[col[v]] != -1
 
     '''if''' last[col[v]] != -1
         sum[lca(v, last[col[v]])]--
+
         sum[lca(v, last[col[v]])] -= 1
     last[col[v]] = v
+
     last[col[v]] := v
 
          
 
          
  '''func''' hugh('''int''' n, '''int''' k, '''Node''' root)''':'''
+
  '''func''' hugh (int n, int k, Node root)''':'''
 
     '''for''' <tex>v \in V</tex>
 
     '''for''' <tex>v \in V</tex>
         used[v] = ''false''
+
         used[v] := false
         sum[v] = 1
+
         sum[v] := 1
     '''for''' i = 1 '''to''' k
+
     '''for''' k := 1 to k
         last[i] = -1
+
         last[k] := -1
     dfs(root)
+
     dfs (root)
  
 
==Обоснование корректности==
 
==Обоснование корректности==
Отсортируем вершины по времени входа. Рассмотрим вершину <tex>v</tex>, в поддереве которой <tex>k</tex> вершин одного цвета. Так как мы обходим вершины в порядке времени входа, эти <tex>k</tex> вершин мы обойдем последовательно. Их наименьший общий предок будет лежать в данном поддереве. Следовательно мы вычтем <tex>k-1</tex> раз единицу из вершины <tex>v</tex>. Для любых других двух вершин их наименьший общий предок не будет лежать в данном поддереве. Следовательно для каждого поддерева учтется по одной вершине каждого цвета, существующего в данном поддереве.
+
{{Лемма
 +
|statement = Наименьшим общим предком вершины и группы вершин, предшествующих по времени выхода, является наименьший общий предок данной вершины и последней, предшествующей ей из группы.
 +
|proof = Рассмотрим дерево как последовательность букв, когда при входе в вершину или выходе из нее записывается ее буква. Пусть рассматриваемая вершина <tex>-\ u</tex>, а последняя рассмотренная из той же группы <tex> -\ v</tex>, их наименьший общий предок <tex>-\ w</tex>. Рассмотрим два варианта расположения этих двух вершин.
  
==См. также==
+
[[Файл:proof_1.png|200px]]
*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
+
[[Файл:proof_2.png|200px]]
 +
 
 +
Теперь возьмем вершину <tex>z</tex>, которая встречается до выхода из <tex>v</tex>. Перебрав несложные пять случаев, можно легко убедиться, что наименьший общий предок <tex>u</tex> и <tex>v</tex> будет ниже, чем наименьший общий предок <tex>u</tex> и <tex>x</tex>.
 +
}}
  
*[[Метод двоичного подъема]]
+
Для того, чтобы учитывать вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка 1. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на 1, так как наименьший предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка этой группы точек. А как раз это и требуется - для каждой пары точек одного цвета учесть данный факт в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех.
  
[[Категория: Алгоритмы и структуры данных]]
+
[[Файл:hugh.png|300px]]
  
[[Категория: Задача о наименьшем общем предке]]
+
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: