MAXimal | |
добавлено: 10 Jun 2008 23:11 Содержание [скрыть] Обратная задача MST (inverse-MST - обратная задача минимального остова) за O (N M2)Дан взвешенный неориентированный граф G с N вершинами и M рёбрами (без петель и кратных рёбер). Известно, что граф связный. Также указан некоторый остов T этого графа (т.е. выбрано N-1 ребро, которые образуют дерево с N вершинами). Требуется изменить веса рёбер таким образом, чтобы указанный остов T являлся минимальным остовом этого графа (точнее говоря, одним из минимальных остовов), причём сделать это так, чтобы суммарное изменение всех весов было наименьшим. РешениеСведём задачу inverse-MST к задаче min-cost-flow, точнее, к задаче, двойственной min-cost-flow (в смысле двойственности задач линейного программирования); затем решим последнюю задачу. Итак, пусть дан граф G с N вершинами, M рёбрами. Вес каждого ребра обозначим через Ci. Предположим, не теряя общности, что рёбра с номерами с 1 по N-1 являются рёбрами T. 1. Необходимое и достаточное условие MSTПусть дан некоторый остов S (не обязательно минимальный). Введём сначала одно обозначение. Рассмотрим некоторое ребро j, не принадлежащее S. Очевидно, в графе S имеется единственный путь, соединяющий концы этого ребра, т.е. единственный путь, соединяющий концы ребра j и состоящий только из рёбер, принадлежащих S. Обозначим через P[j] множество рёбер, образующих этот путь для j-го ребра. Для того, чтобы некоторый остов S являлся минимальным, необходимо и достаточно, чтобы: Ci <= Cj для всех j ∉ S и каждого i ∈ P[j] Можно заметить, что, поскольку в нашей задаче остову T принадлежат рёбра 1..N-1, то мы можем записать это условие таким образом: Ci <= Cj для всех j = N..M и каждого i ∈ P[j] (причём все i лежат в диапазоне 1..N-1) 2. Граф путейПонятие графа путей непосредственно связано с предыдущей теоремой. Пусть дан некоторый остов S (не обязательно минимальный). Тогда графом путей H для графа G будет следующий граф:
В случае нашей задачи мы можем немного упростить описание графа путей: ребро (i,j) существует в H, если i ∈ P[j], j = N..M, i = 1..N-1 3. Математическая формулировка задачиЧисто формально задача inverse-MST записывается таким образом: найти массив A[1..M] такой, что Ci + Ai <= Cj + Aj для всех j = N..M и каждого i ∈ P[j] (i в 1..N-1), и минимизировать сумму |A1| + |A2| + ... + |Am| здесь под искомым массивом A мы подразумеваем те значения, которые нужно добавить к весам рёбер (т.е., решив задачу inverse-MST, мы заменяем вес Ci каждого ребра i на величину Ci + Ai). Очевидно, что нет смысла увеличивать вес рёбер, принадлежащих T, т.е. Ai <= 0, i = 1..N-1 и нет смысла укорачивать рёбра, не принадлежащие T: Ai >= 0, i = N..M (поскольку в противном случае мы только ухудшим ответ) Тогда мы можем немного упростить постановку задачи, убрав из суммы модули: найти массив A[1..M] такой, что Ci + Ai <= Cj + Aj для всех j = N..M и каждого i ∈ P[j] (i в 1..N-1), Ai <= 0, i = 1..N-1, Ai >= 0, i = N..M, и минимизировать сумму An + ... + Am - (A1 + ... + An-1) Наконец, просто изменим "минимизацию" на "максимизацию", а в самой сумме изменим все знаки на противоположные: найти массив A[1..M] такой, что Ci + Ai <= Cj + Aj для всех j = N..M и каждого i ∈ P[j] (i в 1..N-1), Ai <= 0, i = 1..N-1, Ai >= 0, i = N..M, и максимизировать сумму A1 + ... + An-1 - (An + ... + Am) 4. Сведение задачи inverse-MST к задаче, двойственной задаче о назначенияхФормулировка задачи inverse-MST, которую мы только что дали, является формулировкой задачи линейного программирования с неизвестными A1..Am. Применим классический приём - рассмотрим двойственную ей задачу. По определению, чтобы получить двойственную задачу, нужно каждому неравенству сопоставить двойственную переменную Xij, поменять ролями целевую функцию (которую нужно было минимизировать) и коэффициенты в правых частях неравенств, поменять знаки "<=" на ">=" и наоборот, поменять максимизацию на минимизацию. Итак, двойственная к inverse-MST задача: найти все Xij для каждого (i,j) ∈ H, такие что: все Xij >= 0, для каждого i=1..N-1 ∑ Xij по всем j: (i,j) ∈ H <= 1, для каждого j=N..M ∑ Xij по всем i: (i,j) ∈ H <= 1, и минимизировать ∑ Xij (Cj - Ci) для всех (i,j) ∈ H Последняя задача является задачей о назначениях: нам нужно в графе путей H выбрать несколько рёбер так, чтобы ни одно ребро не пересекалось с другим в вершине, а сумма весов рёбер (вес ребра (i,j) определим как Cj - Ci) должна быть наименьшей. Таким образом, двойственная задача inverse-MST эквивалентна задаче о назначениях. Если мы научимся решать двойственную задачу о назначениях, то мы автоматически решим задачу inverse-MST. 5. Решение двойственной задачи о назначенияхСначала уделим немного внимания тому частному случаю задачи о назначениях, который мы получили. Во-первых, это несбалансированная задача о назначениях, поскольку в одной доле находится N-1 вершин, а в другой - M вершин, т.е. в общем случае число вершин во второй доле больше на целый порядок. Для решения такой двойственной задачи о назначениях есть специализированный алгоритм, который решит её за O (N3), но здесь этот алгоритм рассматриваться не будет. Во-вторых, такую задачу о назначениях можно назвать задачей о назначениях с взвешенными вершинами: веса рёбер положим равными 0, вес каждой вершины из первой доли положим равным -Ci, из второй доли - равным Cj, и решение полученной задачи будет тем же самым. Мы будем решать задачу двойственную задачу о назначениях с помощью модифицированного алгоритма min-cost-flow, который будет находить поток минимальной стоимости и одновременно решение двойственной задачи. Свести задачу о назначениях к задаче min-cost-flow очень легко, но для полноты картины мы опишем этот процесс. Добавим в граф исток s и сток t. Из s к каждой вершине первой доли проведём ребро с пропускной способностью = 1 и стоимостью = 0. Из каждой вершины второй доли проведём ребро к t с пропускной способностью = 1 и стоимостью = 0. Пропускные способности всех рёбер между первой и второй долями также положим равными 1. Наконец, чтобы модифицированный алгоритм min-cost-flow (описанный ниже) работал, нужно добавить ребро из s в t с пропускной способностью = N+1 и стоимостью = 0. 6. Модифицированный алгоритм min-cost-flow для решения задачи о назначенияхЗдесь мы рассмотрим алгоритм последовательных кратчайших путей с потенциалами, который напоминает обычный алгоритм min-cost-flow, но использует также понятие потенциалов, которые к концу работы алгоритма будут содержать решение двойственной задачи. Введём обозначения. Для каждого ребра (i,j) обозначим через Uij его пропускную способность, через Cij - его стоимость, через Fij - поток вдоль этого ребра. Также введём понятие потенциалов. Каждая вершина обладает своим потенциалом PIi. Остаточная стоимость ребра CPIij определяется как: CPIij = Cij - PIi + PIj В любой момент работы алгоритма потенциалы таковы, что выполняются условия: если Fij = 0, то CPIij >= 0 если Fij = Uij, то CPIij <= 0 иначе CPIij = 0 Алгоритм начинает с нулевого потока, и нам нужно найти некоторые начальные значения потенциалов, которые бы удовлетворяли указанным условиям. Нетрудно проверить, что такой способ является одним из возможных решений: PIj = 0 для j = N..M PIi = min Cij, где (i,j) ∈ H PIs = min PIi, где i = 1..N-1 PIt = 0 Собственно сам алгоритм min-cost-flow состоит из нескольких итераций. На каждой итерации мы находим кратчайший путь из s в t в остаточной сети, причём в качестве весов рёбер используем остаточные стоимости CPI. Затем мы увеличиваем поток вдоль найденного пути на единицу, и обновляем потенциалы следующим образом: PIi -= Di где Di - найденное кратчайшее расстояние от s до i (повторимся, в остаточной сети с весами рёбер CPI). Рано или поздно мы найдём тот путь из s в t, который состоит из единственного ребра (s,t). Тогда после этой итерации нам следует завершить работу алгоритма: действительно, если мы не остановим алгоритм, то дальше уже будут находиться пути с неотрицательной стоимостью, и добавлять их в ответ не надо. К концу работы алгоритма мы получим решение задачи о назначениях (в виде потока Fij) и решение двойственной задачи о назначениях (в массиве PIi). (с PIi надо будет провести небольшую модификацию: от всех значений PIi отнять PIs, поскольку его значения имеют смысл только при PIs = 0) 6. ИтогИтак, мы решили двойственную задачу о назначениях, а, следовательно, и задачу inverse-MST. Оценим асимптотику получившегося алгоритма. Сначала мы должны будем построить граф путей. Для этого просто для каждого ребра j ∉ T обходом в ширину по остову T найдём путь P[j]. Тогда граф путей мы построим за O (M) * O (N) = O (N M). Затем мы найдём начальные значения потенциалов за O (N) * O (M) = O (N M). Затем мы будем выполнять итерации min-cost-flow, всего итераций будет не более N (поскольку из истока выходит N рёбер, каждое с пропускной способностью = 1), на каждой итерации мы ищем в графе путей кратчайшие пути от истока до всех остальных вершин. Поскольку вершин в графе путей равно M+2, а число рёбер - O (N M), то, если реализовать поиск кратчайших путей простейшим вариантом алгоритма Дейкстры, каждая итерация min-cost-flow будет выполнять за O (M2), а весь алгоритм min-cost-flow выполнится за O (N M2). Итоговая асимптотика алгоритма равна O (N M2). РеализацияРеализуем весь вышеописанный алгоритм. Единственное изменение - вместо алгоритма Дейкстры применяется алгоритм Левита, который на многих тестах должен работать несколько быстрее. const int INF = 1000*1000*1000;
struct rib {
int v, c, id;
};
struct rib2 {
int a, b, c;
};
int main() {
int n, m;
cin >> n >> m;
vector < vector<rib> > g (n); // граф в формате списков смежности
vector<rib2> ribs (m); // все рёбра в одном списке
... чтение графа ...
int nn = m+2, s = nn-2, t = nn-1;
vector < vector<int> > f (nn, vector<int> (nn));
vector < vector<int> > u (nn, vector<int> (nn));
vector < vector<int> > c (nn, vector<int> (nn));
for (int i=n-1; i<m; ++i) {
vector<int> q (n);
int h=0, t=0;
rib2 & cur = ribs[i];
q[t++] = cur.a;
vector<int> rib_id (n, -1);
rib_id[cur.a] = -2;
while (h < t) {
int v = q[h++];
for (size_t j=0; j<g[v].size(); ++j)
if (g[v][j].id >= n-1)
break;
else if (rib_id [ g[v][j].v ] == -1) {
rib_id [ g[v][j].v ] = g[v][j].id;
q[t++] = g[v][j].v;
}
}
for (int v=cur.b, pv; v!=cur.a; v=pv) {
int r = rib_id[v];
pv = v != ribs[r].a ? ribs[r].a : ribs[r].b;
u[r][i] = n;
c[r][i] = ribs[i].c - ribs[r].c;
c[i][r] = -c[r][i];
}
}
u[s][t] = n+1;
for (int i=0; i<n-1; ++i)
u[s][i] = 1;
for (int i=n-1; i<m; ++i)
u[i][t] = 1;
vector<int> pi (nn);
pi[s] = INF;
for (int i=0; i<n-1; ++i) {
pi[i] = INF;
for (int j=n-1; j<m; ++j)
if (u[i][j])
pi[i] = min (pi[i], ribs[j].c-ribs[i].c);
pi[s] = min (pi[s], pi[i]);
}
for (;;) {
vector<int> id (nn);
deque<int> q;
q.push_back (s);
vector<int> d (nn, INF);
d[s] = 0;
vector<int> p (nn, -1);
while (!q.empty()) {
int v = q.front(); q.pop_front();
id[v] = 2;
for (int i=0; i<nn; ++i)
if (f[v][i] < u[v][i]) {
int new_d = d[v] + c[v][i] - pi[v] + pi[i];
if (new_d < d[i]) {
d[i] = new_d;
if (id[i] == 0)
q.push_back (i);
else if (id[i] == 2)
q.push_front (i);
id[i] = 1;
p[i] = v;
}
}
}
for (int i=0; i<nn; ++i)
pi[i] -= d[i];
for (int v=t; v!=s; v=p[v]) {
int pv = p[v];
++f[pv][v], --f[v][pv];
}
if (p[t] == s) break;
}
for (int i=0; i<m; ++i)
pi[i] -= pi[s];
for (int i=0; i<n-1; ++i)
if (f[s][i])
ribs[i].c += pi[i];
for (int i=n-1; i<m; ++i)
if (f[i][t])
ribs[i].c += pi[i];
... вывод графа ...
}
| |