پرش به محتویات

شار بیشینه - الگوریتم Push-relabel

الگوریتم push-relabel (که با نام الگوریتم preflow-push نیز شناخته می‌شود) الگوریتمی برای محاسبه‌ی شار بیشینه در یک شبکه‌ی شار است. تعریف دقیق مسئله‌ای که می‌خواهیم حل کنیم را می‌توانید در مقاله‌ی شار بیشینه - Ford-Fulkerson و Edmonds-Karp بیابید.

در این مقاله، به حل مسئله از طریق «هل دادن» یک پیش‌شار (preflow) در شبکه می‌پردازیم که در زمان $O(V^4)$ یا به طور دقیق‌تر $O(V^2 E)$ اجرا می‌شود. این الگوریتم توسط Andrew Goldberg و Robert Tarjan در سال ۱۹۸۵ طراحی شد.

تعاریف

در طول اجرای الگوریتم، با یک پیش‌شار (preflow) سروکار داریم؛ یعنی تابعی مانند $f$ که شبیه تابع شار است، اما لزوماً قید بقای شار را برآورده نمی‌کند. برای آن، تنها باید قیود زیر برقرار باشند:

$$0 \le f(e) \le c(e)$$

و

$$\sum_{(v, u) \in E} f((v, u)) \ge \sum_{(u, v) \in E} f((u, v))$$

بنابراین، ممکن است یک رأس، شار بیشتری از آنچه توزیع می‌کند دریافت کند. می‌گوییم این رأس دارای شار اضافی است و مقدار آن را با تابع اضافه (excess) به صورت $x(u) =\sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v))$ تعریف می‌کنیم.

همانند تابع شار، با استفاده از تابع پیش‌شار نیز می‌توانیم ظرفیت‌های باقیمانده و گراف باقیمانده را تعریف کنیم.

الگوریتم با یک پیش‌شار اولیه (که در آن برخی رئوس اضافه دارند) شروع می‌شود و در طول اجرا، این پیش‌شار مدیریت و اصلاح می‌شود. اگر بخواهیم کمی از جزئیات را بگوییم، الگوریتم یک رأس با اضافه را انتخاب کرده و این اضافه را به رئوس همسایه «هل» می‌دهد (push می‌کند). این کار تا زمانی تکرار می‌شود که تمام رئوس، به جز منبع و مقصد، از اضافه خالی شوند. به راحتی می‌توان دید که یک پیش‌شار بدون اضافه، یک شار معتبر است. این باعث می‌شود الگوریتم با یک شار واقعی خاتمه یابد.

هنوز دو مشکل وجود دارد که باید با آن‌ها مقابله کنیم. اول، چگونه تضمین کنیم که این فرآیند واقعاً پایان می‌یابد؟ و دوم، چگونه تضمین کنیم که این فرآیند به ما یک شار بیشینه می‌دهد و نه فقط یک شار تصادفی؟

برای حل این مشکلات به کمک تابع دیگری به نام تابع برچسب‌گذاری (labeling) یا $h$ نیاز داریم که اغلب به آن تابع ارتفاع (height) نیز گفته می‌شود و به هر رأس یک عدد صحیح نسبت می‌دهد. یک برچسب‌گذاری را معتبر می‌نامیم اگر $h(s) = |V|$ و $h(t) = 0$ باشد و همچنین اگر یال $(u, v)$ در گراف باقیمانده وجود داشته باشد (یعنی یال $(u, v)$ ظرفیت مثبتی در گراف باقیمانده داشته باشد)، آنگاه $h(u) \le h(v) + 1$ برقرار باشد. به عبارت دیگر، اگر امکان افزایش شار از $u$ به $v$ وجود داشته باشد، ارتفاع $v$ می‌تواند حداکثر یک واحد کمتر از ارتفاع $u$ باشد، اما می‌تواند مساوی یا حتی بیشتر هم باشد.

توجه به این نکته مهم است که اگر یک تابع برچسب‌گذاری معتبر وجود داشته باشد، آنگاه هیچ مسیر افزایشی از $s$ به $t$ در گراف باقیمانده وجود ندارد. زیرا چنین مسیری طولی حداکثر برابر با $|V| - 1$ یال خواهد داشت و هر یال می‌تواند ارتفاع را حداکثر یک واحد کاهش دهد، که این با توجه به اینکه ارتفاع اولیه $h(s) = |V|$ و ارتفاع نهایی $h(t) = 0$ است، غیرممکن می‌باشد.

با استفاده از این تابع برچسب‌گذاری، می‌توانیم استراتژی الگوریتم push-relabel را بیان کنیم: ما با یک پیش‌شار معتبر و یک تابع برچسب‌گذاری معتبر شروع می‌کنیم. در هر مرحله، مقداری از اضافه را بین رئوس push کرده و برچسب‌های رئوس را به‌روزرسانی می‌کنیم. باید اطمینان حاصل کنیم که پس از هر مرحله، پیش‌شار و برچسب‌گذاری همچنان معتبر باقی بمانند. سپس وقتی الگوریتم به پایان می‌رسد، پیش‌شار به یک شار معتبر تبدیل شده است. و از آنجایی که یک برچسب‌گذاری معتبر نیز داریم، هیچ مسیری بین $s$ و $t$ در گراف باقیمانده وجود ندارد، که به این معنی است که شار به‌دست آمده در واقع یک شار بیشینه است.

