Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 04.04.2010, 20:16
гость

 
Сообщений: n/a

Сообщение от newbieman Посмотреть сообщение
Расскажите пожалуйста. LCA может как-то помочь? Причём здесь поиск предка?
а притом что путь между любыми двумя вершинами x и y в любом дереве всегда выглядит следующим образом - сначала надо подняться от x до z=lca(x, y), а потом от него спускаться к y. (причем неважно даже что за вершина выбрана корнем)

соответственно алгоритм такой. выбираем произвольный корень, вычисляем два массива одним проходом по дереву: parent[x] = родитель вершины x и depth[x] = глубина вершины x относительно выбранного корня.

потом путь от x к y (и попутно их lca) ищем так:

// шаг 1. выровнять глубины вершин
while (depth[x] != depth[y]) { if (depth[x] < depth[y]) x = parent[x]; else y = parent[y];

// шаг 2. дойти до общего предка
while (x != y) { x = parent[x]; y = parent[y];

все. вам осталось только после каждого присваивания x = parent[x] и y = parent[y] запоминать соответствующее ребро в каком-то массиве (отдельно для x и y), а в конце вывести их содержимое.
  #12  
Старый 04.04.2010, 20:18
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
while (depth[x] != depth[y]) { if (depth[x] < depth[y]) x = parent[x]; else y = parent[y];
наоборот - if (depth[x] > depth[y]) x = parent[x]; else y = parent[y]; - т.е. делаем шаг вверх из более глубокой вершины.
  #13  
Старый 05.04.2010, 00:43
Новичок

Отправить личное сообщение для newbieman Посмотреть профиль Найти все сообщения от newbieman
 
Регистрация: 02.04.2010
Сообщений: 18

Спасибо. Буду разбираться. Скажите, а будет ли это быстрее обычного поиска в глубину?
  #14  
Старый 05.04.2010, 01:42
гость

 
Сообщений: n/a

Сообщение от newbieman Посмотреть сообщение
Спасибо. Буду разбираться. Скажите, а будет ли это быстрее обычного поиска в глубину?
при поиске в глубину надо просматривать весь граф - O(n) времени. Здесь же время пропорционально числу вершин в искомом пути, т.е. время работы равно объему выходных данных, что асимптотически оптимально.
  #15  
Старый 05.04.2010, 01:44
гость

 
Сообщений: n/a

предобработка (вычисление предков и глубин вершин), конечно, также требует O(n) времени как и поиск в глубину/ширину/любой другой вид обхода но выполняется лишь один раз.
  #16  
Старый 06.04.2010, 14:31
Новичок

Отправить личное сообщение для newbieman Посмотреть профиль Найти все сообщения от newbieman
 
Регистрация: 02.04.2010
Сообщений: 18

Правильно ли я понимаю, что предобработка (т.е. создание массивов parent[] и depth[]) производится для каждой пары вершин рекурсивным проходом в глубину? Ведь тогда всё это будет работать дольше обычного поиска в глубину.

Если предобработка делается один раз - то почему мы строим массивы parent[] и depth[] относительно x (т.е. одной из вершин в очередной паре)?
  #17  
Старый 06.04.2010, 15:31
гость

 
Сообщений: n/a

Сообщение от newbieman Посмотреть сообщение
Правильно ли я понимаю, что предобработка (т.е. создание массивов parent[] и depth[]) производится для каждой пары вершин рекурсивным проходом в глубину?
Неправильно вы понимаете. Предобработка выполняется один раз для всего дерева. Сколько у вас разных деревьев, столько у надо раз делать предобработку.

На предобработанном дереве путь ищется описанным выше алгоритмом за время пропорциональное его длине.
  #18  
Старый 06.04.2010, 19:42
Новичок

Отправить личное сообщение для newbieman Посмотреть профиль Найти все сообщения от newbieman
 
Регистрация: 02.04.2010
Сообщений: 18

Да, я глупость сказал. Спасибо. Понял.
Осталось два вопроса:
1) Выбор корня влияет на производительность? Можно ли выбрать корень с пользой для производительности? Или можно за корень взять любую вершину?
2) Какой из алгоритмов поиска LCA самый быстрый?

Заранее спасибо.
  #19  
Старый 06.04.2010, 19:49
гость

 
Сообщений: n/a

Сообщение от newbieman Посмотреть сообщение
Да, я глупость сказал. Спасибо. Понял.
Осталось два вопроса:
1) Выбор корня влияет на производительность?
нет, путь между двумя вершинами же один и тот же

Цитата:
2) Какой из алгоритмов поиска LCA самый быстрый?
В данном случае, когда вы выводите весь путь, вам LCA собственно быстро искать и не надо - вы гораздо больше времени затратите на вывод пути, чем на поиск LCA.

А вот если бы вам нужен был бы не весь путь, а скажем только его длина, тогда другое дело....
  #20  
Старый 06.04.2010, 21:22
Новичок

Отправить личное сообщение для newbieman Посмотреть профиль Найти все сообщения от newbieman
 
Регистрация: 02.04.2010
Сообщений: 18

Так я же ищу LCA для каждой пары вершин. А их много.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Задачи 0 18.03.2009 18:03
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Графы 0 18.03.2009 03:21
помогите написать программу поиск в глубину на графе гость Реализация, исходники, языки 2 17.01.2009 13:51
Обход графа в глубину гость Реализация, исходники, языки 2 20.11.2007 11:47