Ученые ННГУ занимаются поиском быстрых алгоритмов дискретной оптимизации

Исследования поддержаны грантом РНФ

Учеными Университета Лобачевского под руководством ведущего научного сотрудника ИИТММ ННГУ, профессора Института математики Уорикского университета (Великобритания) Лозина Вадима Владиславовича реализуется научный проект «Алгоритмические, сложностные и структурные вопросы теории графов и дискретной оптимизации».

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

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

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

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

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

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

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

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

Тем не менее, остается открытым вопрос: «а существуют ли в принципе быстрые алгоритмы для «неподдающихся» задач или такие эффективные алгоритмы пока еще не найдены?» Большинство специалистов склоняется к мнению, что таковых алгоритмов для большинства неподдающихся задач не существует, поэтому их никто никогда не сможет найти. Если будет доказана известнейшая гипотеза «P ≠ NP», то это будет означать, что это действительно так.

Проблема «P = NP?» была сформулирована в 1971 г. С.Куком, но до сих пор никто не доказал P = NP или P ≠ NP. Это одна из самых главных открытых проблем в теоретической информатике. Математический институт Клэя в 2000 г. назвал ее первой среди семи нерешенных важнейших «Задач тысячелетия». 

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

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

 
По теме
Порядка 3 миллионов рублей присуждено потребителям по 76 искам, рассмотренных судами в Нижегородской области за первое полугодие 2018 года, сообщает пресс-служба управления Роспотребнадзора.
20.07.2018
 
Доследственная проверка организована по факту гибели 1,5-годовалой девочки в Оке - Время Н Правоохранители начали доследственную проверку по факту гибели 1,5-годовалой девочки в реке Ока около микрорайона Юг днем 19 июля, сообщает пресс-служба СУ СК РФ по Нижегородской области.
19.07.2018 Время Н
Дзержинский городской суд вынес приговор 42-летнему местному жителю. Он признан виновным в том, что сел пьяным за руль автомобиля и совершил ДТП, в котором погиб его знакомый.
19.07.2018 Дзержинск.рф
День торта отмечается 20 июля - Дзержинск.рф   Впервые праздник провел в 2009 году «Миланский Клуб» Королевства Любви – сообщества творческих личностей, которых объединила дружба и общие взгляды на жизнь.
20.07.2018 Дзержинск.рф
  27-29 июля в Нижнем Новгороде пройдет Приволжская воздухоплавательная фиеста, которая возрождается благодаря усилиям клуба воздухоплавателей «SharNN» и нескольким компаниям-партнерам,
20.07.2018 Нижегородские новости
Профильный комитет ЗС НО одобрил увеличение расходов облбюджета-2018 на 266 млн рублей - НИА Нижний Новгород Фото: НИА "Нижний Новгород" НИА "Нижний Новгород" - Алёна Вдовиченко Комитет Законодательного собрания Нижегородской области по бюджету и налогам одобрил увеличение расходов областного бюджета на 266 млн рублей.
19.07.2018 НИА Нижний Новгород
Международный день шахмат отмечается 20 июля Шахматы – увлекательное занятие, которое требует от игроков сосредоточия внимания, четкого логического мышления и умения видеть перспективу действий.
20.07.2018 Дзержинск.рф
Работы по подготовке объектов ЖКХ ведутся в плановом порядке. Заменены 2 котла на котельной ЦРБ, ремонт теплотрассы котельной №1, планово-предупредительные ремонтные работы в стадии завершения.
20.07.2018 Администрация Большеболдинского района
Нижний Новгород. 20 июля. НТА-Приволжье – Более 60 тысяч квадратных метров дорожной поверхности будет отремонтировано на улице Удмуртской в Ижевске.
20.07.2018 НТА-Приволжье