[Перевод] Алгоритмы в реальном мире: Подбор жилья для гостей конференции
Примечание переводчика: В нашем блоге мы рассказываем об облачных сервисах, хостинге и соответствующих технологиях. Кроме того, мы уделяем внимание теме алгоритмов и ранее публиковали материал о поисках простого алгоритма интеллекта. Есть и более приземленные применения алгоритмов — сегодня мы представляем вашему вниманию перевод заметки организаторов конференции HackMIT о том, как с помощью алгоритмов они подбирают жилье гостям мероприятия.
Использовать алгоритмы для решения задач реальной жизни — очень интересное занятие. Организаторы конференции HackMIT, проходящий в Массачусетском технологическом университете, предоставляют хакерам, которые приезжают для участия в событии, жилью на территории кампуса. Студенты, которые впустят к себе постояльцев получают в подарок надувные матрасы — схема работает безотказно.
Сложности
Чтобы обойтись без проблем, нужно сделать так, чтобы требования постояльцев совпадали с тем, что может предложить хозяин — а значит, необходимо каким-то образом осуществлять подбор.
Например, хакер, приезжающий на конференцию, может нуждаться в жилье только ночью с пятницы на субботу, а может на протяжении двух ночей, а хозяева могут иметь возможность разместить разное количество гостей в пятницу и субботу. У постояльца может быть аллергия на домашних животных, жилье некоторых хозяев может быть, наоборот, адаптировано для кошек. Кому-то из гостей не нравится курений, но хозяин может жить в корпусе, где курить разрешено. Существует еще разное отношение к проживанию с людьми противоположного или такого же пола.
Анкета для сбора предпочтений высылается всем гостям и хозяевам жилья, чтобы повысить комфорт пребывания участников конференции и людей, которые их принимают.
Процесс подбора
Изначально организаторы мероприятия подбирали гостям жилье вручную, но при наличии нескольких сотен участников конференции сделать это очень сложно.
Когда речь идет об автоматизации этого процесса, то появляется двудольная проблема подбора. Есть два набора людей, гости и хозяева, представителей которых нужно совместить друг с другом на основе данных опроса. Если один хозяин может принять несколько гостей, то тут вступает в игру дупликация узлов.
Граф совместимости может выглядеть как-то так:
Алгоритм
Простой алгоритм для поиска совпадений может проходить по списку хакеров и связывать их с первым доступным хозяином, удовлетворившим требованиям. Это довольно прожорливый в плане ресурсов алгоритм, но его можно легко и быстро запрограммировать. Если запустить его на тестовых данных, получится что-то вроде этого:
Это максимальное совпадение — в граф нельзя добавить больше совпадений. Однако это не значит, что сюда вошли все возможные варианты совпадений — если поработать получше, то свести можно было бы больше людей.
Чтобы добиться более хороших результатов, понадобится другой алгоритм. Можно взглянуть на проблему выбора, как на проблему максимального потока и использовать алгоритм Эдмондса-Карпа или Хопкрофта-Карпа.
Этот путь гарантирует подбора максимально возможного количества совпадений.
Результаты
Реальные данные говорят о том, что использование хорошего алгоритма позволяет добиться неплохих результатов. В 2015 году в конференции HackMIT приняли участие 359 хакеров, которых разместили уникальных 234 хозяина. Некоторые из хозяев смогли разместить постояльцев на несколько дней, по факту это выразилось в наличии 367 вариантов размещения на каждый день.
Первый не самый оптимальный алгоритм нашел максимальное совпадение для 95% хакеров. Оптимальный алгоритм позволил разместить всех гостей.
