<<
>>

Упражнение с решением 2

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

Всего имеется n возможных лекторов, и в неделю с номером i (для i= 1,2,..., 1 ) доступно подмножество L лекторов для проведения лекций.

С другой стороны, каждый проект требует наличия определенной подготовки, чтобы студенты могли успешно завершить его. В частности, для каждого проекта j (для j = 1, 2, ..., p) определено подмножество P лекторов; чтобы завершить проект, студент должен посетить лекцию хотя бы одного из лекторов подмножества P

Итак, задача: для заданных множеств можно ли выбрать ровно одного лектора для каждой из первых l недель семинара, чтобы выбирались только лекторы, свободные в соответствующую неделю, а для каждого проекта j студенты прослу- шали как минимум одного из лекторов соответствующего множества Pj? Назовем ее задачей планирования лекций.

Чтобы прояснить ситуацию, рассмотрим следующий пример. Допустим, £ = 2, p = 3 и доступны n = 4 лектора, обозначенные A, B, C, D. Доступность лекторов определяется множествами L1 = {A, B, C} и L2 = {A, D}. Необходимые докладчики для каждого проекта определяются множествами P1 = {B,C}, P2 = {A, B, D} и P3 = {C, D}. В этом случае ответ для экземпляра задачи будет положительным: в первую не- делю выбирается лектор B, а во вторую лектор D; для каждого из трех проектов студенты посетят лекцию хотя бы одного из необходимых лекторов.

Докажите, что задача планирования лекций является ЖP-полной.

Доказательство. Задача принадлежит NP, так как для заданной последователь- ности лекторов мы можем проверить, что (a) все лекторы свободны в назначенные им недели и (b) что для каждого проекта был выбран хотя бы один из необходимых лекторов.

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

Однако существует менее очевидное представление задачи планирования лек- ций, типичное для широкого диапазона задач на соблюдение ограничений. Это представление было весьма живописно отражено в «Нью-Йоркере» при описании стиля перекрестного допроса адвоката Дэвида Бойеса: во время перекрестного до- проса Дэвид словно неспешно прогуливается со свидетелем по коридору, одновре- менно незаметно закрывая двери. Дойдя до конца коридора, Дэвид поворачивается к свидетелю — и выясняется, что отступать уже некуда. Все двери закрыты1.

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

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

Задача 3-SAT — канонический пример задачи с двухфазной структурой, опи- санной выше: сначала мы перебираем переменные, присваивая каждой true или false; затем перебираем все условия и смотрим, выполняются ли они с выбранны- ми значениями. Эта параллель с задачей планирования лекций уже предполагает естественное сведение, демонстрирующее, что 3-SAT UМ)

