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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.04.2010, 13:25
Новичок

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

Поиск в глубину
Скажите, а можно как-то оптимизировать поиск в глубину?
Может как-то граф к этому готовить заранее?
Есть какие-то способы?
  #2  
Старый 03.04.2010, 15:03
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Поиск в глубину выполняется за линейное время. Куда еще оптимизировать?
  #3  
Старый 03.04.2010, 15:13
Новичок

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

К примеру: мне нужно найти много путей из разных вершин в разные вершины... Есть ли какая-то методика подготовки графа (выкинуть лишнее к примеру), позволяющая оптимизировать поиск?
  #4  
Старый 03.04.2010, 15:18
Новичок

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

Думаю, что можно попробовать искать сразу несколько путей в одном прогоне... Попробую что-нибудь сделать. Если получится - напишу.
  #5  
Старый 03.04.2010, 15:21
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Флойдом за кубическое время (от количества вершин) можно все пути найти
  #6  
Старый 03.04.2010, 16:01
Новичок

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

Кубическое - долго. У меня гораздо меньше пар вершин, между которыми нужно искать расстояние... =)
  #7  
Старый 03.04.2010, 16:02
Новичок

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

Не знаю, может это vector < vector <pair <int, int> > > тормоза создаёт?
  #8  
Старый 03.04.2010, 18:01
гость

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

у вас граф - дерево, как в предыдущем вашем посте? Поиск минимального расстояния в графе

рассказать про LCA?
  #9  
Старый 04.04.2010, 20:09
Новичок

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

Расскажите пожалуйста. LCA может как-то помочь? Причём здесь поиск предка?
  #10  
Старый 04.04.2010, 20:11
Новичок

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

Да, у меня граф - как в предыдущем посте.
 


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

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


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