اگر الگوریتم Ford-Fulkerson را با الگوریتم push-relabel مقایسه کنیم، به نظر می‌رسد که این دو الگوریتم دوگان (dual) یکدیگر هستند. الگوریتم Ford-Fulkerson در تمام مدت یک شار معتبر را حفظ کرده و آن را تا زمانی که دیگر مسیر افزایشی وجود نداشته باشد بهبود می‌بخشد، در حالی که در الگوریتم push-relabel در هیچ زمانی مسیر افزایشی وجود ندارد و ما پیش‌شار را تا زمانی که به یک شار معتبر تبدیل شود، بهبود می‌دهیم.

الگوریتم

ابتدا باید گراف را با یک پیش‌شار و یک تابع برچسب‌گذاری معتبر مقداردهی اولیه کنیم.

استفاده از پیش‌شار خالی - مانند کاری که در الگوریتم Ford-Fulkerson انجام می‌شود - ممکن نیست، زیرا در این صورت یک مسیر افزایشی وجود خواهد داشت و این بدان معناست که هیچ برچسب‌گذاری معتبری وجود ندارد. بنابراین، هر یال خروجی از $s$ را با ظرفیت بیشینه‌ی خود مقداردهی می‌کنیم: $f((s, u)) = c((s, u))$. و تمام یال‌های دیگر را با صفر مقداردهی می‌کنیم. در این حالت، یک برچسب‌گذاری معتبر وجود دارد، یعنی $h(s) = |V|$ برای رأس منبع و $h(u) = 0$ برای سایر رئوس.

حال بیایید دو عملیات را با جزئیات بیشتری شرح دهیم.

با عملیات push، سعی می‌کنیم تا حد امکان شار اضافی را از یک رأس $u$ به یک رأس همسایه $v$ هل دهیم. یک قانون داریم: تنها مجاز به push کردن شار از $u$ به $v$ هستیم اگر $h(u) = h(v) + 1$ باشد. به زبان ساده، شار اضافی باید به سمت پایین جریان یابد، اما نه با شیب خیلی زیاد. البته، ما فقط می‌توانیم به اندازه‌ی $\min(x(u), c((u, v)) - f((u, v)))$ شار را push کنیم.

اگر یک رأس دارای اضافه باشد، اما امکان push کردن این اضافه به هیچ‌کدام از رئوس مجاور وجود نداشته باشد، باید ارتفاع این رأس را افزایش دهیم. این عملیات را relabel (برچسب‌گذاری مجدد) می‌نامیم. ما ارتفاع را تا جایی که ممکن است افزایش می‌دهیم، به طوری که اعتبار برچسب‌گذاری حفظ شود.

به طور خلاصه، الگوریتم به این صورت است: یک پیش‌شار معتبر و یک برچسب‌گذاری معتبر را مقداردهی اولیه می‌کنیم. تا زمانی که بتوانیم عملیات push یا relabel را انجام دهیم، آن‌ها را اجرا می‌کنیم. پس از آن، پیش‌شار در واقع یک شار است و ما آن را برمی‌گردانیم.

پیچیدگی

به راحتی می‌توان نشان داد که بیشینه برچسب یک رأس $2|V| - 1$ است. در این نقطه، تمام اضافه‌های باقیمانده می‌توانند و به منبع بازگردانده خواهند شد. این حداکثر $O(V^2)$ عملیات relabel را به ما می‌دهد.

همچنین می‌توان نشان داد که حداکثر $O(V E)$ عملیات push اشباع‌کننده (push که در آن ظرفیت کل یال استفاده می‌شود) و حداکثر $O(V^2 E)$ عملیات push غیراشباع‌کننده (push که در آن ظرفیت یک یال به طور کامل استفاده نمی‌شود) انجام خواهد شد. اگر یک ساختمان داده انتخاب کنیم که به ما امکان پیدا کردن رأس بعدی با اضافه را در زمان $O(1)$ بدهد، آنگاه پیچیدگی کل الگوریتم $O(V^2 E)$ خواهد بود.

پیاده‌سازی

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;
}

در اینجا از صف excess_vertices برای ذخیره‌ی تمام رئوسی که در حال حاضر دارای اضافه هستند استفاده می‌کنیم. به این ترتیب می‌توانیم رأس بعدی را برای عملیات push یا relabel در زمان ثابت انتخاب کنیم.

و برای اطمینان از اینکه زمان زیادی را صرف پیدا کردن رأس مجاوری که می‌توانیم به آن push کنیم، نمی‌کنیم، از یک ساختمان داده به نام current-arc استفاده می‌کنیم. اساساً، ما روی یال‌ها به صورت دایره‌ای پیمایش می‌کنیم و همیشه آخرین یالی را که استفاده کرده‌ایم ذخیره می‌کنیم. به این ترتیب، برای یک مقدار برچسب‌گذاری مشخص، یال جاری را تنها $O(n)$ بار تغییر می‌دهیم. و از آنجایی که عملیات relabel خود $O(n)$ زمان می‌برد، پیچیدگی را بدتر نمی‌کنیم.