В этой ситуации существует достаточное множество с размером 2: можно вы- брать места (: и i4.

(Так как иД не блокируются в lt, а fA iifA не блокируются в

Докажите, что задача отслеживания частот является ХР-полной.

16. Рассмотрим задачу характеристики множества по размерам его пересечений с другими множествами. Имеется конечное множество U размера n, а также набор A1, ..., Am подмножеств U. Также заданы числа c1, ..., cm. Вопрос звучит так: существует ли такое множествоX с U, что для всех i = 1, 2, ..., m мощностьX ∩ А. равна с? Назовем его задачей выведения пересечений с входными данными U, {А.} и {с}.

Докажите, что задача выведения пересечений является ХР-полной.

17. Задан направленный граф G = (V, E) с весами we ребер e E. Веса могут быть отрицательными или положительными. В задаче цикла с нулевым весом тре- буется решить, существует ли в G простой цикл, сумма весов ребер которого равна 0. Докажите, что эта задача является ХР-полной.

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

Состав комитета представлен множеством M = {m1, ..., mn} из n членов. За по- следний год в комитете проводилось голосование по t разным вопросам. По каждому вопросу каждый член комитета мог проголосовать «За», «Против» или «Воздержаться». В результате комитет принимает положительное решение по каждому вопросу, если количество голосов «За» строго превышает количество голосов «Против» (воздержавшиеся не считаются ни за одну из сторон); в про- тивном случае принимается отрицательное решение.

Имеется большая таблица, содержащая данные голосования каждого участника комитета по каждому вопросу. Рассматривается следующее определение: под- множество членов M’ Έ M называется решающим, если при проверке только голосов, поданных членами M’, решение комитета по каждому вопросу будет тем же.

(Иначе говоря, результат голосования членов M’ по каждому вопросу определяет общий результат голосования всего комитета.) Такое подмножество можно рассматривать как своего рода «ближнее окружение», которое отражает мнение комитета в целом.

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

Пример. Допустим, имеются четыре члена комитета и три вопроса. Мы ищем решающее подмножество с размером не более к = 2, а голосование проходило

так:

Вопрос

m2 mз m4
Вопрос 1 За За Воздержаться Против
Вопрос 2 Воздержаться Против Против Воздержаться
Вопрос 3 За Воздержаться За За

В данном экземпляре результат будет положительным, поскольку члены m1 и m3 образуют решающее подмножество.

Докажите, что задача решающего подмножества является ЖР-полной.

19. Предположим, вы консультируете управление порта в маленькой стране на по- бережье Тихого океана. Ежегодный объем сделок исчисляется миллиардами, и доход ограничивается исключительно скоростью разгрузки кораблей, при- бывающих в порт.

Работа с опасными грузами усложняет и без того непростую задачу. Допустим, утром в порт прибывает морской конвой, который привозит n контейнеров с разными видами опасных материалов.

В доке стоят m машин, каждая из ко- торых вмещает до к контейнеров.

Существуют две взаимосвязанные задачи, которые обусловлены разными типа- ми ограничений, действующих при обработке опасных материалов. Для каждой из двух задач выберите один из двух ответов:

• Алгоритм с полиномиальным временем для решения задачи.

• Доказательство ЖР-полноты задачи.

(a) Для каждого контейнера существует заданное подмножество машин, на которых они могут перевозиться. Возможно ли погрузить все n контейнеров на m машин, чтобы ни одна машина не была перегружена, а каждый контей- нер был погружен на машину, для которой разрешена его перевозка?

(b) В другой версии задачи любой контейнер может быть погружен на лю- бую машину, однако некоторые пары контейнеров не могут быть погружены на одну машину. (При контакте содержащихся в них химикатов может про- изойти взрыв.) Возможно ли погрузить все n контейнеров на m машин так, чтобы ни одна машина не была перегружена и никакие два контейнера не грузились на одну машину, если это запрещено правилами?

20. Существует много разных способов формального представления задачи кластери- зации, целью которой является разбиение набора объектов на «похожие» группы. Естественным способом представления входных данных для задачи класте- ризации является множество объектов p1, p2, ..., pn, в котором для каждой пары определяется числовое расстояние d(p, p). (Для расстояний устанавливают- ся требования: d(p ,, p) = 0; d(p ,, p) > 0 для разных p и p. и симметричность d(p ,∙> pj) = d(pf p ,·).)

Ранее в разделе 4.7 была рассмотрена одна из возможных формулировок задачи кластеризации: разбить объекты на к множеств так, чтобы максимизировать минимальное расстояние между парами объектов из разных кластеров. Как выясняется, задача решается удачным применением задачи о минимальном остовном дереве.

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

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

Тот факт, что новая формулировка обладает слишком большой вычислительной сложностью для оптимального решения, может показаться удивительным (при таком сходстве задач). Чтобы задачу можно было проанализировать в контексте ЖР-полноты, сначала запишем ее в формулировке с принятием решения. Для заданных n объектов pl, p2, ..., pn с расстояниями, определенными выше, и грани- цы B задача кластеризации малого диаметра формулируется следующим обра- зом: возможно ли разбить объекты на к множеств так, чтобы расстояние между любыми двумя точками, принадлежащими одному множеству, не превышало B? Докажите, что задача кластеризации малого диаметра является ЖР-полной.

21. После знакомства с популярной книгой для начинающих предпринимателей вы осознаете, что компьютерная система в вашем офисе нуждается в обновлении. Однако это начинание сталкивается с некоторыми непростыми проблемами. При планировании новой системы необходимо выбрать к компонентов: опера- ционная система, редактор текстов, почтовый клиент и т. д. Для j-го компонента системы существует множество A вариантов; а конфигурация системы состоит из выбора одного элемента из каждого из множеств A1, A2, ..., Ak.

Проблемы возникают из-за того, что некоторые пары вариантов из разных множеств оказываются несовместимыми. Вариант х. A. и вариант х. A. об- разуют несовместимую пару, если они не могут содержаться в одной системе: например, Linux (вариант операционной системы) и Microsoft Word (вариант редактора текстов) образуют несовместимую пару. Конфигурация системы называется полностью совместимой, если она состоит из элементов x1 A1,

x2 A2, ... xk ^ Aк , из которых ни одна пара (х., х.) не является несовместимой.

Теперь мы можем определить задачу полностью совместимой конфигурации. Экземпляр такой задачи состоит из непересекающихся множеств вариантов A p A2, ..., Ak, и множества P несовместимых пар (x,y), в котором x и у являются элементами разных множеств вариантов. Требуется решить, существует ли полностью совместимая конфигурация: выбор элемента из каждого множества вариантов, при котором ни одна пара выбранных элементов не принадлежит множеству P.

Пример. Допустим, к = 3, а множества Av A2, A3 обозначают варианты выбора операционной системы, редактора текстов и почтового клиента соответственно: AY = {Linux, Windows NT},

A2 = {emacs, Word},

A3 = {Outlook, Eudora, rmail}.

Множество несовместимых пар выглядит так:

P = {(Linux, Word), (Linux, Outlook), (Word, rmail)}

В этом экземпляре ответ на версию с принятием решения будет положитель- ным: например, выбор Linux ^ A1, emacs ^ A2, rmail ^ A3 образует полностью со- вместимую конфигурацию в соответствии с предшествующими определениями. Докажите, что задача полностью совместимой конфигурации является NP- полной.

22. Предположим, вы получили алгоритм A — «черный ящик», который получает ненаправленный граф G = (V, E) и число к и ведет себя следующим образом:

• Если граф G не является связным, алгоритм просто возвращает сообщение о несвязности.

• Если граф G является связным и в нем есть независимое множество с раз- мером не менее к, алгоритм возвращает сообщение «Да».

• Если граф G является связным, но в нем нет независимого множества с раз- мером не менее к, алгоритм возвращает сообщение «Нет».

Предположим, алгоритм A выполняется за время, полиномиальное по размеру G и к.

Покажите, как с использованием обращений к A решить за полиномиальное время задачу о независимом множестве: для заданного графа G и числа к со- держит ли граф G независимое множество с размером не менее к?

23. Для множества конечных двоичных строк S= {s,,..., st} строка и называется конка- тенацией по S, если она равна Ваш знакомый рассматривает следующую задачу: для заданных двух множеств конечных двоичных строк A = {ap ..., am} и B = {bv ..., bn} существует ли строка u, которая бы одновременно являлась конкатенацией по A и конкатенацией по B? Ваш знакомый заявляет: «По крайней мере задача принадлежит NP, поскольку для доказательства положительного ответа мне достаточно предъявить такую строку и». Вы указываете (разумеется, вежливо), что такое объяснение совер- шенно несостоятельно: как узнать, что кратчайшая из таких строк и не имеет

длины, экспоненциальной по размеру входных данных, — ведь в этом случае она не может служить сертификатом полиномиального размера?

Но как выясняется, это заявление можно преобразовать в доказательство при- надлежности NP. А именно, докажите следующее утверждение:

Если существует строка u, которая является конкатенацией и по A, и по B, то существует строка, длина которой ограничивается полиномиально по сумме длин строк в A U B.

24. Имеется двудольный граф G = (V, E); допустим, его узлы разбиты на множе- ства X и Y так, что один конец каждого ребра принадлежит X, а другой при- надлежит Y. Определим (a, b)-скелет графа G как множество ребер E' Т E, для которого не более a узлов в X инцидентно ребру в E' и не менее b узлов в Y инцидентно ребру в E'.

Покажите, что для заданного двудольного графа G и чисел a и b задача принятия решения о существовании (a, b)-скелета является NP-полной.

25. Для функций g1, ..., g функция max(gp ..., g) определяется по формуле

[mах⅜, ..., g)] (x) = max⅜(x), ..., g(x)).

Рассмотрим следующую задачу: имеется n кусочно-линейных непрерывных функцийfv ...,f, определенных на интервале [0, t] для некоторого целого t. Так- же задано целое число В. Требуется решить: существуют ли k функций / ,

для которых

f

«

Докажите, что эта задача является NP-полной.

26. Разъезжая по отдаленным частям света, вы со своим другом накопили большую груду сувениров. В то время вы не задумывались над тем, какие сувениры оста- нутся вам, а какие — ему, но, похоже, пришло время разделить приобретения. Один из возможных способов дележа выглядит так: допустим, имеется n объ- ектов 1, 2, ..., n и объект i имеет согласованную ценность x.. (Например, это может быть сумма, за которую его можно продать; будем считать, что у вас с друзьями нет расхождений по поводу оценки). Можно попытаться найти разбиение объ- ектов на два множества, чтобы общая ценность объектов в каждом множестве была одинаковой.

Для этого следует решить следующую задачу численного разбиения. Даны поло- жительные целые числа x1, ..., xn; требуется решить, возможно ли разбить числа на два множества S1 и S2 с одинаковой суммой:

∑> = ∑>,

Покажите, что задача численного разбиения является NP-полной.

27. Рассмотрим следующую задачу. Даны положительные целые числа x1, ..., xn, а так- же числа к и B. Требуется узнать, возможно ли разбить числа {x.} на к множеств S1, ..., Sk так, чтобы квадраты сумм множеств в совокупности давали не более B:

