Пять типичных задач - Введение: некоторые типичные задачи

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

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

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

Все эти задачи самодостаточны, а побудительные причины для их изучения лежат в области вычислительных приложений. Тем не менее для описания некоторых из них будет удобно воспользоваться терминологией графов. Графы — достаточно стандартная тема на ранней стадии изучения вычислительных технологий, но в главе 3 они будут рассматриваться на довольно глубоком уровне; кроме того, ввиду огромной выразительной силы графов они будут широко использоваться в книге. В контексте текущего обсуждения граф G достаточно рассматривать просто как способ представления попарных отношений в группе объектов. Таким образом, G состоит из пары множеств (V, E) — набора узлов V и набора ребер E, каждое из которых связывает два узла. Таким образом, ребро е ∈ E представляет двухэлементное подмножество V: e = {u, v} для некоторых u, v ∈ V; при этом u и v называются концами е. Графы обычно изображаются так, как показано на рис. 1.3; узлы изображаются маленькими кружками, а ребра — отрезками, соединяющими два конца.

Перейдем к обсуждению пяти типичных задач.

Рис. 1.3. Примеры графов с четырьмя узлами

Интервальное планирование

Рассмотрим очень простую задачу планирования. Имеется некий ресурс — аудитория, суперкомпьютер, электронный микроскоп и т. д.; множество людей обращается с заявками на использование ресурса в течение периода времени. Заявка имеет вид: “Можно ли зарезервировать ресурс, начиная с времени s и до времени f?” Будем считать, что ресурс в любой момент времени может использоваться только одним человеком. Планировщик выбирает подмножество заявок, отклоняя все остальные, чтобы принятые заявки не перекрывались по времени. Целью планирования является максимизация количества принятых заявок.

Более формальная постановка: имеется n заявок с номерами 1, ..., n; в каждой заявке i указывается начальное время s_i и конечное время f_i. Естественно, s_i < f_i для всех i. Две заявки i и jназываются совместимыми, если запрашиваемые интервалы не перекрываются, то есть заявка i приходится либо на более ранний интервал времени, чем у j (f_i ≤ s_i), либо на более поздний интервал времени, чем у j (f_i ≤ s_i). В более общем смысле подмножество A заявок называется совместимым, если все пары запросов i, j ∈ A, i ≠ j являются совместимыми. Целью алгоритма является выбор совместимого подмножества заявок максимально возможного размера.

Пример задачи интервального планирования представлен на рис. 1.4. На диаграмме представлено одно совместимое множество размера 4, и оно является самым большим совместимым множеством.

Вскоре мы увидим, что эта задача может быть решена с применением очень естественного алгоритма, который упорядочивает множество заявок по некоторой эвристике, а затем “жадно” обрабатывает их за один проход, выбирая совместимое подмножество максимально возможного размера. Это типично для категории “жадных” (greedy) алгоритмов, которые мы будем рассматривать для различных задач, — “недальновидных” правил, которые обрабатывают входные данные по одному элементу без сколько-нибудь очевидных опережающих проверок. Когда “жадный” алгоритм находит оптимальное решение для любых конфигураций задачи, это часто выглядит совершенно неожиданно. Впрочем, сам факт оптимальности столь простого решения обычно что-то говорит о структуре нижележащей задачи.

Рис. 1.4. Пример задачи интервального планирования

Взвешенное интервальное планирование

В задаче интервального планирования мы стремились максимизировать количество одновременно принимаемых заявок. Теперь рассмотрим более общую постановку задачи: интервалу каждой заявки i присваивается соответствующий коэффициент (вес) v_i > 0; можно рассматривать его как оплату, которую владелец ресурса получит от i-го претендента при удовлетворении его заявки. Наша цель — найти совместимое подмножество интервалов с максимальным общим весом.

Частный случай, при котором v_i = 1 для каждого i, представляет собой базовую задачу интервального планирования; однако введение произвольных весов существенно влияет на природу задачи максимизации. Например, если значение v₁ превышает сумму всех остальных v_i, то оптимальное решение должно включать интервал 1 независимо от конфигурации полного набора интервалов. Итак, любой алгоритм для решения этой задачи должен быть крайне чувствителен к значениям весов, но при этом вырождаться в метод решения (невзвешенной) задачи интервального планирования, если все значения равны 1.

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

Двудольные паросочетания

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

У этих концепций существует более общее выражение в понятиях теории графов. Для этого будет полезно определить понятие двудольного графа. Граф G = (V, E) называется двудольным (bipartite), если множество узлов V может быть разбито на множества X и Y таким способом, что у каждого ребра один конец принадлежит X, а другой конец — Y. Двудольный граф изображен на рис. 1.5; часто граф, двудольность которого требуется подчеркнуть, изображается именно таким образом — узлы X и Y выстраиваются в два параллельных столбца. Впрочем, обратите внимание на то, что два графа на рис. 1.3 также являются двудольными.

