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

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

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

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

Поиск минимального расстояния в графе
Здравствуйте.

Подскажите, а какой из алгоритмов поиска является на сегодняшний день самым быстрым? Пробовал Дейкстру (в т.ч. с Фиббаночиевой кучей), но производительность не очень устраивает.
Граф - неориентированный, без отрицательных расстояний.

Спасибо.
  #2  
Старый 02.04.2010, 15:13
гость

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

Фибоначчиева куча - скорее чисто теоретическое построение, чем практическое.

Говорят, можно искать пути за линейное время в худшем случае -
http://www.google.com/search?q=short...th+linear+time

Но для реально больших практических графов рулят эвристики - тогда можно и за сублинейное время решать. Но эвристики зависят от задачи. Что у вас за граф?
  #3  
Старый 02.04.2010, 15:54
Новичок

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

Граф у меня - дерево (циклы отсутствуют), взвешенный, целочисленный, неориентированный.
Фибанночиева куча - я имею ввиду использование очереди в Дейкстре. (я так понимаю там M*logN).
Сублинейное - это N+M?

Я так понимаю, что эвристики - это то, что отличает A* от Дейкстры?
  #4  
Старый 02.04.2010, 17:23
гость

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

Дерево говорите? В дереве вообще никакой нах Дейкстры не нужно. Поиск в глубину найдет вам путь за линейное (O(n)) время.

Если есть возможность предобработать граф (тоже линия), то ващще можно пути потом за O(1) искать (в неявном виде) + O(длина пути) чтобы его вывести. Читаем про наименьшего общего предка.
  #5  
Старый 02.04.2010, 17:34
Новичок

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

Подождите...
Я может чего недопонимаю...
А разве поиск в глубину...
а) ...работает быстрее, чем N^2 ?
б) ...способен найти кратчайший путь во ВЗВЕШЕННОМ графе?

Заранее спасибо.
  #6  
Старый 02.04.2010, 17:43
Новичок

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

Блин, а по идее и впрямь за N всё найдёт...
  #7  
Старый 02.04.2010, 17:47
гость

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

Сообщение от newbieman Посмотреть сообщение
Подождите...
Я может чего недопонимаю...
А разве поиск в глубину...
а) ...работает быстрее, чем N^2 ?
число ребер M в любом дереве равно N-1. DFS работает за O(N+M) = O(N).

Цитата:
б) ...способен найти кратчайший путь во ВЗВЕШЕННОМ графе?
а это не имеет значения в дерево. там по определению между любой парой вершин только один путь => нечего минимизировать попросту.
  #8  
Старый 03.04.2010, 09:14
Новичок

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

Подскажите, а как при поиске в глубину восстановить маршрут поиска (и вычислить расстояние) при нахождении нужного элемента?
  #9  
Старый 03.04.2010, 13:24
Новичок

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

В начале процедуры (рекурсивной) записывать в вектор текущий пункт, по выходу из цикла перебора его соседей - удалять его.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск мостов в графе Masha Реализация, исходники, языки 1 24.12.2009 20:34
Поиск всех путей в графе Eldar Графы 6 21.05.2009 09:53
поиск циклов в неориентированном графе giena Графы 1 26.01.2009 05:45
Поиск минимального цикла через алгоритм Форда-Фалкерсона Amber66 Графы 6 20.06.2008 17:48
Поиск путей в графе MrFandorin Графы 5 24.04.2008 01:25