Каков был бы хороший алгоритм для проверки циклической ссылки в этом случае?
Для тех, кто любит Debian и предварительно упакованную Java:
sudo mkdir /usr/share/ca-certificates/test/ # don't mess with other certs
sudo cp ~/tmp/test.loc.crt /usr/share/ca-certificates/test/
sudo dpkg-reconfigure --force ca-certificates # check your cert in curses GUI!
sudo update-ca-certificates --fresh --verbose
Не забудьте проверить /etc/default/cacerts для:
# enable/disable updates of the keystore /etc/ssl/certs/java/cacerts
cacerts_updates=yes
Чтобы удалить cert:
sudo rm /usr/share/ca-certificates/test/test.loc.crt
sudo rm /etc/ssl/certs/java/cacerts
sudo update-ca-certificates --fresh --verbose
2 ответа
В случае, где Вы никогда не добавляете самоссылку (чтобы быть определенными позже) объекты, Ваша структура данных описывает направленный граф без петель ( http://en.wikipedia.org/wiki/Directed_acyclic_graph ), где каждый экземпляр класса IAmCircular описывает узел с рядом прямых узлов преемника = Дети.
Принятие предварительного условия, что до этого момента, никакой цикл не был создан, функция, которую Вы хотите, PerformCircularReferenceCheck, должно только проверить, достижимо ли "это" от "цели". Если это, это должно возвратить исключение.
мудрая теория Сложности, эта проблема является возможностью соединения ST ( http://en.wikipedia.org/wiki/St-connectivity ) и завершена для класса NL ( http://en.wikipedia.org/wiki/NL_ (сложность) ), даже когда Вы ограничиваете вход графами без петель (который является Вашим случаем).
, В частности, теорема Savitch ( http://en.wikipedia.org/wiki/Savitch%27s_theorem ) уступает конструктивному дорогу для создания O (log^2 n) алгоритм пространства (работающий вовремя O (n^2)) для него, где n является количеством узлов.
кроме того, будучи полным NL, маловероятно, что там существует алгоритм, который работает в пространстве O (зарегистрируйте n) (т.е. используйте только постоянное количество указателей на узлы), так как это подразумевало бы маловероятный NL = L.Править: в частности, маленькие изменения алгоритма зайца и черепахи, предложенного кем-то, не работали бы (потому что они используют слишком мало пространства).
я рекомендовал бы реализовать тривиальный O (n) время, O (n) алгоритм пространства, который генерирует для "цели" его группу преемников (рекурсивно) и проверяющий, появляется ли "это" в этом наборе.
Быть осторожной, явная конструкция набора важна. Иначе, если Вы просто рекурсивно проверяете, достижимо ли "это" каким-либо преемником "цели", Вы рискуете работать в экспоненциальное время.
я рекомендовал O (n) time/O (n) алгоритм пространства, потому что асимптотически лучше, чтобы можно было сделать мудрый временем, и Вы уже используете O (n) пространство для Вашей структуры данных.
Повторяющееся решение состоит в том, чтобы определить набор R (достижимый) и CR (дети Достижимых).
Вы запускаете с R = {this} и CR = {this.children}.
На каждом шаге, Вы проверяете, содержит ли CR this (или target, в зависимости от Вашей точной цели). В противном случае Вы добавляете CR к R и устанавливаете CR на детей CR и удаляете элементы R от CR.
, Если CR становится пустым, R является полным набором элементов, достижимых от this.