P и NP классы задач распознования

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

 

Кафедра «Информационных систем и технологий»

 

 

ЛАБОРАТОРНАЯ РАБОТА № 1

 

 

P и NP классы задач распознования

 

                                                               Выполнил: магистрант

                                                          группы ИСТм-51

                                                          Казаков Константин   

                                                        Проверил: к.т.н., профессор  

                                                        Лиманова Наталья Игоревна

 

2016 г.

Цель работы:  изучить алгоритмы и освоить алгоритмы решения задачи коммивояжера.

 

Упражнение 4.2. Покажите, что нижняя оценка линейного программирования из раздела 4.3.2. не хуже оптимального значения в целочисленной задаче о назначениях.

 

  Дано:

Представим задачу коммивояжера в терминах целочисленного линейного программирования. Введем переменные

Задача коммивояжера может быть записана следующим образом:

при ограничениях

 

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

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

Критерий оптимальности для задачи коммивояжера имеет вид:

Решение:

 

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

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

Исходные параметры модели. Пусть i=1,2,...,m - номера исполнителей, j=1,2,...,n - номера работ. Обозначим через R= r(i,j) - mn матрицу производительностей, элемент которой r(i,j) - есть производительность исполнителя с номером i на работе с номером j.

Варьируемые параметры. Обозначим через X= x(i,j) - mn матрицу неизвестных, элемент которой x(i,j) принимает значение 1, если исполнитель с номером i будет назначен на работу с номером j, и значение 0, в противном случае. Ограничения математической модели

(3)

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

                           F(X) = ∑ ∑ r(i,j) x(i,j) →max              (4)

Задача (1) - (4) называется задачей о назначениях с аддитивным критерием оптимальности. Если в качестве критерия оптимальности выбрать функционал

           F(X) = max r(i,j) x(i,j) → min             (5)

где max берется по всем i=1,2,...,m и всем j=1,2,...n, то такая задача (1)-(3) называется минимаксной задачей о назначениях.

Нетрудно показать (введением фиктивных исполнителей или фиктивных работ), что математическая модель (1)-(3) эквивалентна математической модели (7)-(9):

 

Рассмотрим следующие условия на введенные переменные: 0 ≤ x(i,j) ≤ 1, i=1,2,...,m, j=1,2,...,n.                                                              (10)

Исходя из того, что матрица ограничений условий (7) - (8) является абсолютно унимодулярной (целочисленная матрица называется абсолютно или вполне унимодулярной, если любой ее минор равен 1, -1 или 0), то любой опорный план математической модели (7), (8), (10) является целочисленным, отсюда вытекает эквивалентность математических моделей (1)-(3) и (7)-(9). Кроме того, так как из условий (7) и (8) и условий не отрицательности переменных, автоматически следует, что переменные не могут быть больше 0, исходная математическая модель (1) -(3) эквивалентна (с точки зрения поиска оптимального решения задачи о назначениях) математической модели с ограничениями (7), (8), условиями m=n и ограничениями 0 ≤ x(i,j), i=1,2,...,m, j=1,2,...,n. (11)

Упражнение 4.21. Приведите пример задачи распознавания, которая не принадлежит классу NP (в предположении, что P≠NP).

Дано:

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

Класс NP является более широким. Он включает в себя все задачи распознавания, в которых ответ «Да» может быть проверен за полиномиальное время. Задача принадлежит этому классу, если, даже не умея ее решать, можно “легко” проверить ответ, подглядев его или найдя в интернете. При этом достаточно уметь проверять только ответ «Да». Иногда проверка ответа «Да» может быть легче или сложнее проверки ответа «Нет».

P – класс задач, решаемых за полиномиальное (от размера входа) время. Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д.