< И.

Покажите, что эта задача является ЖР-полной.

28. Ниже описана разновидность задачи о независимом множестве. Имеется

граф G = (V, E) и целое число к. В контексте этой задачи множество I с Vбудет называться строго независимым, если для любых двух узлов v, и I ребро (v, и) не принадлежит E, а также не существует пути из двух ребер из и в v — то есть не существует узла w, для которого (u, w) E и (w, v) E. Задача о строго не-

зависимом множестве требует решить, существует ли в G строго независимое множество с размером не менее к.

Докажите, что задача о строго независимом множестве является ЖР-полной.

29. Вы строите большую сеть рабочих станций, которая будет моделироваться не- направленным графом G; узлы G представляют отдельные рабочие станции, а ребра представляют прямые каналы связи. Всем рабочим станциям необходим доступ к центральной базе данных с информацией, необходимой для работы базовых функций операционной системы.

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

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

Задача о доминирующем множестве формулируется следующим образом: для заданной сети G и числа к возможно ли разместить к копий базы данных в к разных узлах так, чтобы каждый узел либо содержал собственную копию базы данных либо был соединен прямым каналом с узлом, содержащим копию? Покажите, что задача о доминирующем множестве является ЖР-полной.

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

Для примера рассмотрим традиционную задачу минимизации функции одной переменной — допустим, f(x) = 3 + x - 3х2 на интервале x [0,1]. Производная рав-

на нулю в точке x = 1/6, но это точка максимума, а не минимума функции; чтобы получить минимум, следует выполнить стандартную проверку значений на гра- ницах интервала (причем минимум в данном случае достигается на границе x = 1).

Проверка границы не создает серьезных проблем для функций одной перемен- ной; но предположим, что в задаче требуется минимизировать функцию n пере- менных x1, x2, ..., xn на единичном кубе, где все x1, x2, ..., xn [0,1]. Минимум может достигаться как внутри куба, так и на его границах; и последняя перспектива выглядит устрашающе, так как куб состоит из 2n «углов» (для которых каждое из значений x. равно либо 0, либо 1), а также из различных фрагментов других измерений. Из-за этой сложности книги по матанализу подозрительно нечет- ко излагают этот вопрос при описании многофакторных задач оптимизации.

И тому есть веская причина: минимизация функции с n переменными в еди- ничном n-мерном кубе относится к классу ХР-полных задач. Чтобы это утверж- дение стало более конкретным, рассмотрим специальный случай многочленов с целочисленными коэффициентами по n переменным x1, x2, ..., xn. На всякий случай освежим в памяти терминологию: одночленом называется произведе- ние вещественного коэффициента с и каждой из переменных х., возведенной в неотрицательную целую степень а.; это можно записать в виде (Например, 2л⅛JГj является одночленом).Многочленом называется сумма ко- нечного набора одночленов (например, 2jг,^jГsJгJ +jг,J⅛⅝0je⅛, является многоч- леном).

Задача минимизации многофакторного многочлена формулируется так: для заданного многочлена по n переменным с целочисленными коэффициента- ми и заданной целой границей B возможно ли выбрать вещественные числа x1, x2, ..., xn ^ [0, 1], с которыми многочлен достигает значения < B?

