IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Поиск центра графа
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


Здравствуйте.

Собственно задача:

Имеется сильно связный неориентированный невзвешенный граф. Требуется найти такую вершину (центр), чтобы кратчайшие расстояния от нее до всех остальных вершин графа были, по-возможности, минимальны.(по-моему не совсем корректно, поэтому скажу иначе: поиск в ширину, пущенный от нее, должен сделать минимальное число "волн").

Естественно, решение за O(n^2) очевидно (просто серия из n поисков в ширину), но при этом время работы алгоритма слишком велико. Собственно, был бы рад любым идеям по реализации данного алгоритма smile.gif .

ЗЫ
Из собственных мыслей:

1.) Взять произвольную вершину. Пустив bfs из нее, найти наиболее удаленную от нее вершину ( пусть она будет называться L ). Пустив bfs от L, найти наиболее удаленную от нее вершину ( R ). Пустить одноременно два bfs'а от L и R и ждать их пересечения. Центр, имхо, будет лежать где-то в множестве вершин, вошедших в это пересечение. (но опять - таки их слишком много)

2.) Попытаться использовать данные предыдущих поисков. Но эта идея по-моему бесперспективна...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


Неужели ни у кого нет никаких идей? Может условия задачи невнятно сформулировал?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Условие-то понятно, просто графы - это вообще не самая приятная тема.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
Естественно, решение за O(n^2) очевидно (просто серия из n поисков в ширину), но при этом время работы алгоритма слишком велико.
Какой же у тебя граф, если на нем O(n2) слишком долго работает? В принципе и поиск центра орграфа (Флойд + минимальный эксцентриситет), который имеет сложность O(n3), отрабатывает довольно быстро. Никогда не сталкивался с тем, что "время работы алгоритма слишком велико".

Можно посмотреть на твой граф (хотя бы приблизительно, количество вершин чему равно?).
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Даже когда известны ВСЕ расстояния между всеми вершинами, возможно ли определить центр по этой матрице расстояний меньше, чем за квадрат?
А вообще, тут, видимо, важно не только кол-во вершин в графе, но и кол-во рёбер.
Гы, http://forum.sources.ru/index.php?showtopic=225018


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


Цитата
Можно посмотреть на твой граф (хотя бы приблизительно, количество вершин чему равно?).


Количество вершин невелико(порядка тысячи). Дело в том, что время работы ограничено двумя секундами (а при этом имеются еще и некоторые подготовительные операции).

Цитата
Даже когда известны ВСЕ расстояния между всеми вершинами, возможно ли определить центр по этой матрице расстояний меньше, чем за квадрат?


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

Вообще, мне кажется, из того, что граф неориентированный и невзвешенный вытекает то, что значения минимального эксцентриситета для двух смежных вершин не будут различаться больше, чем на единицу. Исходя из этих соображений, я написал поиск, который, начиная с какой-то случайной вершины, идет по смежным вершинам с минимальным эксцентриситетом подобно поиску в глубину(причем я обрываю его по достижениии какого-то предельного числа ходов). Но опять-же при заданных временных ограничениях он не находит правильного ответа. Почему так происходит, я не понимаю (предельное число ходов - около 800, при этом, имхо, можно несколько раз пересечь граф по диаметру).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


> время работы ограничено двумя секундами

СТОП. Это для олимпиады? Тогда мы не будем помогать.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


Цитата
СТОП. Это для олимпиады? Тогда мы не будем помогать.


Ну и что с того? Это же чистая теория графов... Вопрос в том, знаешь ты как это делается, или нет. А если я к примеру не знаю, как Дейкстра пишется? Что мне, самому ее придумывать?))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(Tony @ 5.01.2010 23:06) *
А если я к примеру не знаю, как Дейкстра пишется? Что мне, самому ее придумывать?))
Во-первых, Дейкстра - он. И алгоритм, кстати, - тоже.
Да и в придумывании велосипедов (особенно для олимпиады) ничего плохоого нет. Я, например, и придумал и написал несколько реализаций "Дейкстры" до того, как узнал, что этот алгоритм, оказывается, имеет имя собственное (причем, что самое обидное - не мое smile.gif.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Если это задача с реальной олимпиады, в которой ты в данный момент участвуешь, то думай сам.
Если это с какой-то давно прошедшей, то тогда да, попробуем помочь.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


Цитата
Во-первых, Дейкстра - он. И алгоритм, кстати, - тоже.
Да и в придумывании велосипедов (особенно для олимпиады) ничего плохоого нет. Я, например, и придумал и написал несколько реализаций "Дейкстры" до того, как узнал, что этот алгоритм, оказывается, имеет имя собственное (причем, что самое обидное - не мое smile.gif.


Возможно, алгоритм Дейкстры не самый удачный пример)) Ну да ладно...

Цитата
Если это задача с реальной олимпиады, в которой ты в данный момент участвуешь, то думай сам.
Если это с какой-то давно прошедшей, то тогда да, попробуем помочь.


О'кей, буду думать)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 2.12.2020 4:56
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name