Хамгийн их урсгал - Түлхэх-дахин шошголох алгоритм¶
Түлхэх-дахин шошголох алгоритм (эсвэл урьдчилсан урсгал түлхэх алгоритм гэж бас нэрлэгддэг) нь урсгалын сүлжээний хамгийн их урсгалыг тооцоолох алгоритм юм. Бидний бодохыг хүсэж буй бодлогын нарийн тодорхойлолтыг Хамгийн их урсгал - Форд-Фалкерсон ба Эдмондс-Карп өгүүллээс олж болно.
Энэ өгүүлэлд бид сүлжээгээр урьдчилсан урсгал түлхэх замаар бодлогыг бодохыг авч үзэх ба энэ нь $O(V^4)$, эсвэл илүү нарийвчлан $O(V^2 E)$ хугацаанд ажиллана. Алгоритмыг Эндрю Голдберг, Роберт Тарьян нар 1985 онд зохиосон.
Тодорхойлолтууд¶
Алгоритмын явцад бид урьдчилсан урсгал-тай харьцах хэрэгтэй болно — өөрөөр хэлбэл урсгалын функцтэй төстэй боловч урсгал хадгалагдах хязгаарлалтыг заавал хангадаггүй функц $f$-тэй. Түүний хувьд зөвхөн
and
хязгаарлалтууд биелэх ёстой.
Тиймээс ямар нэг орой тараадгаасаа илүү их урсгал хүлээн авах боломжтой. Бид энэ оройг илүүдэл урсгалтай гэж хэлэх ба түүний хэмжээг илүүдэл функц $x(u) =\sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v))$-ээр тодорхойлно.
Урсгалын функцтэй ижил аргаар бид урьдчилсан урсгалын функцээр үлдэгдэл багтаамж ба үлдэгдэл графыг тодорхойлж болно.
Алгоритм эхлэлийн урьдчилсан урсгалаас (зарим орой илүүдэлтэй) эхлэх ба гүйцэтгэлийн явцад урьдчилсан урсгалыг зохицуулж, өөрчилнө. Зарим дэлгэрэнгүйг аль хэдийн хэлэхэд алгоритм илүүдэлтэй оройг сонгож, илүүдлийг хөрш оройнууд руу түлхэнэ. Эх ба цоргоос бусад бүх орой илүүдэлгүй болтол үүнийг давтана. Илүүдэлгүй урьдчилсан урсгал нь зөв урсгал болохыг харахад амархан. Энэ нь алгоритмыг жинхэнэ урсгалтайгаар дуусгана.
Бидний шийдэх ёстой хоёр бодлого хэвээр байна. Нэгдүгээрт энэ нь үнэхээр дуусна гэдгийг бид хэрхэн баталгаажуулах вэ? Хоёрдугаарт энэ нь бидэнд ердөө дурын урсгал биш үнэхээр хамгийн их урсгалыг өгнө гэдгийг бид хэрхэн баталгаажуулах вэ?
Эдгээр бодлогыг бодохын тулд бидэнд өөр функцийн тусламж хэрэгтэй, тухайлбал орой бүрд бүхэл тоо оноодог шошголох функц $h$, ихэвчлэн өндрийн функц гэж бас нэрлэгддэг функц хэрэгтэй. Хэрэв $h(s) = |V|$, $h(t) = 0$ бөгөөд үлдэгдэл графт ирмэг $(u, v)$ байвал $h(u) \le h(v) + 1$ бол буюу ирмэг $(u, v)$ үлдэгдэл графт эерэг багтаамжтай бол бид шошголлыг зөв гэж нэрлэнэ. Өөрөөр хэлбэл хэрэв $u$-ээс $v$ рүү урсгалыг нэмэгдүүлэх боломжтой бол $v$-ийн өндөр $u$-ийн өндрөөс хамгийн ихдээ нэгээр бага байж болох ч тэнцүү буюу бүр өндөр байж болно.
Хэрэв зөв шошголох функц оршин байвал үлдэгдэл графт $s$-ээс $t$ хүрэх нэмэгдүүлэх зам оршихгүй гэдгийг тэмдэглэх нь чухал. Учир нь ийм зам хамгийн ихдээ $|V| - 1$ ирмэгийн урттай байх ба ирмэг бүр өндрийг хамгийн ихдээ нэгээр л бууруулж чадна, харин эхний өндөр нь $h(s) = |V|$, сүүлийн өндөр нь $h(t) = 0$ бол энэ нь боломжгүй.
Энэ шошголох функцийг ашиглан бид түлхэх-дахин шошголох алгоритмын стратегийг тодорхойлж болно: Бид зөв урьдчилсан урсгал ба зөв шошголох функцээс эхэлнэ. Алхам бүрд бид оройнуудын хооронд зарим илүүдлийг түлхэж, оройнуудын шошгыг шинэчилнэ. Алхам бүрийн дараа урьдчилсан урсгал ба шошголол зөв хэвээр байхыг бид баталгаажуулах ёстой. Хэрэв тэгвэл алгоритм дуусахад урьдчилсан урсгал нь зөв урсгал болно. Мөн бидэнд зөв шошголол байгаа тул үлдэгдэл графт $s$ ба $t$-ийн хооронд зам оршихгүй бөгөөд энэ нь урсгал үнэндээ хамгийн их урсгал гэсэн үг.
Хэрэв бид Форд-Фалкерсоны алгоритмыг түлхэх-дахин шошголох алгоритмтай харьцуулбал алгоритмууд бие биенийхээ хос мэт санагдана. Форд-Фалкерсоны алгоритм ямагт зөв урсгалыг хадгалж, нэмэгдүүлэх зам байхгүй болтол түүнийг сайжруулдаг бол түлхэх-дахин шошголох алгоритмд ямар ч үед нэмэгдүүлэх зам оршихгүй бөгөөд бид урьдчилсан урсгалыг зөв урсгал болтол сайжруулна.
Алгоритм¶
Эхлээд бид графыг зөв урьдчилсан урсгал ба шошголох функцээр эхлүүлэх ёстой.
Форд-Фалкерсоны алгоритмд хийдэг шиг хоосон урьдчилсан урсгалыг ашиглах боломжгүй, учир нь тэгвэл нэмэгдүүлэх зам байх ба энэ нь зөв шошголол оршихгүй гэдгийг илэрхийлнэ. Тиймээс бид $s$-ээс гарах ирмэг бүрийг түүний хамгийн их багтаамжаар эхлүүлнэ: $f((s, u)) = c((s, u))$. Бусад бүх ирмэгийг тэгээр эхлүүлнэ. Энэ тохиолдолд зөв шошголол оршин байна, тухайлбал эх оройн хувьд $h(s) = |V|$, бусад бүхний хувьд $h(u) = 0$.
Одоо хоёр үйлдлийг илүү дэлгэрэнгүй тайлбарлая.
push үйлдлээр бид нэг орой $u$-ээс хөрш орой $v$ рүү аль болох их илүүдэл урсгалыг түлхэхийг оролдоно.
Бидэнд нэг дүрэм бий: бид зөвхөн $h(u) = h(v) + 1$ байх үед л $u$-ээс $v$ рүү урсгал түлхэхийг зөвшөөрнө.
Энгийн үгээр хэлбэл илүүдэл урсгал доошоо урсах ёстой, гэхдээ хэт эгц биш.
Мэдээж бид зөвхөн $\min(x(u), c((u, v)) - f((u, v)))$ урсгалыг түлхэж чадна.
Хэрэв орой илүүдэлтэй боловч илүүдлийг ямар ч зэргэлдээ орой руу түлхэх боломжгүй бол бид энэ оройн өндрийг ихэсгэх хэрэгтэй.
Бид энэ үйлдлийг relabel гэж нэрлэнэ.
Бид шошголлын зөв байдлыг хадгалсаар байхын зэрэгцээ түүнийг аль болох ихээр нэмэгдүүлнэ.
Товчлон дүгнэвэл алгоритм товчхондоо ийм байна: Бид зөв урьдчилсан урсгал ба зөв шошголлыг эхлүүлнэ. Бид түлхэх эсвэл дахин шошголох үйлдлийг гүйцэтгэж чадах л бол тэдгээрийг гүйцэтгэнэ. Дараа нь урьдчилсан урсгал үнэндээ урсгал болох ба бид түүнийг буцаана.
Complexity¶
Оройн хамгийн их шошго $2|V| - 1$ болохыг харуулахад амархан. Энэ үед үлдсэн бүх илүүдлийг эх рүү буцаан түлхэж болох ба түлхэнэ. Энэ нь хамгийн ихдээ $O(V^2)$ дахин шошголох үйлдэл өгнө.
Мөн хамгийн ихдээ $O(V E)$ ханадаг түлхэлт (ирмэгийн нийт багтаамжийг ашигладаг түлхэлт), хамгийн ихдээ $O(V^2 E)$ ханадаггүй түлхэлт (ирмэгийн багтаамжийг бүрэн ашигладаггүй түлхэлт) гүйцэтгэгдэхийг харуулж болно. Хэрэв бид илүүдэлтэй дараагийн оройг $O(1)$ хугацаанд олох боломж олгодог өгөгдлийн бүтэц сонговол алгоритмын нийт complexity нь $O(V^2 E)$ болно.
Implementation¶
const int inf = 1000000000;
int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess, seen;
queue<int> excess_vertices;
void push(int u, int v) {
int d = min(excess[u], capacity[u][v] - flow[u][v]);
flow[u][v] += d;
flow[v][u] -= d;
excess[u] -= d;
excess[v] += d;
if (d && excess[v] == d)
excess_vertices.push(v);
}
void relabel(int u) {
int d = inf;
for (int i = 0; i < n; i++) {
if (capacity[u][i] - flow[u][i] > 0)
d = min(d, height[i]);
}
if (d < inf)
height[u] = d + 1;
}
void discharge(int u) {
while (excess[u] > 0) {
if (seen[u] < n) {
int v = seen[u];
if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
push(u, v);
else
seen[u]++;
} else {
relabel(u);
seen[u] = 0;
}
}
}
int max_flow(int s, int t) {
height.assign(n, 0);
height[s] = n;
flow.assign(n, vector<int>(n, 0));
excess.assign(n, 0);
excess[s] = inf;
for (int i = 0; i < n; i++) {
if (i != s)
push(s, i);
}
seen.assign(n, 0);
while (!excess_vertices.empty()) {
int u = excess_vertices.front();
excess_vertices.pop();
if (u != s && u != t)
discharge(u);
}
int max_flow = 0;
for (int i = 0; i < n; i++)
max_flow += flow[i][t];
return max_flow;
}
Here we use the queue excess_vertices to store all vertices that currently have excess.
In that way we can pick the next vertex for a push or a relabel operation in constant time.
And to make sure that we don't spend too much time finding the adjacent vertex to whom we can push, we use a data structure called current-arc. Basically we will iterate over the edges in a circular order and always store the last edge that we used. This way, for a certain labeling value, we will switch the current edge only $O(n)$ time. And since the relabeling already takes $O(n)$ time, we don't make the complexity worse.