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

Используя новый универсальный алгоритм, Карлос Гестрин (Carlos Guestrin), профессор компьютерных наук и машинного обучения, вместе с командой студентов составили список 100 блогов в интернете, на которых, по их мнению, можно быстрее всего получить актуальные новости в интернете, пишет ScienceDaily. Список включает хорошо известные блоги, такие как как Boing Boing, и менее известные, например, Watcher of Weasels и Don Surber. В ходе выборки из 45 тыс. блогов, активно использующих ссылки на другие ресурсы, оценивалась скорость появления новости.

Но чтение даже 100 блогов, многие из которых имеют многочисленные сообщения, может быть слишком трудоемким. Исследователи опять воспользовались тем же алгоритмом, чтобы составить список самых "быстрых" блогов, на которых находилось только 5 тыс. сообщений. Этот список отличался от предыдущего наличием большего числа блогов, кратко излагающих основную суть новостей, таких, как The Modulator и Anglican predominating.

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

"Ничто не свидетельствует о гибкости Cascades лучше, чем его возможности по решению этих двух трудных и, казалось бы, различных проблем", - говорит Рэндал Брайант (Randal Bryant), декан факультета компьютерных наук университета Карнеги-Меллон. По его мнению, компьютерные специалисты все чаще разрабатывают универсальные методы для решения совершенно различных проблем.

Работа над алгоритмом Cascades началась в 2004 г. Первоначально алгоритм был адресован разработчикам беспроводных сенсорных сетей. Данные сети могут потенциально отслеживать такие показатели, как качество воды, температура зданий, степень загрязнения озер водорослями, структурная целостность мостов и проч. Во всех этих случаях большие проблемы создает размещение неверного числа датчиков в неправильном месте.

Алгоритм позволяет оптимизировать размещение датчиков, оценивая субмодулярность, то есть эффект добавления датчиков в сети меньшего или большего размера. Например, добавление одного датчика в сеть из 5 датчиков оказывает больший эффект, чем в сеть из 10 тыс. датчиков.