Доброго времени суток, всезнающий all! На днях пришлось заюзать вышеуказанный алгоритм (кто не в курсе, поиск оптимального пути на взвешенном графе). Не думал, что возникнут вопросы, но они возникли. Если граф достаточно большой, нет смысла весь его держать в памяти. Нужно только текущие ветки. Тоесть необходимо написать некий менеджер памяти (может еще как?), где можно будет достаточно быстро добавлять, удалять и получать доступ к элементам - переходам по вершинам графа. К тому же необходима связь между элементами - запоминание, откуда (с какой вершины) пришли в данную точку. Есть у меня идеи, но какие-то карявые. Такой оптимизацией не занимался. Может кто уже делал что подобное. Размерность графа - 3. Но это думаю не особо большую роль играет. ЗЫ Кстати есть идея с sqlite сделать, чтобы обрабатывать данные о вершинах в индексированных таблицах. Вобщем делимся мнениями.
chuti pereformuliruite zadachu v storonu konkretnosti i opredelionnosti, otbrosiv lishnie detali vrode sqlite i bellmanov. vy hotite menedger pamiati? Opishite ego jelaemye svoistva s minimum vtorostepennyh detalei
qqwe В том и дело, что мне нужно реализовать алгоритм Беллмана, а как - это вопрос. Я задал вопрос более широко. Возможно не нужно писать менеджер памяти, я и хотел посоветоваться. По поводу конкретных свойств менеджера памяти - они вытекают из особенностей самого алгоритма. А описывать алгоритм здесь смысла не вижу, очень долго будет. Вот ссылка на вики ru.wikipedia.org/wiki/Алгоритм_Беллмана-Форда. Алгоритм очень распространенный, я надеюсь многие с ним знакомы. Спасибо.
Эм может я что-то не понимаю, но к чему менеджер памяти в графе с 3 вершинами? o_O Или под "размерностью" подразумевается что-то другое? vector < vector < pair<int,int> > > g; // сам граф vector<int> par; // откуда пришли в i-ую вершину (из какой вершины) ? Если нужно совсем динамическое, то можно в сторону map<int, set<int> >, multimap<int,int>, hashmap и т.п. [added] Хотя, если только Форда-Беллмана запускать, то граф вообще можно хранить как set < pair< pair<int,int>, int> > - список рёбер.
>> Размерность графа - 3 Имел ввиду матрица 3-хмерная. STL вообще не покатит. Я конечно понимаю, что очень удобно создавать и обращаться с элементами в контейнере. Но при большой размерности ты себе представляешь, сколько будет вызывать new / delete ?! А создать весь граф сразу тоже нельзя (см. первое сообщение). Выделить надо сразу какой-то буфер, и в нем работать. То есть менеджер памяти. Но тогда нужны алгоритмы быстрой перестановки/поиска и тд. Все-таки склоняюсь к тому, чтобы заюзать sqlite движок. Чем не менеджер памяти? И доступ к огромным объемам очень быстрый. И сохранить сразу можно.
perez, окей, но какие именно операции на графе выполняються будут? От того, насколько динамичной должна быть структура, всё ведь сильно зависит.
Ну смотри. Делается очередная итерация. Делается по шагу из всех оконечных текущих вершин. Во - первых надо знать, что это за вершины. Все текущие пути увеличатся. Проверить цену доступ до каждой новой точки со всех сторон. Выявить не актуальные ветки. Проследить неактуальную ветку назад до первого ответвления. Удалить не актуалные переходы. Уже куча механизмов, связанных с доступом и удалением. Потом появляются пробелы в памяти в основном мелкие и в большом количестве. Во всей этой структуре необходимо прослеживать очередность ходов, то есть кто за кем, чтобы потом вернуться по пути. Ветвлений ОЧЕНЬ много. Есть мысль Просто создать большой массив структур и просто по ходу дела инициализировать их вместо того чтобы новые создавать / удалять. Но тут опять же если просто после скольких-то итераций алгоритма "чистить память" от пробелов, возникает куча лишних действий с индексацией (i-й элемент знает, за кем он стоит, но при перемещении в массиве индекс сменится). Короче поиска немеряно будет по массиву. Потом если предположить, что можно отсортировать этот массив, то как сравнивать элементы? У них будет x, y, z и кое-какая доп инфа. Наврядли это получится.
>> И если так важна оптимизация, почему Форд-Беллман, а не Дейкстра? Ну наверное потому, что алгоритм Беллмана я со студенческой скамьи знаю, в простом случае даже реализовывал. Знаю реальные задачи, решенные с пом. него. Потом уважаю своего профессора по мат. программированию, который любит его =) Я с ним больше знаком, его можно усложнять, навешивать разные фичи. К примеру можно задать как условие - минимально количество поворотов в пути. То есть не единственное условие - кратчайший путь, а дополнительные можно вводить.
perez, я если честно, вообще не понял твой предпоследний пост. Какие ветки, какие удаления переходов? Это относится к самому алгоритму Форда-Беллмана или к специфике программы? Вот классический алгоритм Форда-Беллмана в простейшей stl-ной реализации: Код (Text): int n; // число вершин vector < vector < pair<int,int> > > g; // граф списками смежности vector<int> dst (n, INF), p (n, -1); // расстояние до каждой вершины, и предыдущая вершина в оптимальном пути dst[start_v] = 0; for(;;) { bool any = false; for (int i=0; i<n; ++i) if (dst[i] != INF) for (size_t j=0; j<g[i].size(); ++j) { int to = g[i][j].first; if (dst[i] + g[i][j].second < dst[to]) { dst[to] = dst[i] + g[i][j].second; p[to] = i; any = true; } } if (!any) break; } В ходе самого Форда-Беллмана ничего ниоткуда удалять не надо, пути все потом можно восстановить по вектору p[], памяти кроме самого графа надо на 2N int'ов. Так что плиз объясни ещё раз, что ты хотел сказать.
