Планирование опроса - Нахождение потока в сети

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

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

Задача

Одной из важных тем в бурно развивающейся области анализа данных является изучение закономерностей потребительских предпочтений. Допустим, компания продает к продуктов и ведет базу данных с историями покупок по большой группе клиентов. (Обладатели карт “Клуба покупателей” догадаются, как собираются такие данные.) Компания желает провести опрос и разослать индивидуальные анкеты в группе из n своих клиентов, чтобы определить, какие продукты больше нравятся покупателям.

Планирование опроса подчиняется некоторым правилам:

♦ Каждый клиент получает вопросы, относящиеся к определенному подмножеству продаваемых продуктов.

♦ Клиенту можно задавать вопросы только о тех продуктах, которые он покупал.

♦ Анкета не должна быть слишком длинной, чтобы не отбить у клиента желание участвовать в опросе, поэтому каждому клиенту задаются вопросы по продуктам из диапазона от с_i до с'_i.

♦ Наконец, для получения достаточного объема информации о продукте j необходимо опросить от p_j до p'_j разных клиентов.

В более формальном представлении входные данные задачи планирования опроса представляют собой двудольный граф G, узлы которого представляют клиентов и продукты, а ребро между клиентом i и продуктом j существует в том случае, если клиент покупал данный продукт. Кроме того, для каждого клиента i = 1, ..., n установлены ограничения с_i ≤ с'_i на количество продуктов, о которых его можно спрашивать; для каждого продукта j = 1, ..., k установлены ограничения p_j ≤ p'_j на количество разных клиентов, которым будут задаваться вопросы. Требуется решить, возможно ли построить анкеты, с которыми будут выполнены все указанные ограничения.

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

Разработка алгоритма

Мы решим эту задачу преобразованием к задаче циркуляции для потоковой сети G' с уровнями потребления и нижними границами, показанными на рис. 7.16. Чтобы получить граф G' из G, мы ориентируем ребра G от клиентов к продуктам, добавляем узлы s и t с ребрами (s, i) для каждого клиента i = 1, ..., n, ребрами (j, t) для каждого продукта j = 1, ..., k и ребром (t, s). Циркуляция в такой сети соответствует распределению вопросов. Поток в ребре (s, i) определяет количество продуктов, включаемых в анкету для клиента i, поэтому ребро будет иметь пропускную способность с'_i и нижнюю границу с_i. Поток в ребре (j, t) соответствует количеству клиентов, которым задаются вопросы о продукте j, поэтому ребро будет иметь пропускную способность p'_j и нижнюю границу р_j. Каждое ребро (i, j), проходящее от клиента к купленному им продукту, имеет пропускную способность 1 с нижней границей 0. Поток, передаваемый ребром (t, s), соответствует общему количеству заданных вопросов. Мы можем присвоить этому ребру пропускную способность ' и нижнюю границу У всех узлов уровень потребления равен 0.

Наш алгоритм должен просто построить сеть G' и проверить, существует ли в ней действительная циркуляция. Сформулированное ниже утверждение устанавливает правильность этого алгоритма.

Анализ алгоритма

(7.53) В графе G', построенном описанным способом, действительная циркуляция существует в том и только в том случае, если существует действительный вариант планирования опроса.

Доказательство. Приведенное описание подсказывает способ преобразования плана опроса в соответствующий поток. Ребро (i, j) передает одну единицу потока, если клиенту i задается вопрос о продукте j в опросе, и не передает поток в противном случае. Поток в ребрах (s, i) представляет количество вопросов, заданных клиенту i, поток в ребре (j, t) — количество клиентов, которым заданы вопросы o продукте j, и, наконец, поток в ребре (t, s) — общее количество заданных вопросов. Такой поток соответствует 0 потреблению, то есть в каждом узле происходит сохранение потока. Если опрос удовлетворяет этим правилам, то для соответствующего потока выполняются пропускные способности и нижние границы.

И наоборот, если задача циркуляции имеет действительное решение, то согласно (7.52) существует действительная целочисленная циркуляция, у которой имеется естественное соответствие в виде действительного плана опроса. Клиенту i будут заданы вопросы о продукте j в том и только том случае, если ребро (i, j) передает единицу потока.