PNAS: Появилось новое решение одной из 10 самых известных проблем в информатике

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

Сакет Навлаха, доцент лаборатории Колд-Спринг-Харбор, говорит, что задача компьютера — подобрать водителя и пассажира так, чтобы все были довольны.

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

Это одна из 10 самых известных проблем в информатике, — говорит Навлаха.

Навлакха обнаружил проблему в нервной системе: как сделать так, чтобы каждое мышечное волокно управлялось одним нейроном. У взрослых животных такое соответствие есть, а у молодых — нет.

Навлаха нашёл решение этой проблемы в биологии. Он выяснил, что нейроны, которые изначально подключены к одному и тому же мышечному волокну, конкурируют друг с другом за сохранение связи. Проигравшие в этом соревновании могут забрать свои нейротрансмиттеры и участвовать в торгах с другими волокнами. В результате каждый нейрон и каждое волокно обретают партнёра.

Навлаха придумал, как подбирать партнёров за пределами нервной системы.

Он говорит, что это простой алгоритм из двух уравнений: конкуренция между нейронами, подключёнными к одному и тому же волокну, и перераспределение ресурсов.

Алгоритм протестировали в сравнении с другими программами по подбору пар. Он показал отличные результаты: создаёт почти оптимальные пары и оставляет меньше участников без пары. Это может сократить время ожидания пассажиров и уменьшить количество больниц без врачей.

Навлаха отмечает преимущество нового алгоритма — он сохраняет конфиденциальность.

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

Навлаха надеется, что другие разработчики смогут адаптировать этот алгоритм для своих инструментов.

Результаты опубликованы в издании Proceedings of the National Academy of Sciences.

03.09.2024