| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Привет, Кодфорсес.
Друзья, а расскажите, пожалуйста, что вы знаете про быстрое нахождение радиуса и/или диаметра невзвешенного неориентированного графа (определения тут) ? Быстрое = быстрее, чем за O(MN) (т.е. обходы в ширину из каждой вершины). Интересуют любые результаты: вероятностные, в среднем, для неплотных графов и т.д. Благодарю.
Гипотеза: если рассмотреть произвольную вершину a, найти самую удалённую от неё вершину b, а потом найти самую удалённую от b вершину с, то расстояние между b и c будет диаметром.
Нашёл контрпример:
7 8
0 1
0 3
0 4
1 2
1 3
1 4
3 5
4 6
a = 0, b = 2, c = 5. А диаметр равен 4.
Хорошая гипотеза. Для дерева она даже верна. =)
Для произвольного графа не всегда, к сожалению. Рассмотрим граф, состоящий из цикла длины 6 и еще одной вершины, связанной ребром с какой-нибудь вершиной цикла, что-то вроде этого (буквы — это вершины):
Тогда, запустившись, например, от B, найдем самую удаленную вершину F. От нее все расстояния не больше 3, при том, что диаметр равен 4 (E — D).
А если попробовать проитерировать этот алгоритм MAGIC раз? Ну для MAGIC = 10-20.
ответ чуть ниже)
Из левой вершины приходим в правую, из правой — в левую. Клинч. А диаметр, между тем, между верхней и нижней.
Тестили, не работает.
И ведь даже неверно, что если две вершины являются друг для друга самыми удалёнными, то расстояние между ними является диаметром.
Немного неправильно понял.
Таких пар просто может быть несколько с разным расстоянием(см. примеры выше)
Не две самые удалённые вершины, а вершины, которые являются самыми удалёнными друг для друга, то есть, среди всех вершин графа вершина b находится дальше всех от a, а вершина a — дальше всех от b.
Да-да, я знаю, немного не так прочитал ваш комментарий.
Не годится: Для графа
http://i021.radikal.ru/1203/12/81ff712b94e6.png
Если идти от вершины 10, то найдём вершину 11 и от неё 8 или 1. Но диаметр это путь от 8 до 1.
UPD: впрочем опоздал :)
А вопрос практический или теоретический? Я просто вроде придумал какой-то треш за n2 × ln4(n) =)
Просто вроде можно хитрыми махинациями с сетами (испльзуя бинпоиск по ответу) перемножить два графа (в смысле, перемножить их ориентированные матрицы смежности) за n2 × ln2(n). Если будут желающие, могу пояснить, как это делать.
А тогда можно за n2 × ln3(n) возвести граф в степень d (квадрат графа, степень — аналогично) и выяснить, является ли она полным графом (для диаметра) или есть ли вершина, смежная со всеми (радиус графа). А значит, можно бинпоиском по ответу найти диаметр или радиус за n2 × ln4(n).
В предположении, что можно перемножать графы за n2ln2(n), можно решать и за n2ln3(n). За n2ln3(n) возведем граф во все степени, являющиеся степенями двойки, и запомним все эти графы. Делая бинпоиск, будем хранить помимо чисел-границ бинпоиска граф в степени левой границы бинпоиска. За n2ln2(n) будем его обновлять при каждом шаге бинпоиска вправо.
Да, правильно, я недодумал)
И да, мне интересно, как это делать :)
Что-то я теперь перестал понимать, как это делать. Постараюсь к вечеру снова понять. Суть у меня была в том, что это не обычные матрицы, в каждой ячейке произведения лежит не сумма n элементов, а or. Поэтому необязательно искать все элемнты — наоборот, желательно действовать так, чтобы каждое ребро было найдено только один раз.
Нехорошо получилось, я всех заинтриговал, а теперь не знаю, как это делать =(
Кстати, алгоритм Штрассена же перемножает матрицы за nln27, так что можно найти радиус и диаметр за то же самое умножить на ln(n). Когда рёбер достаточно много, это меньше, чем n × m.
Он, конечно, перемножает, но ему нужна обратная операция к "сложению". Поэтому его нельзя применять к поиску кратчайших путей и иже с ним, у минимума и логического "ИЛИ" нет обратной операции.
ммм, да, действительно. Обидно.
Разве здесь не достаточно простого умножения матриц? Матрица смежности в какой-то степени это количество путей какой-то длины между всеми парами вершин. Нам тут только нужно сравнивать эти количества с нулем.
Ну, это то же умножение матриц, только вместо сложения — ИЛИ, а вместо умножения —И, ну или максимум с минимумом. Кстати, вроде бы метод четырех русских для такого умножения работал, если мне память не изменяет.
Да нет, можно использовать именно умножение и сложение, и считать количество путей.
Изначально в матрице записано количество путей длины один между каждыми двумя вершинами — 0 или 1. Чтоб было проще, стоит, наверное, добавить петли. Тогда будет количество путей длины не более, чем 1.
Да, похоже на правду. Что-то я не о том думал, когда писал прошлый комментарий.
Значит, сложность выходит nln27logn. Неплохо. =) А ведь матрицы можно перемножать еще быстрее, хотя на практике быстрее Штрассена вроде ничего не используется.
По поводу битовых матриц.
http://www.sciencedirect.com/science/article/pii/S0019995873902283
Да на практике и это, весьма вероятно, будет работать дольше, чем куб, особенно хорошо написанный. Гораздо лучше (чем Штрассен) применить битовую оптимизацию и грамотное отсечение с рандомом.
Кстати, а ты прав. Можно ведь возводить в степень не матрицу boolean'ов, а матрицу int'ов.
Что-то мне подсказывает, что n2×ln4(n) хуже, чем n * m :)
Ну теоретически лучше, но на практике хуже, конечно) Потому я и спрашивал, теоретический это вопрос или практический =)
Ну даже если n=100, то n2×ln4(n) = 40'960'000 а n×m = 500'000
Я же уже согласился, что n × m на практике лучше?
Примеры, когда n2 × ln3(n) меньше, чем n × m (формально, без учёта константы) начинаются примерно с n = 10000, даже если считать, что m = n2 / 2.
Скорее практический, но теоретически тоже интересно.
Круто, у меня вот никакого прогресса не вышло. А как вы так быстро матрицы перемножаете? =)
wil93 and I once attended a conference about the theme. You can find some useful papers here, under "Fast Computation of the Neighbourhood Function and Distance Distribution", and here (look at the links in the bottom of the text). Hope this helps :)
Yep, the algorithm they presented was as follows:
Dist(U,V)is better than the best diameter found then update it, else exit.The interesting thing is that the algorithm founds the diameter very soon.
If you want an approximate diameter, then you can stop manually after having done, say, K searches. The algorithm is then O(MK). It is worth noting that you will find very good results even with very small K.
When they presented this algorithm, they showed us the results and the running time of some test with (if I'm not mistaken) K = 10, compared to the O(MN) algorithm. It turned out that even with that value of K the diameter found was very close to the "best" one.
Yes, that seems to be cool thing to use in practice. But, as we discussed a bit earlier (in Russian, though =)), we can choose U in such unlucky way that we won't find precise diameter ever.
Well, in the real task that I approached graphs could be pretty dense, so there's no sense in "approximating" radii or diameters, as they were quite small.
Still, thanks for pointing out the papers and nice description!
Does it work for every kind of graphs?
(I am missing comment delete option :(. )
No, example below.
Yes it does. But it is an approximate algorithm, as you are running only K iterations (where K ~ 10 or more, depending on you). It is interesting as it finds quickly the optimal solution (the "optimal in average" K is relatively small, so using a fixed small K can works well). Maybe this algorithm isn't very reliable in programming contest, because of its "approximate" nature, but in practice it is good.
Tranvick is correct. I mistaken the problem. Many thanks.
You are wrong, it works only for trees.
We run BFS from A, then from B and answer will be 3. But really answer is 4(E — D).
Your algorithm is ok for get a tree's diameter, but it's wrong for get a graph's diameter.
Сорри, отвечу про взвешенный случай:
Раньше думал, что диаметер графа (правда для взвешенного случая) не умеют решать быстрее чем APSP. Но вот тут говорят обратное: http://arxiv.org/abs/1011.6181
На практике предлагается параллелить BFS (Дейкстру), как сделать это очень эффективно можно прочитать тут http://is.gd/P7YLL1
Наверное, для невзвешенного случая ситуация иная, было бы интересно узнать, как это можно сделать быстро и желательно просто.
Есть забавная идея в этом направлении.
Рассмотрим дерево кратчайших путей от одной вершины. Для любой пары вершин, являющихся предком и потомком в нем, кратчайшее расстояние равно расстоянию между ними по дереву. Вот если оно достаточно высокое (это часто для разреженых графов), это отсекает очень проверок расстояния сразу.
Upd. Кроме того, его диаметр дает очевидный диапазон ответа. Мы можем узнать, что ответ маленький, и попробовать что-нибудь резко оптимизировать, например, случайным образом ребра релаксировать и какие-то вершины полностью тестировать, которые нам не нравятся.
Кстати, забавная оптимизация алгоритма за O(N*M) получается. Можно вместо того, чтобы каждый раз пускать BFS, обрабатывать предка наибольшего поддерева дерева кратчайших путей. В этом случае можно автоматически не рассматривать все вершины его поддерева, так как они уже кратчайшие. Наверное, можно еще что-то поотсекать.
Может быть стоит переименовать тему, чтобы она соответствовала содержанию? Ну "Поиск диаметра произвольного графа".
Done.
Our group in Florence recently worked on the computation of the diameter of large real-world graphs. You can download our software at http://amici.dsi.unifi.it/lasagne. In the web site, all the references are also listed. I hope this helps.
Для взвешенных графов есть такая статья http://arxiv.org/abs/1011.6181 В ней же есть библиография, тоже интересно.
Обидно правда, что там опять используется умножение матриц за N^{2.376}. Это, конечно, хороший алгоритм. Но для N <= 10^{100} вроде ускорения не дает из-за константы :)
В общем, работа представляет интерес для чистых теоретиков.
http://arxiv.org/abs/1209.4761
Что-то я не читал этот пост, когда он активно обсуждался. Сейчас просмотрел, в комментариях не нашел такой простой метод.
Используя метод 4-х русских, я умею за N^3 / log^2 перемножить 2 матрицы операциями AND и OR.
Используя идею, которую уже озвучили в комментариях (предподсчитать все степени D^{2^k}, где D — матрица смежности + бинпоиск по ответу), мы получили решение за N^3 / log, что строго лучше чем NM для почти полных графов. Т.е. для почти полных графов есть решение :-)
Теперь про произвольные графы:
Уже обсуждалась идея "возьмем случайную вершину, от нее самую дальнюю, от нее тоже, так будем делать, пока расстояние увеличивается, а все это запустим 100 раз".
Я знаю существенное улучшение этой идеи: по ходу можно отмечать "уже бесполезные вершины", а потом обрывать процесс, когда мы попадаем в "бесполезную вершину". Чем лучше работает определитель "бесполезности", тем быстрее алгоритм сходится. Можно еще неравенство треугольника использовать (d[a][b] <= d[a][c] + d[c][b]).