МТИ: характеристики сети можно с большой точностью оценить обходом наугад
Эта способность играет роль в решении ряда коллективных задач, в частности, в процедуре голосования при выборе нового места для строительства муравейника.
Ученые лаборатории искусственного интеллекта МТИ подтвердили гипотезу биологов, выяснив, что исследование среды методом случайного блуждания позволяет точно оценить ее населенность. При этом скорость выполнения оценки приближается к максимальной теоретически возможной.
Результаты исследования применимы в анализе социальных сетей, в разработке систем коллективного принятия решений для групп роботов и в проектировании самоорганизующихся сетей, например, недорогих датчиков, рассеянных в труднопроходимой среде.
Исследователи доказывают, что метод случайного блуждания, когда условный исследователь обходит, возможно, ограниченную территорию, позволяет выяснить характеристики всей сети в целом с такой же точностью и быстротой, что и метод случайной выборки, когда берется наугад несколько ячеек сети и в каждой подсчитывается число муравьев. Последний, отмечают авторы, применим не всегда: к примеру, если нужно оценить, какая доля участников социальной сети считают себя приверженцами той или иной политической партии, случайной выборкой это сделать нельзя, если нет полного списка участников сети - можно лишь выбрать кого-то из них и проследить его связи.
