Есть вопрос о поиске диаметра реально большого графа.
Зачем? Да по сути развлекаюсь - попалась тут малому шахматная головоломка, надо было коней переставлять из одной позиции в другую. Решил помочь, быстренько набросал программку, задача решена, но как обычно - любопытство нас заело: а какая задача на той же доске будет самая сложная, решаемая самым большим количеством ходов - ну, т.е. по сути ищем диаметр графа.
Беда только в том, что узлов у этого графа больше 400 тысяч. Так что тот же алгоритм Флойда-Уоршелла потребует такого количества памяти, не говоря уж о времени, что не хочется и пытаться. А посему вопрос - как-то для такого размера (очень разреженных!) графов можно просчитать диаметр побыстрее и без такого количества необходимой памяти?
Диаметр ну очень большого графа...
Диаметр ну очень большого графа...
Последний раз редактировалось kiv 27 ноя 2019, 20:34, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Computer Science»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость