Лекция 8

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

Пример доказательства NP-полноты с помощью введения ограничителя.

Задача УПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВ.

Условие:Задано конечное множество заданий T. Для каждогоtTзадано целое числоr(t)0– время готовности, когда задание может начать обрабатываться, директивный срокd(t)N₊₀, когда должно быть завершено задание, длительностьl(t)N₊₀– время обработки задания.

Вопрос:Существует ли дляTдопустимое расписание, т.е. такая функция: TN₊₀со следующими свойствами:

1) (t)  r(t)

2) (t)+l(t)  d(t)

3)  t’T t’t  (t’)+l(t’)(t) или (t)+l(t)(t’).

(Другими словами, задание tвыполняется с момента времени(t)до момента(t)+l(t), оно не может быть начато ранее моментаr(t), должно быть закончено не позднееd(t), и временной интервал выполнения заданияtне может перекрываться с временным интервалом другого заданияt’)

Докажем, что данная задача NP-полная. Используя метод локальной замены, сведём её кNP-полной задаче РАЗБИЕНИЕ.

Пусть индивидуальная задача РАЗБИЕНИЕ задаётся конечным множеством Aи размером всех элементовs(a)(aA); пусть значение. В качестве базисных модулей данной индивидуальной задачи выступают отдельные элементыaA.Пустьat_a, r(t_a)=0, d(t_a)=B+1, l(t_a)=S(a).В качестве ограничителя возьмём ещё одно заданиеt, такое, чтоr(t)=B/2,d(t)=(B+1)/2, l(t)=1.

Подобное преобразование, очевидно, требует полиномиального времени. Ограничения, которые накладывает дополнительное задание t, носят двоякий характер. Во-первых, этот ограничитель не позволяет строить расписание, еслиBнечётно (в этом случае и исходная задача разбиение не имеет решения), т.к. в этом случаеr(t)=d(t) иtне может быть включено в расписание. Поэтому в дальнейшем мы будем рассматривать только ситуацию, когдаBчётно. Тогда мы имеем для ограничителяtследующее значениеr(t)=B/2, d(t)=r+1. Из этого свойства следует, что(t)=B/2. Отсюда время, доступное для обработки всех остальных заданий, делится на 2 блока, как это указано на рисунке:

Таким образом, задача составления расписания превращается в задачу выбора подмножества заданий, которые будут выполняться раньше задания t,и подмножества заданий, которые будут выполняться послеt. Такой выбор возможен только в том случае, если мы найдём множествоA’такое, что, таким образом, для рассматриваемой индивидуальной задачи РАЗБИЕНИЕ, искомое множествоA’существует тогда и только тогда, когда для соответствующей индивидуальной задачи УПОРЯДОЧИВАНИЕ ВНУТРИ ИНТЕРВАЛОВ существует допустимое расписание, что и доказываетNP-полноту.

Метод построения компонент

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

ПРИМЕР

Докажем NP-полноту задачи УПОРЯДОЧИВАНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ.

Условие: Задано множествоTзаданий, каждое из которых имеет длительность 1, для каждого задания задан директивный срокd(1)N₊₀; частичное упорядочивание (<·) на множестве Tи целое неотрицательноеk|T|.

Вопрос:Существует ли расписание : T{0,1,2, … ,|T|-1}, такое, что

tt’(t)(t’)

(t)<(t’) если t <· t’

|{tT : (t)+1d(t)}|  k

Докажем NP-полноту задачи.

Пусть граф G=(V, E) и положительное целое числоJ(J|V|) образуют индивидуальную задачу из массовой задачи КЛИКА. Соответствующая индивидуальная задача из задачи УПОРЯДОЧИВАНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ имеет множество заданийT=VE, величинаk=|E|-J(J-1)/2.Частичное упорядочивание заданий определяется следующим образом:

t <· t’  tV, t’Eи вершинаtинцидентна ребруt’;

Таким образом, компонента, соответствующая каждой вершине, состоит из единственного задания с директивным сроком |V|+|E|,а компонента, соответствующая каждому ребру, состоит из единственного задания с директивным срокомJ(J+1)/2.Благодаря наличию частичного порядка на множествеT в искомом расписании задание, соответствующее ребру, будет следовать за заданиями, соответствующими его вершинам. Поэтому задания, для которых имеется опасность запаздывания, обязательно соответствуют рёбрам. Искомое расписание удобно представить себе схематически следующим образом рисунком:

Первые две части из четырёх частей расписании можно рассматривать как компоненту выбора клики. До этого срока может быть выполнено не более J(J+1)/2заданий. Для того чтобы число запоздавших заданий не превосходило заданной вершиныk, в начале должны стоять, по крайней мере,J(J-1)/2заданий, соответствующих рёбрам. Однако если задание, соответствующее ребру выполняется ранее своего директивного срока, то и задания, соответствующее его концевым вершинам должны быть закончены раньше этого срока. Минимально возможное количество вершин, которые могут быть инцидентныJ(J-1)/2различным рёбрам, равноJ(причём такая ситуация возможна только тогда, когда эти рёбра образуют полный граф на указанныхJвершинах). Отсюда следует, что среди заданий, выполняющихся ранее директивного срока, должно иметься, по крайней мере,Jзаданий, соответствующих вершинам. Однако до директивного срока заданий, соответствующих рёбрам, может быть выполненоне болееJ(J+1)/2-J(J-1)/2 = Jзаданий, отвечающих вершинам. Следовательно, в любом таком расписании до директивного срока заданий, соответствующих рёбрам, должно закончитсяровноJзаданий, соответствующих вершинам, ировноJ(J-1)/2– рёбрам, что соответствует клике исходного графа G. Обратно, если клика существует, то расписание можно построить способом, указанном на рисунке.

Применение теории NP-полноты для анализа задач.

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

В ситуации, которая описана, нельзя полагаться на интуицию, поскольку очень часто NP-полные задачи при незначительном изменении условий превращаются в полиномиально разрешимые. Например, задачи 3-ВЫП и 3-СNP-полны, а близкие им задачи 2-ВЫП и ПАРОСОЧЕТАНИЕ разрешимы за полиномиальное время. Таким образом, при анализе задач лучше пользоваться двухсторонним подходом: с одной стороны пытаться найти полиномиальный алгоритм, а с другой пытаться доказатьNP-полноту задачи. Мы рассмотрим ситуацию, когдаNP-полнота задачи доказана. Далее будет рассмотрен указанный двухсторонний подход для более глубокого анализа этой задачи.

Анализ подзадач.

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

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

Очевидно, что если задача ПявляетсяNP-полной, то её подзадачи могут быть какNP-полными, так и полиномиально разрешимыми. В предположении, чтоPNP, можно считать, что подзадачи любойNP-полной задачи лежат по разные стороны воображаемой границы, которая разделяет полиномиальные и труднорешаемые задачи. На самом деле, при анализе подзадач лучше в каждый момент представлять себе «пограничную зону» между двумя типами задач. С одной стороны от неё, лежатNP-полные задачи, с другой стороны – полиномиально разрешимые, в самой же пограничной зоне лежат задачи,NP-полнота, которых остаётся под вопросом.

ПРИМЕР.

Задача РАСПИСАНИЕ С ОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ.

Условие:Задано множествоTзаданий с длительностью выполнения 1. Задан частичный порядок на множестве заданий. Указано число процессоровmи общий директивный срокDN.

Вопрос:Существует ли такое расписание :T{0,1,2,…,D}, что для каждогоi{0,1,2,…,D}|{tT:(t)=i}|mи еслиt <·t’,то (t)<(t’).

В качестве гипотетического приложения задачи рассмотрим следующую ситуацию. Предположим, что вы получили задание помочь поступившим первокурсникам составлять план своих занятий на всё время обучения. В данной ситуации, студенты представляют вам список всех курсов, которые они намереваются прослушать – это и есть множество заданий T, числоm– это максимальное количество курсов, которые они могут слушать одновременно. ВеличинаD– это количество семестров обучения. Предполагается, что университет достаточно большой, так что каждый курс лекций читается каждый семестр, и ни какие два курса не пересекаются по времени. Однако некоторые курсы являются вспомогательными для других и поэтому должны быть прослушаны раньше, эта особенность создаёт частичный порядок. Предположим, что мы хотим написать программу на компьютере для решения задачи. Задача расписания соотношения предшествования являетсяNP-полной. Тем не менее, возможно найдутся некоторые естественные ограничения приемлемые для большинства студентов и облегчающее решение задачи. Поскольку работоспособность студентов ограничена, то вполне вероятно, что величинуmможно сверху ограничить каким либо числом. Вспомогательные курсы лекций, также могут удовлетворять дополнительным ограничениям. Например, некоторые студенты могут выбрать очень разнообразную программу обучения, при этом ни один из выбранных ими курсов не потребует вспомогательных курсов, в этом случае условие порядка отсутствует. В некоторых случаях может казаться, что для каждого курса лекций требуется только один явный вспомогательный курс, а все остальные курсы, вспомогательные для первого, являются вспомогательными и для явного вспомогательного. В данном случае, частичный порядок представляет собой древовидную структуру. Возможны и другие ограничения. Если рассматривать только эти два ограничения (на количество слушаемых курсов и тип частичного порядка), то можно представить состояние знаний о семействе подзадач задачи РАСПИСАНИЕ С ОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ в виде следующего рисунка:

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