МТИ: характеристики сети можно с большой точностью оценить обходом наугад
МТИ: характеристики сети можно с большой точностью оценить обходом наугад



Источник: MIT


13:07 15.07.2016

|   1714 прочтений



Как предполагают биологи, муравьи оценивают концентрацию своих сородичей поблизости по частоте столкновений с ними при случайном блуждании.

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

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

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

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


Теги: МТИ