|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
15.11.2009, 14:10 | #1 |
Регистрация: 15.11.2009
Сообщений: 4
|
Кратчайшее расстояние между всеми вершинами
нужно найти кратчайшее расстояние между всеми вершинами
сразу приходит в голову алгоритм Флойда, но количество вершин <=100000 и матрица такого рамера будет превышать лимит по памяти.... как быть? |
15.11.2009, 14:12 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Можно полное условие задачи? А то сдесь матрица матрицой, если тупой Флойд, то оно зависнет по времени, память это второстепенное. Есть ограничение на количество ребер?
|
15.11.2009, 14:54 | #3 |
Регистрация: 15.11.2009
Сообщений: 4
|
ребра тоже <=100000
|
15.11.2009, 15:06 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Если так, то задача довольно простая, если бы небыло ограничения на ребра - то задача мне кажеться теоретически неразрешимой. Значит так: оформляем граф не ввиде матрицы смежности, а в виде списков ребер. А путь дальнейшего решения зависит от самого графа. Еще несколько уточняющих вопросов от меня (хочеться наконец полносьтю увидеть условие задачи) - граф ориентированный? есть ли упоминания об наличии/отсутствии циклов, циклов отрицательного веса, петель, мультиребер?
|
15.11.2009, 15:24 | #5 |
Регистрация: 15.11.2009
Сообщений: 4
|
граф неориентированный
петель нет вес ребер равен 1 гарантируется, что из каждой вершины можно попасть в каждую вроде как все хммм...а что потом со списком ребер делать то? |
15.11.2009, 15:36 | #6 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Ну теперь хоть кажеться понятным, что от нас требуют. Только один вопрос (может, все еще проще, чем я думаю) - что потом делать с результатами? Ведь мы получим кратчайшие расстояния от 100000 вершин до 100000 вершин, тоесть 10 миллиардов чисел Нужно найти все эти 10 миллиардов результатов? обычно требования в таких задачах другие. Если именно так, то я не представляю, как решать, ведь алгоритмы, которые не загибаються на стадии обработки (и фактически являються верными в таких случаях) просто упадут при сохранении результатов. Если нету закономерности в результатах, то это невозможно сделать, так как придеться потратить 10 Гб, что бы хранить в процессе решения результаты. Можете написать джадж-систему и номер задачи, я сам посмотрю?
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Расстояние между раммкой | Syltan | Microsoft Office Word | 1 | 14.11.2009 20:31 |
Расстояние между строками | Kib | Общие вопросы Delphi | 5 | 30.06.2009 01:02 |
Расстояние между абзацами в CSS | Андрей79 | HTML и CSS | 4 | 13.04.2009 09:59 |
max расстояние между плоскими телами! | Flanker13 | Общие вопросы Delphi | 3 | 17.03.2009 13:46 |
Расстояние между 2 городами | Uli9 | Помощь студентам | 1 | 06.12.2008 22:40 |