«Решать такие задачи полным перебором вариантов нельзя»

Что такое теория расписаний, как решение ее задач может помочь в реальной жизни и каким образом связаны непопулярные законы с расписанием транспорта, рассказал в интервью Indicator.Ru Евгений Гафаров, ведущий научный сотрудник Института проблем управления РАН.

Одна и та же задача дискретной математики может быть интерпретирована и как задача о принятии непопулярных законов, и как задача об утилизации химических отходов. Исследователи из Института проблем управления РАН и Университета Магдебурга доказали, что эта задача является NP-трудной — найти приемлемый алгоритм ее решения не удастся без фундаментальных открытий.

— Расскажите, к какому типу задач относится найденная вами?

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

— А какой практический смысл у таких задач?

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

— Опишите подробнее условия вашей задачи.

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

Также эта задача может быть интерпретирована как задача о непопулярных законах. Представим, что правительству необходимо принять ряд законов, каждый из которых ущемляет какие-то группы населения (например, пенсионеров, бизнесменов, учителей или жителей какой-то области). То есть каждый такой закон «нагревает» какие-то группы населения. При этом каждая группа постепенно адаптируется к каждому непопулярному закону и «остывает». У каждой группы населения есть «порог терпения». Если его превысить набором непопулярных законов, то группа «перегревается» и начинает «бунтовать». Правительству необходимо так распределить принятие непопулярных законов во времени, чтобы не превысить «порог терпения» ни у одной группы и при этом принять законы как можно быстрее.

— А как вы пришли к такой формулировке задачи, почему выбрали именно этот практический пример?

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

— Как вы оценивали ограничения для примера задачи о принятии непопулярных законов? Ведь речь идет о довольно размытых параметрах — негативных эмоциях, обстановке в стране.

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

— То, что эта задача сложноразрешимая, означает, что ее вообще нельзя решить?

— Чтобы ответить на этот вопрос, нужно рассказать о сути задач комбинаторной оптимизации. Представьте, что среди множества вариантов выбрать нужно лучший. При этом множество настолько велико, что даже с помощью суперкомпьютера перебрать все варианты за разумное время невозможно. Известный пример из университетского курса — классическая задача о рюкзаке. Вот ее постановка. Дано n предметов. Для каждого предмета определены масса и стоимость. Есть рюкзак вместимостью A килограммов. Необходимо выбрать, какие предметы взять с собой в рюкзаке, так, чтобы их суммарная масса не превышала А килограммов, а суммарная стоимость была максимальной. Эта задача имеет порядка 2ⁿ допустимых решений, и даже для n=200 предметов это уже очень большое число. Даже суперкомпьютер будет перебирать это множество вариантов неприемлемо долго. То есть решать такие задачи полным перебором вариантов нельзя. Цель исследователя — найти такой алгоритм перебора, при котором множество рассматриваемых вариантов будет существенно сокращено, но будет содержать оптимальный вариант.

— И ваша задача относится к тем, для которых такой алгоритм найти нельзя?

— Наша задача относится к классу так называемых NP-трудных задач. Условно задачи комбинаторной оптимизации можно разделить на два класса — полиномиально разрешимые, простые задачи класса P и NP-трудные задачи. Для NP-трудных задач «быстрые» полиномиальные алгоритмы решения неизвестны. Оба этих класса входят в класс задач NP.

Одна из математических «проблем тысячелетия» — определить, равны ли классы P и NP. Ее решение сравнимо по важности с доказательством теоремы Пуанкаре, найденным Григорием Перельманом. Если найти полиномиальный алгоритм хотя бы для одной NP-трудной задачи, то это было бы решением проблемы тысячелетия.

Мы доказали, что задача о переполнении буфера является NP-трудной, то есть для нее сложно построить быстрый алгоритм решения. А это значит, что практические задачи в расширенной постановке придется решать приближенно или же решать их частные случаи.

Понравился материал? Добавьте Indicator.Ru в «Мои источники» Яндекс.Новостей и читайте нас чаще.

Подписывайтесь на Indicator.Ru в соцсетях: Facebook, ВКонтакте, Twitter, Telegram, Одноклассники.