Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

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

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

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

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

* * *

МАТЕМАТИКИ И ЯИЧНИЦА

В одной из популярных юмористических историй о математиках рассказывается о том, как они пытаются оптимизировать все возможные действия, чтобы максимально снизить объем работы. Один математик подробно объяснил процесс приготовления яичницы: извлечь сковородку из шкафа, включить плиту, поставить сковородку на плиту, налить масло, дождаться, когда сковородка нагреется, разбить яйцо на сковородку, добавить соль… Этого математика спросили: «Что вы будете делать, если плита уже включена и сковородка стоит на конфорке?» Математик ответил: «Выключу плиту и уберу сковородку в шкаф, чем сведу задачу к ранее решенной».

* * *

NP-полные задачи

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

В 1900 году Давид Гильберт представил на Международном математическом конгрессе в Париже список задач, которые он считал наиболее важными для математиков XX века. Спустя сто лет Институт Клэя определил список «задач тысячелетия» и назначил премию в миллион долларов за решение каждой из них. Стоит отметить, что этот престижный институт был основан в 1998 году Аэндоном Клэем, известным предпринимателем и любителем математики. Клэй предложил за решение каждой из задач весьма привлекательную сумму, в отличие от Гильберта, который мог предложить тем, кто решит задачи из его списка, разве что вечную славу.

В списке семи задач тысячелетия первое место занимает именно проблема о равенстве классов сложности Р и NP. Эта задача относится к так называемой теории сложности вычислений. В ней анализируется время, необходимое для решения задачи и подтверждения правильности ее решения.

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

Немецкий математик Давид Гильберт.