Карты метро и нейронные сети. Теория графов

Клауди Альсина

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

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

Схема нейронной сети, подобной тем, что используются в информатике. Входные сигналы (обозначены стрелкой справа) получаются рецепторами (круги в правой части схемы), которые передают сигналы нейронам (круги в центре схемы), а те в свою очередь выдают результат (круги в левой части схемы), на основе которого формируется выходной сигнал (обозначен стрелкой слева).

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

Понятия и результаты, полученные в теории графов, — мощный инструмент организации сложных систем. Представьте социальные графы в Facebook или Twitter: число вершин этих графов равно числу пользователей, а многочисленные ребра представляют отношения между ними.

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

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

Графы и линейное программирование

В 40-е годы XX века появилось так называемое линейное программирование — теория, сыгравшая ключевую роль в объединении науки управления и ставшая частью раздела «Исследование операций».

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

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

Линейное программирование также связано со статистикой, теорией принятия решений и теорией игр.

Изначально линейное программирование не располагало мощными средствами вычислений, но со временем рост возможностей компьютеров способствовал бурному развитию этой дисциплины. Подсчитано, что современные организации тратят от 50 до 90 % вычислительных мощностей на решение задач линейного программирования. Среди тех, кто внес важный вклад в развитие линейного программирования, стоит выделить Джона фон Неймана, Леонида Канторовича, Тьяллинга Купманса, Джорджа Данцига, а также Нарендру Кармаркара — блестящего исследователя, работавшего в американской телефонной компании AT&T Bell, который изобрел радикально новый алгоритм решения задач линейного программирования.

Пионер линейного программирования математик Джон фон Нейман общается со студентами Принстонского университета. 1947 год.

Чтобы читатель понял смысл линейного программирования, рассмотрим небольшой пример, который отлично иллюстрирует задачи, решаемые в этой дисциплине.

Рассмотрим компанию, которая производит два типа напитков А и В, в которых сочетаются два ингредиента а и Ь. Прибыль от продажи единицы напитка А составляет 6 евро, от единицы напитка В — 5 евро. В рассматриваемый период на складе компании находится 1000 литров а и 3000 литров Ь. При производстве напитка А нужно смешать 0,3 литра а и 0,5 литра Ь, при производстве В — 0,3 литра a и 0,7 литра Ь. Как получить максимальную прибыль?

* * *

ДЖОРДЖ ДАНЦИГ (1914–2005)

Этот блестящий математик, который много лет преподавал в Стэнфордском университете, считается отцом линейного программирования наряду с Леонидом Канторовичем. Данциг разработал симплекс-метод, который лег в основу практического применения линейного программирования. О Данциге рассказывают, что как-то раз он опоздал на занятие по статистике, которое вел Ежи Нейман, и подумал, что две задачи, написанные на доске, — это домашнее задание. Оно оказалось трудным, но Данцигу удалось решить его. Нейман был потрясен: 25-летний студент справился с задачами, которые считались нерешаемыми. Если бы Данциг знал это, то никогда не попробовал бы решить их.

* * *

Условия задачи сведены в следующую таблицу.

Алгоритм решения подобных задач в общем виде выглядит так:

1. Какими ресурсами мы располагаем?

2. Каков объем каждого ресурса?

3. Какие продукты нужно изготовить?

4. Сколько ресурсов требуется для изготовления каждого продукта?

5. Каковы неизвестные величины?

6. По какой формуле рассчитывается прибыль?

Обозначим за х объем выпуска напитка А, за у — объем выпуска напитка В, для изготовления которых нам потребуются ресурсы а и Ь. Формула расчета прибыли, которую нужно максимизировать, такова:

6х + 5у.

Однако на переменные х и у накладываются дополнительные условия, вызванные ограниченностью ресурсов:

x >= 0,

у >= 0,

0,5x + 0,3у =< 1000,

0,5x + 0,7у =< 3000.

Мы составили математическую модель задачи, и теперь необходимо найти максимальное значение выражения 6х + 5у для пары значений (х, у), которые будут удовлетворять четырем вышеперечисленным ограничениям. Построим область допустимых решений, которую образуют все точки (х, у) в декартовой системе координат, удовлетворяющие условиям задачи.