Хамгийн бага өртөгтэй урсгал ашиглан хуваарилалтын бодлогыг бодох¶

Хуваарилалтын бодлого нь хоёр эквивалент томьёололтой:

Квадрат матриц $A[1..N, 1..N]$ өгөгдсөн бол мөр ба багана бүрд яг нэг элемент сонгогдох ба эдгээр элементийн утгуудын нийлбэр хамгийн бага байхаар түүнээс $N$ элемент сонгох хэрэгтэй.
$N$ захиалга ба $N$ машин байна. Захиалга бүрийн хувьд машин бүр дээр үйлдвэрлэх өртөг мэдэгдэж байна. Машин бүр дээр зөвхөн нэг захиалга гүйцэтгэж болно. Нийт өртөг хамгийн бага байхаар бүх захиалгыг машинуудад хуваарилах шаардлагатай.

Энд бид хамгийн бага өртөгтэй урсгал (min-cost-flow) олох алгоритм дээр суурилсан, хуваарилалтын бодлогыг $\mathcal{O}(N^3)$-д бодох шийдлийг авч үзнэ.

Тайлбар¶

Хоёр хэсэгт сүлжээ байгуулъя: эх $S$, цорго $T$ байх ба эхний хэсэгт $N$ орой (матрицын мөр буюу захиалгад харгалзах), хоёр дахьд нь мөн $N$ орой (матрицын багана буюу машинд харгалзах) байна. Эхний олонлогийн орой $i$ бүр ба хоёр дахь олонлогийн орой $j$ бүрийн хооронд бид 1 багтаамжтай, $A_{ij}$ өртөгтэй ирмэг татна. Эх $S$-ээс бид эхний олонлогийн бүх орой $i$ рүү 1 багтаамжтай, 0 өртөгтэй ирмэг татна. Хоёр дахь олонлогийн орой $j$ бүрээс цорго $T$ рүү 1 багтаамжтай, 0 өртөгтэй ирмэг татна.

Үүссэн сүлжээнд бид хамгийн бага өртөгтэй хамгийн их урсгалыг олно. Урсгалын утга нь $N$ байх нь ойлгомжтой. Цаашилбал эхний хэсгийн орой $i$ бүрийн хувьд $F_{ij}$ = 1 урсгалтай байх хоёр дахь хэсгийн яг нэг орой $j$ байна. Эцэст нь энэ бол эхний хэсгийн оройнууд ба хоёр дахь хэсгийн оройнуудын хоорондох нэг нэгт харгалзаа бөгөөд энэ нь бодлогын шийд юм (олдсон урсгал хамгийн бага өртөгтэй тул сонгосон ирмэгүүдийн өртгийн нийлбэр боломжит хамгийн бага байх ба энэ нь оновчтой байдлын шалгуур юм).

Хуваарилалтын бодлогын энэ шийдлийн complexity нь хамгийн бага өртөгтэй хамгийн их урсгалын хайлтыг ямар алгоритмаар гүйцэтгэхээс хамаарна. Дейкстра ашиглавал complexity нь $\mathcal{O}(N^3)$, Беллман-Форд ашиглавал $\mathcal{O}(N^4)$ байна. Энэ нь урсгалын хэмжээ $O(N)$ бөгөөд Дейкстрагийн алгоритмын итерац бүрийг $O(N^2)$-д гүйцэтгэж болох ба Беллман-Фордын хувьд энэ нь $O(N^3)$ байдагтай холбоотой.

Implementation¶

The implementation given here is long, it can probably be significantly reduced. It uses the SPFA algorithm for finding shortest paths.

const int INF = 1000 * 1000 * 1000;

vector<int> assignment(vector<vector<int>> a) {
    int n = a.size();
    int m = n * 2 + 2;
    vector<vector<int>> f(m, vector<int>(m));
    int s = m - 2, t = m - 1;
    int cost = 0;
    while (true) {
        vector<int> dist(m, INF);
        vector<int> p(m);
        vector<bool> inq(m, false);
        queue<int> q;
        dist[s] = 0;
        p[s] = -1;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            inq[v] = false;
            if (v == s) {
                for (int i = 0; i < n; ++i) {
                    if (f[s][i] == 0) {
                        dist[i] = 0;
                        p[i] = s;
                        inq[i] = true;
                        q.push(i);
                    }
                }
            } else {
                if (v < n) {
                    for (int j = n; j < n + n; ++j) {
                        if (f[v][j] < 1 && dist[j] > dist[v] + a[v][j - n]) {
                            dist[j] = dist[v] + a[v][j - n];
                            p[j] = v;
                            if (!inq[j]) {
                                q.push(j);
                                inq[j] = true;
                            }
                        }
                    }
                } else {
                    for (int j = 0; j < n; ++j) {
                        if (f[v][j] < 0 && dist[j] > dist[v] - a[j][v - n]) {
                            dist[j] = dist[v] - a[j][v - n];
                            p[j] = v;
                            if (!inq[j]) {
                                q.push(j);
                                inq[j] = true;
                            }
                        }
                    }
                }
            }
        }

        int curcost = INF;
        for (int i = n; i < n + n; ++i) {
            if (f[i][t] == 0 && dist[i] < curcost) {
                curcost = dist[i];
                p[t] = i;
            }
        }
        if (curcost == INF)
            break;
        cost += curcost;
        for (int cur = t; cur != -1; cur = p[cur]) {
            int prev = p[cur];
            if (prev != -1)
                f[cur][prev] = -(f[prev][cur] = 1);
        }
    }

    vector<int> answer(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (f[i][j + n] == 1)
                answer[i] = j;
        }
    }
    return answer;
}