|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 19 Dec 2001 05:11:04
To : Ilia Kantor
Subject : Re: Гоpит отчет по куpсовой. Сpочно! Need help!!!
--------------------------------------------------------------------------------
До меня дошли слухи, что *16.12.01* *21:35:44* пролетало сообщение
от Ilia к *Sergey Politov* про *"Гоpит отчет по куpсовой. Сpочно! Need
help!!!"*. И я решил вмешаться.
IK> Я имел в виду описание алгоpитма поподpобнее, как его пpидумал ты.
IK> Что за *поpядок важен* ? Hу и по втоpой части задачи у тебя, вpоде,
IK> тоже pешение есть, чтобы сложность складывалась :)..
Hачнем с самого простого. *поpядок важен* - т.е. граф остается
ориентированным.
Теперь решение, я придумал более прикольное решение, которое быстрее. Значит
слушай.
Берем наш граф и составляем по нему новый. Вершин в нем будет v*(l+1), где v
- кол-во
вершин в старом графе, а l - длина последовательности меток. Вершина будет
как бы парой
(a,b), где a - вершина в страром графе, а b - по скольким меткам из
последовательности
ты уже прошел, теперь о ребрах, ребра все остаюстся в своих слоях, т.е. если
было ребро
a-c, то в новом графе будут все ребра (a,b)-(c,b), для всех b. Теперь
спрашивается, как
попасть из слоя в слой, т.е. когда b отличаются. Отвечается если в исходном
графе было
ребро a-c, и вершине c была приписана метка, котороя стоит на k-м месте в
последовательности, то в новом графе будет ребро (a,k-1)-(c,k), вот вроде
все. Теперь
просто поиск в ширину на этом графе, и искомое множество все вершины, в
которые получилось
попасть, на последнем уровне.
Теперь о второй части. После такого поиска можно, спускаясь с верхнего слоя
вниз, для всех
вершин в которых, мы были найти интересующее нас множество. Так вот теперь
зачем все это
делалось. Когда мы провели поиск для нескольких кольких вершин, и ведя поиск
для следующей,
натыкаемся на вершину в которой мы были при одном из предидущих поисков, то
дальше от этой
вершины можно не идти, наше множество для нее не увеличится. Вообще мне
кажется, что все
можно найти уже на первом уровне и для более высоких уровней это множество не
хранить,
просто запоминать попадали мы в эту вершину или нет что бы останавливать в
ней поиск. Hо
это только подозрение. Вообще-то сложность не складывается, но и алгоритм
другой.
Теперь про сложность поиск в ширину O(e*l), e - кол-во ребер в исходном
графе. Hа спуск
O(e*l), т.к. множество считается как объединение множеств вершин смежных с
данное, то
каждое ребро рассматривается по одному разу. Теперь о памяти если по умному
организовать
спуск, и мое предположение верно, то во время спуска можно хранить множество
только, для
обсчитываемого и следующего уровня, т.е. памяти на это уйдет O(v), а вот
новый граф, если
со вторым пунктом, придется хранить весь что есть O(v*l), а вот если думать
только о первом
пункте и изменить поиск в ширину, так что бы он искал не кратчайшее
расстояние а просто
проверял возможность попадание, то памяти надо всего на хранение двух
уровней, текущего
и на уровень выше, что есть O(v). Вроде все.
Я знаю что объясняю я фигово, так что не обижусь если будет тьма вопросов.
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Металл сила - всем рэперам могила. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
