Алгоритмы в реальном мире

Автор оригинала: Anish Athalye
  • Перевод
В нашем блоге мы уделяем внимание теме алгоритмов и ранее публиковали материал о возможности алгоритмизации интеллекта. Есть и более приземленные применения алгоритмов — сегодня мы решили поговорить именно об этом.


/ фото hackNY.org CC

Использовать алгоритмы для решения задач реальной жизни — очень интересное занятие. Организаторы конференции HackMIT, проходящий в Массачусетском технологическом университете, предоставляют хакерам, которые приезжают для участия в событии, жилье на территории кампуса. Студенты, которые впустят к себе постояльцев получают в подарок надувные матрасы — схема работает безотказно.

Чтобы обойтись без проблем, нужно сделать так, чтобы требования постояльцев совпадали с тем, что может предложить хозяин — а значит, необходимо каким-то образом осуществлять подбор. Например, хакер, приезжающий на конференцию, может нуждаться в жилье только ночью с пятницы на субботу, а может на протяжении двух ночей, а хозяева могут иметь возможность разместить разное количество гостей в пятницу и субботу.

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

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

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

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

Реальные данные говорят о том, что использование хорошего алгоритма позволяет добиться неплохих результатов. В 2015 году в конференции HackMIT приняли участие 359 хакеров, которых разместили уникальных 234 хозяина. Некоторые из хозяев смогли разместить постояльцев на несколько дней, по факту это выразилось в наличии 367 вариантов размещения на каждый день.

Первый не самый оптимальный алгоритм нашел максимальное совпадение для 95% хакеров. Оптимальный алгоритм позволил разместить всех гостей.

P.S. Мы стараемся делиться не только собственным опытом работы над сервисом по предоставлению виртуальной инфраструктуры 1cloud, но и рассказывать о различных исследованиях и новинках в смежных областях знаний.

Не забывайте подписываться на наш блог на Хабре, друзья!
  • +10
  • 7,7k
  • 1
1cloud.ru
240,00
IaaS, VPS, VDS, Частное и публичное облако, SSL
Поделиться публикацией

Комментарии 1

    +2
    Я конечно понимаю, что это перевод, но смысл статьи я так и не уловил. Всё сводится к тому, что есть такие алгоритмы которые позволили оптимизировать некой кампании подбор жилья для людей, приезжающих на конференцию. При этом самый простой вариант, не оптимален, а вот если немного подумать и поискать, то можно улучшить качество алгоритма и оптимально разместить всех. Самой полезной частью статьи пожалуй являются 2 ссылки на Wiki.

    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

    Самое читаемое