Предполагается, что существует изменяющийся во времени график с N узлами с именем a1,a2,...,an и сериями контактов как t node1 node2, что означает node1 контактов с node2 в момент времени t
Предполагаемый узел a1 несет сообщение (на графике имеется только одна копия сообщения), со времени 0, с сколькими узлами может соприкасаться сообщение максимум за время T?Сообщение может быть свободно передано другому узлу в любое время.Например, a1 может выбрать передачу в a2 в момент 2 или сохранить сообщение до тех пор, пока a1 не свяжется с a3 и не передаст его в a3.
Вотпример, чтобы сделать это более понятным.Для графика с 6 узлами и рядами контактов:
1 a1 a2 2 a1 a3 3 a1 a4 4 a3 a5 6 a3 a6 10 a4 a3
В течение времени 0~10 сообщение можетне более 4 узлов: a2,a3,a5,a6 с сообщением, переведенным с a1 на a3 во время 2.
Имейте в виду временные ряды.Здесь a1 переносит сообщение, но передает сообщение на a3 во время 2.Тогда в момент времени 3 узел a1 не имеет сообщения, поэтому сообщение не может связаться с a4.Если a1 сохраняет сообщение во время 2 вместо перевода на a3, сообщение связывается со списком a2,a3,a4,a3.Набор контактов будет {a2,a3,a4} с размером 3, который меньше, чем 4.
Как я могу получить самый большой набор контактных узлов?Или просто число?
В настоящее время я получаю его с помощью рекурсивного алгоритма, но стоимость невыносима, когда T велико.