Выберите в этой главе задачу Y, которая заведомо является ХР-полной, и по- кажите, что Y 1. Также имеется библиотека допол- нительных строк Т = {tv t0,..., t } из символов того же алфавита; каждая из этих строк также имеет длину 2f . Пытаясь определить, может ли строка sb следовать прямо за строкой sa в хромосоме, мы проверяем, содержит ли библиотека Т строку tk, чтобы первые ( символов tk совпадали с последними t символами в s , а последние ( символов tk совпадали с первыми ( символами в sь. Если это возможно, мы говорим, что tk скрепляет пару (s , sb). (Другими словами, tk может быть фрагментом ДНК, «перекрывающим» точку перехода sa в sb.)

Нам хотелось бы сцепить все строки S в некотором порядке без перекрытий, так чтобы каждая последовательная пара скреплялась некоторой строкой из би- блиотеки Т. Следовательно, мы хотим упорядочить строки S в виде ^ ,

где iv ..., ;'я — такая перестановка {1, 2,...,;?}, что для всех j = 1, 2,..., п— 1 су- ществует строка tk, скрепляющая пару (⅝ ,⅝ i J. (Одна строка tk может исполь- зоваться для нескольких последовательных пар в конкатенации.) Если это возможно, говорят, что у множества S существует идеальная сборка.

Для заданных множеств S и T задача об идеальной сборке формулируется так: существует ли для S идеальная сборка по отношению к T? Докажите, что задача об идеальной сборке является ЖР-полной.

Пример. Допустим, задан алфавит {А,С,G,Т}, множество S = {ЛG,ТС,ТЛ} и мно- жество Т = {АС,СА,GС,GТ} (так, что каждая строка имеет длину 2f = 2). Тогда ответ на этот экземпляр задачи об идеальной сборке будет положительным: три строки S можно сцепить в порядке ТСАGТА (так, что = s2, = 5, и = s. ).

В этом порядке пара (j ,⅜,) скрепляется строкой СА из библиотеки Т, а пара (jlп ,л„) сцепляется строкой GТ из библиотеки Т.

33. В натуральном хозяйстве люди обмениваются товарами и услугами напрямую, без участия денег как промежуточного шага. Обмен происходит тогда, когда каждая сторона рассматривает множество получаемых товаров как обладающее большей ценностью, чем множество товаров, которые отдаются взамен. Исто- рически человеческое общество обычно переходило от натурального хозяйства к денежной экономике; соответственно различные сетевые системы, экспери- ментирующие с бартером, могут рассматриваться как намеренные попытки вернуться к более ранней форме экономических взаимодействий. При этом обнаруживаются некоторые проблемы, изначально присущие натуральному обмену по сравнению с системами, использующими деньги. Одной из таких трудностей является сложность нахождения возможностей для обмена (даже когда такие возможности существуют).

Для моделирования этих сложностей мы введем концепцию ценности, которая назначается каждым человеком каждому объекту в реальном мире. Предполо- жим, имеется множество из n людей pl, ..., pn и множество m объектов av ..., am. Каждый объект принадлежит одному человеку. Далее, у каждого человека р. имеется оценочная функция v., которая определяется так, что v(а) является неотрицательным числом, которое определяет ценность объекта а. для р., — чем больше число, тем большую ценность объект представляет для человека. Обмен между двумя людьми в такой системе возможен в том случае, если существуют люди р. и р., и подмножества объектов A. и A , принадлежащих р и р. соответственно, так что для каждого участника предпочтительными являются объекты того подмножества, которое ему пока не принадлежит. А точнее, суммарная ценность объектов A. для участника р. превышает сум- марную ценность объектов A,, и суммарная ценность объектов A для участ- ника р превышает суммарную ценность объектов A.. (Обратите внимание: подмножество Ai не обязано включать все объекты, принадлежащие рi; то же относится к A..) A и A. могут быть произвольными подмножествами принад- лежащих им объектов, удовлетворяющим этим критериям.)

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

34. В 1970-е годы ученые, работающие в области математической социологии (включая Марка Грановеттера и Томаса Шеллинга), взялись за разработку мо- делей некоторых видов коллективного человеческого поведения: почему одни модные «фишки» приживаются, а другие быстро отмирают? Почему одни тех- нологические новшества распространяются повсеместно, а другие не выходят за пределы малых групп пользователей? Какова динамика беспорядков и гра- бежей, которые иногда проявляются в поведении разъяренной толпы? Ученые предположили, что все эти ситуации являются примерами каскадных процессов, при которых поведение участника сильно зависит от поведения его близкого окружения; процесс, запущенный несколькими участниками, распространяется на все большее количество людей и в конечном итоге получает очень широкое воздействие. Этот процесс можно сравнить с распространением слухов или эпидемии, передаваемой от человека к человеку.

Рассмотрим простейшую версию модели каскадных процессов. Имеется неко- торое поведение (собирание марок, покупка сотового телефона, участие в бес- порядках), и в какой-то момент времени каждый человек либо принимает в нем участие, либо не принимает. Население представляется направленным графом G = (V, E), в котором узлы соответствуют людям, а ребро (v, w) означает, что че- ловек v влияет на поведение человека w; если человек v участвует в поведении, это также способствует принятию поведения человеком w. У каждого человека w также имеется порог θ(w) [0,1], который имеет следующий смысл: в любой

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

Узлы с низким порогом быстрее «заражаются» поведением, узлы с более вы- соким порогом более консервативны. Узел w с порогом θ(w) = 0 принимает по- ведение немедленно, без влияния окружения. Наконец, нужно договориться по поводу узлов без входящих ребер: будем считать, что они принимают поведение, если θ(w) = 0, и не принимают его при более высоком пороге.

Для заданного экземпляра этой модели распространение поведения может быть смоделировано следующим образом.

Инициализировать все узлы w с θ(w) = 0 как участников поведения.

(Все остальные узлы в исходном состоянии не участвуют в поведении.)

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

Для всех людей, не участвующих в поведении, одновременно:

Если среди узлов с ребрами к w доля участников не менее θ(w) w становится участником Конец Если Конец Конец

Вывести итоговое множество участников

Этот процесс конечен, так как потенциальных участников всего n и при каждой итерации по крайней мере один человек становится участником поведения.

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

Допустим, выбирается множество узлов S (Ξ V, а порог каждого узла в S обнуля- ется 0. (Убедив людей опробовать новый продукт, мы гарантируем их участие.) Затем запускается описанный выше процесс, и мы смотрим, насколько большим окажется итоговое множество участников. Обозначим размер итогового мно- жества участников f (S) (размер записывается в виде функции от S, так как он естественно зависит от выбора S). Величина f (S) может рассматриваться как влияние множества S, так как она отражает распространение поведения, «по- сеянного» в S.

При планировании маркетинговой кампании целью является нахождение мало- го множества S, имеющего как можно большее влияние f (S). Задача максими- зации влияния определяется так: для заданного направленного графа G = (V, E) с пороговыми значениями для каждого узла, параметров k и b существует ли множество S, содержащее не более k узлов, для которых f(S) > b?

Докажите, что задача максимизации влияния является ЖР-полной.

Пример. Допустим, граф G = (V, E) состоит из пяти узлов {a, b, c, d, e}, четырех ребер (a, b), (b, c), (e, d), (d, c), а пороги всех узлов установлены равными 2/3. В этом случае ответ на экземпляр задачи максимизации влияния, определяемой графом G, с k = 2 и b = 5, будет положительным: если выбрать S = {a, e}, то все три остальных узла также станут участниками. (В этой задаче такой вариант выбора S только один; например, если выбрать S = {a, d}, то b и c станут участниками, но e не станет; а если выбрать S = {a, b}, то ни один из узлов c, d или e не станет участником.)

35. Трое ваших друзей работают в крупной компании, занимающейся компьютер- ными играми. Вот уже несколько месяцев они работают над идеей новой игры «Droid Trader!», одобренной руководством компании. За это время им пришлось выслушать множество обескураживающих замечаний, от «Вам придется осно- вательно поработать с отделом маркетинга над названием» до «А может, стоит добавить побольше крови?»

Но сейчас практически все уверены, что игра пойдет в производство, и друзья обращаются к вам за решением последней проблемы: а не получится ли игра слишком простой — игроки слишком быстро освоят ее и им станет скучно?

Вы не сразу разбираетесь в происходящем по их подробному описанию; но если отбросить все космические сражения, поединки и псевдомистицизм в духе «Звездных войн», основная идея выглядит так. Игрок управляет космическим кораблем и пытается заработать деньги, покупая и продавая дроидов на разных планетах. Всего существуют n типов дроидов и k планет. Каждая планета p об- ладает следующими свойствами: на ней продаются s( j, p) > 0 дроидов типа j по фиксированной цене x( j, p) > 0 за штуку, для всех j = 1, 2, ..., n; также существует спрос на d(j, p) > 0 дроидов типа j по фиксированной цене y( j, p) > 0. (Будем считать, что на планете не может быть положительного спроса одновременно с положительным предложением на дроидов одного типа; таким образом, по крайней мере одно из значений s( j, p) и d( j, p) равно 0.)

Игрок начинает на планете s с z единицами денег и заканчивает на планете t; существует направленный ациклический граф G для множества планет, в кото- ром пути s-t соответствуют действительным маршрутам игрока. (Граф G выбран ациклическим, чтобы избежать бесконечных игр.) На протяжении пути s-tP в G игрок может участвовать в сделках следующим образом. Прибывая на планету p в пути P, он может купить до s( j, p) дроидов типа j по цене x( j, p) за штуку (при условии, что у него хватит денег) и/или продать до d( j, p) дроидов типа j по цене y( j, p) за штуку (для j = 1, 2, ..., n). Счет игрока определяется суммой денег, которую он имеет на руках при прибытии на планету t. (Также начисляются дополнительные очки за космические сражения и поединки, но для формули- ровки задачи они нас не интересуют.)

Итак, задача фактически сводится к получению наибольшего результата. Дру- гими словами, для заданного экземпляра игры с направленным ациклическим графом G на базе множества планет, всех остальных параметров, описанных выше, и целевого ограничения B существует ли путь P в G и последователь- ность сделок в P, при которой игрок заканчивает со счетом не менее B? На- зовем этот экземпляр задачей максимального счета в игре Droid Trader!, или сокращенно ЗМСDT!.

Докажите, что задача ЗМСDT! является NP-полной (в предположении P Ф NP). Тем самым вы гарантируете отсутствие простой стратегии для получения высо- кого счета в игре ваших друзей.

36. Даже если вы знаете людей много лет, понять их порой бывает нелегко. Для примера возьмем хотя бы Раджа и Аланис. Ни один из них не относится к «жа- воронкам», но сейчас они ежедневно встают в 6 утра и отправляются на рынок за свежими фруктами и овощами для своего ресторана здорового питания.

Стремясь сэкономить на продуктах, они столкнулись с непростой проблемой. Существует большое множество из n ингредиентов Ip I2, ..., In (пучки зеле- ни, бутылки рисового уксуса и т. д.). Ингредиент I. покупается в единицах по s(j) граммов (с покупкой целого количества единиц) и стоит c(j) долларов за единицу. Кроме того, он остается годным для использования в течение t(j) дней с даты покупки.

За следующие к дней ваши друзья должны подать к фирменных блюд, по од- ному в день. (Выбор дня, в который должно готовиться то или иное блюдо, остается на их усмотрение.) Фирменное блюдо с номером i использует подмно- жество S. Л {IpI2, ..., In} ингредиентов, а именно a(ij) граммов ингредиента I. Наконец, существует еще одно ограничение: постоянные клиенты ресторана останутся постоянными только в том случае, если они получают еду, приготов- ленную из самых свежих продуктов. Для каждого фирменного блюда ингреди- енты Si делятся на два подмножества: те, которые должны покупаться в день изготовления фирменного блюда, и те, которые могут быть куплены в любой день, но их срок годности еще не истек. (Например, салат-месклан с базиликом должен готовиться из базилика, купленного в этот же день, а в соусе песто с рук- колой, базиликом и корнелльским козьим сыром можно использовать базилик, купленный несколько дней назад, если он еще не завял).

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

Итак, задача планирования фирменных блюд выглядит так: для заданной инфор- мации об ингредиентах и рецептах, а также бюджета x возможно ли спланиро- вать к фирменных блюд так, чтобы общая сумма, потраченная на ингредиенты за к дней, не превышала x?

Докажите, что задача планирования фирменных блюд является ЖР-полной.

37. Как ни странно, даже в «Звездных войнах» кроется немало ЖР-полных задач. Рассмотрим задачу, с которой столкнулись Люк, Лея и их друзья на пути со «Звезды Смерти» на скрытую базу повстанцев. Галактику можно рассматривать как ненаправленный граф G = (V, E), в котором узлы представляют звездные системы, а ребро (и, v) обозначает возможность прямого перемещения из и в v. «Звезде Смерти» соответствует узел s, а скрытой базе повстанцев — узел t. Расстояния, представленные ребрами графа, не одинаковы; каждому ребру е назначается целочисленная длина £r >0. Кроме того, некоторые ребра пред- ставляют маршруты, активно патрулируемые имперскими кораблями; соответ- ственно каждому ребру e также назначается целочисленный риск re > 0, который определяет прогнозируемые повреждения от насыщенных спецэффектами космических сражений в случае перемещения по этому ребру.

Самый безопасный маршрут пролегает по дальним секторам Галактики, от одной безопасной звездной системы к другой; но в этом случае топливо у ко- рабля кончится задолго до того, как он доберется до места назначения. Самый быстрый маршрут — рвануть через населенный центр, но тогда придется отби- ваться от слишком большого количества имперских кораблей. В общем случае общая длина любого пути P из 5 в t определяется как сумма длин всех его ребер, а общий риск — как сумма рисков всех его ребер.

Итак, Люк, Лея и компания пытаются решить для этого графа усложненную разновидность задачи о кратчайшем пути: им нужно добраться из 5 в t по пути с разумно малой общей длиной и общим риском. А конкретнее задачу о крат- чайшем галактическом пути можно сформулировать так: для заданной конфи- гурации, описанной выше, и целочисленных ограничений L и R существует ли путь из 5 в t, в котором общая длина не превышает L и при этом общий риск не превышает R?

Докажите, что задача о кратчайшем галактическом пути является ЛP-полной.

38. Рассмотрим разновидность задачи о дереве Штейнера, которую мы будем назы- вать графическим деревом Штейнера. Имеется ненаправленный граф G = (V, E), множество вершин X Л V и число k. Требуется решить, существует ли множество F Л E, содержащее не более kребер, для которого в графе (V,F)Xпринадлежит одной компоненте связности.

Покажите, что задача о графическом дереве Штейнера является ЛP-полной.

39. Задача о направленных непересекающихся путях определяется следующим об- разом: имеется направленный граф G и k пар узлов (5p t), (52, t2), ..., (5k, tk). Требуется решить, существуют ли непересекающиеся по узлам пути P1, P2, ..., Pk, такие, что P идет из 5 в t.

Покажите, что задача о направленных непересекающихся путях является ЛP - полной.

40. Рассмотрим задачу, встречающуюся при проектировании схем широковеща- тельной рассылки в сети. Имеется направленный граф G = (V, E) с узлом r V и назначенным множеством «целевых узлов» T F V - {r}. С каждым узлом v связано время переключения 5 , которое представляет собой положительное целое число.

Во время 0 узел r генерирует сообщение, которое должно быть получено каждым узлом в T. Для этого нужно построить схему, в которой r передает информацию некоторым из своих соседей (последовательно), которые в свою очередь сообщают некоторым из своих соседей и т. д., пока сообщение не бу- дет получено каждым узлом T. На более формальном уровне схема рассылки определяется следующим образом: узел r может отправить копию сообщения одному из своих соседей во время 0; сосед получит сообщение во время 1. В общем случае во время t > 0 любой узел v, уже получивший сообщение, может отправить копию сообщения одному из своих соседей — при условии, что он еще не отправлял копию сообщения в любой из моментов t - 5v + 1, t - 5v + 2, ..., t - 1. (В этом проявляется роль времени переключения: v необходима пауза в 5v - 1 шагов между последовательными отправками сообщения. Если 5v = 1, никакие дополнительные ограничения не добавляются.)

Временем завершения схемы рассылки называется минимальное время t, к кото- рому все узлы T получат сообщение. Задача о времени рассылки определяется так: для входных данных, описанных выше, и границы b существует ли схема рассылки с временем завершения, не превышающим b?

Докажите, что задача о времени рассылки является NР-полной.

Пример. Допустим, имеется направленный граф G = (V, E) с множеством V = {r, а, b, с} и ребрами (r, a), (a, b), (r, с); множество T = {b, с} и время переклю- чения составляет sv = 2 для всех v V. В этом случае схема рассылки с мини-

мальным временем завершения будет выглядеть так: r отправляет сообщение a во время 0; а отправляет сообщение b во время 1; r отправляет сообщение с во время 2; схема завершается во время 3, когда с получает сообщение. (Обра- тите внимание: узел а может отправить сообщение при получении его во вре- мя 1, так как это его первая отправка сообщения; но узел r не может отправить сообщение во время 1, так как sr = 2, а сообщение было отправлено во время 0.)

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

(a) Покажите, что задача о циклическом покрытии может быть решена за полиномиальное время. (Подсказка: воспользуйтесь задачей о двудольном паросочетании.)

(b) Предположим, каждый цикл должен содержать не менее трех ребер. Покажите, что проверка существования такого циклического покрытия для графа G является NР-полной.

42. Компания, занимающаяся проектированием коммуникационных сетей, обра- щается к вам со следующей задачей. Изучается конкретная сеть, состоящая из n узлов и моделируемая направленным графом G = ( V,E). По соображениям от- казоустойчивости G требуется разбить на максимально возможное количество виртуальных «доменов»: доменом в G называется множество X узлов с размером не менее 2, так что для каждой пары узлов u, v ^ Xсуществуют направленные пути из и в v и из v в u, полностью содержащиеся в X.

Покажите, что следующая задача доменной декомпозиции является ХР-полной. Имеется направленный граф G = (V, E) и число k; возможно ли разбить V не менее чем на k множеств, каждое из которых является доменом?

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнение с решением 2:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения