Диаметр ну очень большого графа...
Добавлено: 04 окт 2014, 10:04
Есть вопрос о поиске диаметра реально большого графа.
Зачем? Да по сути развлекаюсь - попалась тут малому шахматная головоломка, надо было коней переставлять из одной позиции в другую. Решил помочь, быстренько набросал программку, задача решена, но как обычно - любопытство нас заело: а какая задача на той же доске будет самая сложная, решаемая самым большим количеством ходов - ну, т.е. по сути ищем диаметр графа.
Беда только в том, что узлов у этого графа больше 400 тысяч. Так что тот же алгоритм Флойда-Уоршелла потребует такого количества памяти, не говоря уж о времени, что не хочется и пытаться. А посему вопрос - как-то для такого размера (очень разреженных!) графов можно просчитать диаметр побыстрее и без такого количества необходимой памяти?
Зачем? Да по сути развлекаюсь - попалась тут малому шахматная головоломка, надо было коней переставлять из одной позиции в другую. Решил помочь, быстренько набросал программку, задача решена, но как обычно - любопытство нас заело: а какая задача на той же доске будет самая сложная, решаемая самым большим количеством ходов - ну, т.е. по сути ищем диаметр графа.
Беда только в том, что узлов у этого графа больше 400 тысяч. Так что тот же алгоритм Флойда-Уоршелла потребует такого количества памяти, не говоря уж о времени, что не хочется и пытаться. А посему вопрос - как-то для такого размера (очень разреженных!) графов можно просчитать диаметр побыстрее и без такого количества необходимой памяти?