| 0 |
|
Нахождение наиболее эффективного способа транспортировки объектов в сети — например, по системе автомобильных магистралей США или через Интернет — представляет собой проблему, десятилетиями привлекающую внимание математиков и специалистов по информатике. Традиционным подходом к ее решению является алгоритм максимального потока (max flow), в котором сеть представляется в виде графа с серией узлов или вершин и соединяющих их линий — ребер.
Принимая во внимание, что для каждого ребра (участка дороги или оптического кабеля) имеется максимальная пропускная способность, такой алгоритм пытается найти оптимальную схему пересылки из одного узла в другой без превышения этих ограничений.
Однако, как утверждает Джонатан Келнер (Jonathan Kelner) из лаборатории CSAIL (Computer Science and Artificial Intelligence Laboratory) Массачусетского технологического института (MIT), с ростом сетей, таких как Интернет, решение проблемы оптимального трафика традиционными способами становится неприемлемым из-за быстрого увеличения затрачиваемого машинного времени.
В статье, представленной на Симпозиум по дискретным алгоритмам в Портланде (штат Орегон), он и его коллега Лоренцо Ореччиа (Lorenzo Orecchia), описывает новый теоретический алгоритм, значительно сокращающий число операций, необходимых для решения проблемы максимального потока. Таким образом, нахождение оптимального способа использования пропускной способности становится возможным даже для гигантских графов из миллиардов и триллионов ребер, представляющих Интернет или геном человека.
Прежние алгоритмы max-flow решали проблему поочередно для каждого ребра. Так, для пересылки товаров из пункта А в пункт Б, алгоритм отправлял из по одному пути, доводя его загрузку до максимальной, а затем, по следующему пути. Но в 2011 г. аспирант CSAIL Александр Мадры (Aleksander Madry) вместе с коллегами из Йельского Университета и Университета Южной Калифорнии разработали методику для одновременного анализа всех возможных маршрутов.
Граф в свою очередь представляется как схема с множеством резисторов, и батареей, подключенной к точкам А и Б. Электрический ток не выбирает какой-либо один маршрут, но проходит понемногу через каждый резистор в сети. Таким образом, граф анализируется глобально за один подход.
Техника, предложенная теперь, еще больше уменьшает время решения такой задачи. В отличие от прежних методов, рассматривающих все пути в графе как равноценные, она выделяет те маршруты, на которых образуются заторы. Алгоритм разбивает каждый граф на кластеры хорошо связанных узлов и пути между ними, испытывающие проблемы с проходимостью. Это позволяет сосредоточиться только на проблемных областях и получить почти линейную зависимость между количеством узлов и временем решения задачи.
Такой результат, по мнению независимых экспертов, позволяет рассматривать эту работу как знаменательный прорыв в алгоритмах теории графов и программных методах оптимизации.
Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365
| 0 |
|
