Управление движением ресурса

Реализация рекурсивных запросов

В больших сетях яркость может растекаться от каждой вершины неограниченно во все стороны. Чтобы локализовать область поиска и управлять движением «пятна яркости» в сети, используются рекурсивные запросы. Под рекурсивным запросом будем понимать многократный запрос, входное множество вершин которого изменяется в зависимости от полученного ответа по одному из наперед заданных правил. Глубина рекурсии может варьироваться от запроса к запросу.

Входным множеством вершин очередного запроса в рекурсии не обязательно должно быть выходное множество от предыдущего запроса, то есть множество вершин, входящих в ответ на предыдущий запрос. Каждое новое входное множество состоит из предыдущего входного множества, подвергнутого определенным изменениям. Эти изменения могут быть двух видов.

I. Добавление одной или нескольких вершин из выходного множества предыдущего запроса. Обозначим количество добавляемых вершин через k+: k+ = 1, 2, … l — l*, где l — количество вершин в ответе, l* - мощность пересечения входного и выходного множества. Этот тип изменений соответствует ситуации, когда самый ожидаемый (вероятный) ответ на поставленный запрос является удовлетворительным, но его нужно расширить и/или уточнить.

В таком случае из множества вершин, входящих в ответ, выбираются некоторые дополнительные вершины (вместе со своим ресурсом) и добавляются в исходное множество вершин, участвующих в запросе. После чего снова происходит увеличение проводимостей соответствующих ребер, и весь процесс перераспределения ресурса повторяется заново — для нового начального состояния.

Количество новых запросов, которые возможно сгенерировать таким способом, составит: N+ = .

II. Удаление одной или нескольких вершин из входного множества предыдущего запроса. Количество удаляемых вершин обозначим через k-: k- = 1, 2, … m.

Этот вид изменений входного множества может преследовать различные цели.

II a) Удаляются вершины из пересечения множеств вопрос-ответ, т. е. входного и выходного множеств предыдущего запроса. Такие изменения предназначены для отсекания самого очевидного ответа и поиска других, менее очевидных. То есть, чтобы получить заведомо «нетривиальный» ответ, сначала нужно узнать ответ тривиальный, и только затем его отсечь.

Количество удаляемых вершин может изменяться от 1 до l*, где l* - мощность пересечения множеств запроса и ответа.

Общее количество запросов, сгенерированных этим правилом, будет:

.

II b) Удаляются вершины из предыдущего входного множества, которых не оказалось в множестве выходном. Эти изменения производятся, если нужно создать длинные ассоциативные цепочки, — создать движение яркости сквозь сеть. Чем меньше вершин из предыдущего входного множества перейдет в следующее, тем быстрее будет передвигаться «пятно яркости» по сети, охватывая каждый раз новые участки. Если же основную массу из входного множества не трогать, пятно яркости будет блуждать около фиксированного центра. С помощью этого правила можно составить.

Итоговые формулы для N+ и N-:N+ = ,.

Комбинируя все возможные сочетания добавления и удаления вершин, получим N = различных множеств, каждое из которых претендует на то, чтобы быть входным множеством запроса на следующем шаге рекурсии.