Рис. 1.5. Двудольный граф

В задаче поиска устойчивых паросочетаний результат строился из пар мужчин и женщин. В случае двудольных графов ребра представляются парами узлов, поэтому мы можем сказать, что паросочетание в графе G = (V, E) представляет собой множество ребер M ⊆ E c тем свойством, что каждый узел входит не более чем в одно ребро M. Паросочетание M является идеальным, если каждый узел входит ровно в одно ребро M.

Чтобы убедиться в том, что это представление отражает ту же ситуацию, которая была описана в задаче устойчивых паросочетаний, рассмотрим двудольный граф G' с множеством X из nмужчин, множеством Y из n женщин и ребрами из каждого узла X в каждый узел Y. Тогда паросочетания и идеальные паросочетания G' в точности соответствуют паросочетаниям и идеальным паросочетаниям в множествах мужчин и женщин.

В задаче устойчивых паросочетаний в ситуацию была добавлена система предпочтений. Здесь предпочтения не рассматриваются, но сама природа задачи для произвольных двудольных графов добавляет другой источник сложности: не гарантировано существование ребра из каждого узла x ∈ X в каждый узел у ∈ Y, так что множество возможных паросочетаний имеет весьма сложную структуру. Другими словами, все выглядит так, словно только некоторые комбинации мужчин и женщин желают образовать пары, и мы хотим определить, как составить множество пар в соответствии с этими ограничениями. Для примера рассмотрим двудольный граф G на рис. 1.5; в G существует много паросочетаний, но только одно идеальное паросочетание (а вы его видите?).

Паросочетания в двудольных графах позволяют моделировать ситуации, в которых объекты связываются с другими объектами. Например, узлы X могут представлять задания, узлы Y — машины, а ребра (x_i, у_j) — показывать, что машина у_j способна обработать задание х_i. Тогда идеальное паросочетание описывает такой способ назначения каждого задания машине, которая может его обработать, при котором каждой машине назначается ровно одно задание. Весной на кафедрах информатики часто рассматриваются двудольные графы, в которых X — множество профессоров, Y — множество предлагаемых курсов, а ребро (x_i, у_j) означает, что профессор х_i может преподавать курс у_j. Идеальное паросочетание в таком графе представляет собой связывание каждого профессора с курсом, который он может преподавать, таким образом, что для каждого курса будет назначен преподаватель.

Итак, задача поиска паросочетаний в двудольном графе формулируется следующим образом: для имеющегося произвольного двудольного графа G найти паросочетание максимального размера. Если |X| = |Y| = n, то идеальное паросочетание существует в том и только в том случае, если максимальное паросочетание имеет размер n. Как выясняется, алгоритмические методы, рассматривавшиеся ранее, не позволяют сформулировать эффективный алгоритм для этой задачи. Однако существует очень элегантный и эффективный алгоритм поиска максимального паросочетания; он индуктивно строит паросочетания все большего размера с избирательным возвратом в ходе выполнения.

Этот процесс, называемый приращением(augmentation), является центральным компонентом в большом классе эффективно решаемых задач, называемых задачами нахождения потока в сети.

Независимое множество

А теперь перейдем к чрезвычайно общей задаче, которая включает большинство более ранних задач как частные случаи. Для заданного графа G = (V, E) множество узлов S ⊆ V называется независимым, если никакие два узла, входящие в S, не соединяются ребром. Таким образом, задача поиска независимого множества формулируется так: для заданного графа G найти независимое множество максимально возможного размера. Например, максимальный размер независимого множества для графа на рис. 1.6 равен 4: оно состоит из четырех узлов {1, 4, 5, 6}.

Рис. 1.6. Размер наибольшего независимого множества в этом графе равен 4

Задача поиска независимого множества представляет произвольную ситуацию, в которой вы пытаетесь выбрать некоторые объекты из набора, в то время как между некоторыми объектами существуют попарные конфликты. Допустим, у вас есть n друзей, но некоторые пары терпеть друг друга не могут. Сколько друзей можно пригласить на обед, если вы хотите избежать лишней напряженности? По сути, речь идет о поиске наибольшего независимого множества в графе, узлы которого представляют ваших друзей, а ребра — конфликты в парах.

Задачи интервального планирования и паросочетаний в двудольном графе могут рассматриваться как особые случаи задачи независимого множества. Для задачи интервального планирования определите граф G = (V, E), в котором узлы соответствуют интервалам, а каждая перекрывающаяся пара соединяется ребром; независимые множества в G соответствуют совместимым подмножествам интервалов. С представлением задачи паросочетаний в двудольном графе ситуация чуть менее тривиальна. Для заданного двудольного графа G' = (V', E') выбираемые объекты соответствуют ребрам, а конфликты возникают между двумя ребрами, имеющими общий конец (такие пары ребер не могут принадлежать общему паросочетанию). Соответственно мы определяем граф G = (V, E), в котором множество узлов V эквивалентно множеству ребер E' в G'. Мы определяем ребро между каждой парой элементов V, соответствующих ребрам G' с общим концом. Теперь можно проверить, что независимые множества G точно соответствуют паросочетаниям G'.

Проверка не так уж сложна, но чтобы уследить за преобразованиями “ребра в узлы, узлы в ребра”, придется как следует сосредоточиться³.

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

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

Естественно задать вопрос: можно ли сказать хоть что-нибудь положительное о сложности задачи независимого множества? Кое-что можно: если имеется граф G из 1000 узлов и мы захотим убедить вас в том, что он содержит независимое множество S с размером 100, сделать это будет несложно. Достаточно показать граф G, выделить узлы S красным цветом и позволить вам убедиться в том, что никакие два узла не соединены ребром. Итак, между проверкой того, что множество действительно является большим независимым, и непосредственным поиском большого независимого множества существует огромная разница. На первый взгляд замечание кажется тривиальным (и действительно является таковым), но оно играет ключевую роль в понимании этого класса задач. Более того, как вы вскоре увидите, в некоторых особо сложных задачах даже может не быть простого способа “проверки” решений в этом смысле.

Задача конкурентного размещения

Наконец, мы приходим к пятой задаче, которая базируется на следующей игре для двух участников. Допустим, имеются две крупные компании, которые открывают свои сети кофеен по всей стране (назовем их JavaPlanet и Queequeg's Coffee); в настоящее время они соревнуются за свою долю рынка в некотором географическом регионе. Сначала JavaPlanet открывает свое заведение; затем Queequeg's Coffee открывает свое; потом JavaPlanet; снова Queequeg's, и т. д. Допустим, они должны выполнять градостроительные нормы, согласно которым две кофейни не должны располагаться слишком близко друг к другу, и каждая компания пытается разместить свои заведения в самых удобных точках. Кто выиграет?

Сделаем правила “игры” более конкретными. Географический регион, о котором идет речь, разделен на n зон с номерами 1, 2, ..., n. Каждой зоне i присваивается оценка b_i — доход, который получит любая из компаний, открывшая кофейню в этой зоне. Наконец, некоторые пары зон (i, j) являются смежными, а местные градостроительные нормы запрещают открывать кофейни в двух смежных зонах независимо от того, какой компании они принадлежат (а также запрещают открывать две кофейни в одной зоне). Для моделирования этих конфликтов мы воспользуемся графом G = (V, E), где V — множество зон, а (i, j) — ребро в E, если зоны i и j являются смежными. Таким образом, градостроительные нормы требуют, чтобы полный набор кофеен образовал независимое множество в G.

В нашей игре два игрока P₁ и Р₂ поочередно выбирают узлы в G, игрок P₁ делает первый ход. Набор всех выбранных узлов в любой момент времени должен образовать независимое множество в G. Предположим, игрок Р₂ имеет целевую границу B, и мы хотим узнать: существует ли для Р₂ такая стратегия, чтобы независимо от выбора ходов P₁ игрок P₂ мог выбрать множество узлов с суммарной оценкой не ниже B?

Мы назовем эту формулировку задачей конкурентного размещения.

Для примера возьмем набор данных на рис. 1.7; предположим, игроку Р₂ установлена целевая граница B = 20. В этом случае у Р₂ имеется выигрышная стратегия. С другой стороны, при B = 25 у игрока Р₂ такой стратегии нет.

Рис. 1.7. Экземпляр задачи конкурентного размещения

В этом нетрудно убедиться, изучая диаграмму в течение некоторого времени; но для этого потребуется проверка разных сценариев в виде “Если P₁ ходит так, то Р₂ пойдет вот так; но если P_lпоходит так, то Р₂ ответит так...” И похоже, это обстоятельство является неотъемлемой особенностью задачи: мало того что проверка наличия у P₂ выигрышной стратегии имеет высокую вычислительную сложность; в графе сколько-нибудь значительного размера нам будет трудно даже убедить вас в наличии у Р₂ выигрышной стратегии. Не существует короткого доказательства, которое можно было бы продемонстрировать; вместо этого приходится приводить объемистый анализ множества всех возможных ходов.

В этом отношении задача отличается от задачи независимого множества, в которой, насколько нам известно, найти большое решение сложно, зато предложенное большое решение проверяется легко. Эти отличия формализуются в классе PSPACE-полных задач, к которому принадлежит задача конкурентного размещения. Считается, что PSPACE-полные задачи строго сложнее NP-полных задач, и это предполагаемое отсутствие коротких “доказательств” их решений является признаком этой повышенной сложности. Концепция PSPACE-полноты отражает широкий спектр задач, связанных с играми и планированием; многие из них считаются фундаментальными проблемами в области искусственного интеллекта.