|
|
|
|
|
|
|
Вернуться
| 21 Карелин Виталий Александрович, 26 марта 2009 г. 18:22:11 | |
Кстати, насколько я понимаю алгоритм Прима:
Строим граф последовательно, по одной добавляя ребра.
На каждом шаге находим ребра между всеми вершинами в графе и всеми вершинами не в графе. Выбираем минимальное и добавляем к графу. И так n-1 раз.
Все правильно?
Но минимальное ребро находится за i*(n-i) сравнений.... (i - количество ребер в графе, (n-i) - количество ребер не в графе)
Итого сравнений: 1*(n-1)+2*(n-2)+3*(n-3)+...+(n-2)*2+(n-1)*1 . Что-то не похоже на n^2...
Данная сумма при n=8000 дает ~85 миллиардов итераций. Многовато...
|
|
|
| 22 SOVA xxx, 26 марта 2009 г. 18:22:09 | |
|
*O((N^2)/2 + N log N)
|
|
|
| 23 SOVA xxx, 26 марта 2009 г. 18:19:41 | |
просто трудно решать задачу без условия:)
её можно решить(я могу решить) за O(N^2 + N log N)
|
|
|
| 24 Карелин Виталий Александрович, 26 марта 2009 г. 18:12:28 | |
|
Если искать 'для каждой вершины вершину ближайшую к ней' то может получиться несвязный граф. И с циклами. Точки все нужно соединить в один граф. И, имхо, очевидно, что циклов быть не должно...
|
|
|
| 25 SOVA xxx, 26 марта 2009 г. 17:39:47 | |
скажу чесна что впервые слышу про прима и краскала за куб...
и я прав:) щас открыл книгу алгоритм прима за O(N^2) но для ограничений видимо не подойдет:)
алгоритм Краскала за О(e log e) где е количество ребер
тока если я правильно понял задачу
то тут врядли они подойдут хотя мб и пойдут))
лучше прима используй или чето другое тк тебе не сам остов минимального вес нужен а дерево с минимальным максимальным листом
а вообщем если я опять же понял задачу то нужно всего найти для каждой вершины вершину ближайшую к ней тк я не вижу чтобы было сказано про дерево или отсутствие циклов:)
|
|
|
| 26 Карелин Виталий Александрович, 26 марта 2009 г. 16:06:52 | |
|
Есть такая задача - есть N точек на плоскости. Их всех нужно соединить вместе, да так, что б максимальная длина ребра была как можно меньше. Как я понимаю - эта задача схожа с задачей нахождения остова минимального веса. Решается такая задача методами Краскела и Прима. Но у этих алгоритмов сложность O(n^3), а в одном месте на этой задаче ограничение N<=8000. И не пройдет никак. Какой тут еще может быть алгоритм? Подскажите, пожалуйста! А то я понятия не имею....
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
