Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

«Мы надеемся, что это дает вам уверенность в достоверности всей информации, которую мы размещаем, – пишет Ланге, – и, может быть, даже вдохновляет остальные организации поднимать планку».

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

Время и пространство – основа всех известных компромиссов в информатике, но последние исследования рандомизированных алгоритмов предлагают нам рассмотреть еще одну переменную – достоверность. Как выразился Майкл Миценмахер из Гарварда, «что мы хотим сделать, так это придумать ответ, который сэкономит вам время и пространство и использует третью переменную – вероятность ошибки». Когда ему предложили привести пример такого компромисса, он ни секунды не сомневался. «Коллега только что предложил игру, в которой нужно выпивать каждый раз, как этот термин появляется на одном из моих слайдов. Вы что-нибудь слышали о фильтрах Блума?»

Чтобы понять суть идеи фильтра Блума, Миценмахер предлагает рассмотреть поисковую систему Google, которая сканирует весь интернет и индексирует каждую страницу. Интернет составляет более триллиона URL-адресов, а средний URL длиной примерно в 77 знаков. Когда поисковый механизм считывает какой-то URL, как он может понять, была ли эта страница ранее обработана или нет? Чтобы просто хранить список всех уже посещенных страниц, требуется огромное пространство, и повторный поиск по этому списку (пусть даже полностью отсортированному) – это кошмар! В данной ситуации можно сказать, что лечение хуже самой болезни. Другими словами, каждый раз проверять, не была ли эта страница уже проиндексирована, будет гораздо более затратным по времени, чем просто индексировать случайную страницу дважды.

Но что, если нам всего-то и нужно знать, что этот URL новый для нас? Вот тут на сцену и выходит фильтр Блума. Названный по имени его создателя, Бёртона Блума, этот фильтр работает по принципу, схожему с тестом Миллера – Рабина: URL подставляется в ряд уравнений, которые, по сути, проверяют «свидетелей» его новизны (вместо того чтобы объявить «n не является простым числом», эти уравнения говорят «я не видел n раньше»). Если вас устроит коэффициент погрешности 1–2 %, хранение полученных результатов в такой вероятностной структуре данных, как фильтр Блума, позволит вам сэкономить очень много времени и пространства. И польза подобных фильтров не ограничивается только поисковыми системами: фильтры Блума интегрированы в большинство современных браузеров для сверки URL-адресов со списком известных вредоносных сайтов, они также являются важной частью пиринговых платежных систем вроде Bitcoin.

По словам Миценмахера, «идея ошибочного компромисса пространства – думаю, основная проблема в том, что люди не связывают это с вычислениями. Они полагают, что компьютер должен просто выдать ответ. Поэтому, когда на лекции, посвященной алгоритмам, вы слышите: "У вас должен получиться один ответ; но этот ответ может быть неправильным", – мне нравится думать, что это заставляет их [студентов] собраться. Думаю, люди просто не осознают, насколько часто они сталкиваются с этим в своей жизни, и не могут принять это».

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

Представьте себе, что вы планируете путешествовать по миру и посетить десять городов. Ваша собственная версия проблемы коммивояжера: вы улетаете и прилетаете в Сан-Франциско и планируете побывать в Сиэтле, Лос-Анджелесе, Нью-Йорке, Буэнос-Айресе, Лондоне, Амстердаме, Копенгагене, Стамбуле, Дели и Киото. Вас не слишком волнует общая протяженность маршрута, но вы, вероятно, стремитесь снизить расходы на поездку. Первое, что стоит здесь отметить: хотя десять городов – это не так уж и много, но количество возможных вариантов маршрута – это 10! (10 факториал) – более 3,5 млн. Иными словами, у вас нет никакой практической возможности проверить каждую комбинацию и выбрать самую низкую цену. Придется получше пораскинуть мозгами.

В качестве первой попытки построить маршрут вы можете рассмотреть самый дешевый рейс из Сан-Франциско (скажем, в Сиэтл), а затем найти самый дешевый рейс оттуда в любой из оставшихся городов (пусть это будет Лос-Анджелес), потом самый дешевый оттуда (например, в Нью-Йорк) и т. д., пока вы не дойдете до десятого города, откуда вам нужно будет лететь обратно в Сан-Франциско. Это пример так называемого жадного алгоритма, который можно еще назвать близоруким: на каждом этапе пути он близоруко выбирает лучший вариант из тех, что под рукой. В теории планирования, которую мы рассмотрели в главе 5, жадный алгоритм – например, выполнение самой простой и занимающей меньше всего времени работы из доступных, не заглядывая далеко вперед, – порой может стать именно тем, что требуется для решения проблемы. В этом случае решение проблемы коммивояжера, которое может предложить жадный алгоритм, не самое плохое, но далекое от лучшего из возможных.

После того как вы построили базовый маршрут, вам стоит проверить возможные альтернативы, меняя последовательность городов, и посмотреть, получается ли лучше. Например, если мы решили сперва лететь в Сиэтл, а потом в Лос-Анджелес, можно попробовать поменять их местами: сначала Лос-Анджелес, затем Сиэтл. Для любого заданного маршрута мы, таким образом, можем переставить местами два города 11 раз. Скажем, мы перепробуем все варианты и выберем тот, который позволит нам максимально сэкономить. С этого момента у нас есть новый построенный маршрут, с которым мы будем работать дальше, и мы можем снова заняться перестановкой, чтобы извлечь какие-то дополнительные выгоды. Этот алгоритм называется «восхождение на холм», поскольку поиск лучших и худших решений среди множества вариантов можно рассматривать как путешествие по холмистой местности с целью взобраться на самую высокую гору.