Wikipedia

プリフロープッシュ法

（プッシュ再ラベル法から転送）

プリフロープッシュ法（プリフロープッシュほう、プッシュ再ラベル法、英: preflow–push algorithm, push–relabel algorithm）とは、数理最適化においてフローネットワークにおける最大流を求めるアルゴリズムである。プッシュ・再ラベルの名はプッシュ操作と再ラベル操作の二つの手続きを行うことに由来する。実行を通じて、プリフロープッシュ法はプリフローを保持しながら、再ラベル操作により求まる可能ネットワークの下で近傍の頂点間にフローを流すプッシュ操作によって最大流を求める。同じ最大流問題に対するアルゴリズムのフォード・ファルカーソン法ではソースからシンクまでの路からフローを増やしていく大域的な増加路を求めるアルゴリズムである[1]。

プリフロープッシュ法は最大流問題に対して最も効率の良いアルゴリズムの一つとして知られている。汎用プリフロープッシュ法においては時間計算量が強多項式時間の O(V 2E) で動作することが知られており、計算量 O(VE 2) で動作するエドモンズ・カープ法よりも効率の良い解法とされている[2]。類似の解法の中にはより高速に動作するアルゴリズムも存在する。highest label node selection規則に従った方法では計算量が O(V 2√E) オーダーで動作することが最大流問題に対するベンチマーク問題の実験から求まっている[3][4]。動的木を使用したプリフロープッシュ法では時間計算量は O(VElog(V 2/E)) に達するが[2]、実用上の面では効率が悪くなるTemplate:用出典。

またプリフロープッシュ法は最小費用流問題（英語版）に対して拡張することができる[5]。距離ラベルの概念はより効率的に増加道を求めることができ、これとプリフロープッシュ法を組み合わせることでより高い性能を発揮するアルゴリズムを使用することができる[4][6]。

歴史

編集

プリフローの概念は1974年にアレキサンダー・カルザノフ（英語版）によって Soviet Mathematical Dokladi 15 に掲載したことから始まる。プリフロー法は増加道の距離を求める際にラベリングシステムを使用せず、プッシュ操作により求めるアルゴリズムである[2][7]。

プリフロープッシュ法はアンドリュー・V・ゴールドバーグ（英語版）とロバート・タージャンによって提案されたアルゴリズムである。プリフロープッシュ法は1986年11月の STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing において始めて公表され、1988年に ACM の学術論文誌に掲載された。両者の論文では計算量 O(V 2E) で終了する汎用解法、計算量 O(V 3) の段階的解法、計算量 O(VE log(V 2/E)) で動作する動的木を使用し、並列・分散実装化された解法が提案されている[2][8]。ゴールドバーグ＝タージャンはYossi Shiloach・Uzi Vishkinの並列最大流アルゴリズムにおける距離ラベルに上記の技法を適用した解法を公表した[9][10]。

実装例

編集
C言語の実装例
#include <stdlib.h>
#include <stdio.h>

#define NODES 6
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define INFINITE 10000000

void push(const int * const * C, int ** F, int *excess, int u, int v) {
  int send = MIN(excess[u], C[u][v] - F[u][v]);
  F[u][v] += send;
  F[v][u] -= send;
  excess[u] -= send;
  excess[v] += send;
}

void relabel(const int * const * C, const int * const * F, int *height, int u) {
  int v;
  int min_height = INFINITE;
  for (v = 0; v < NODES; v++) {
    if (C[u][v] - F[u][v] > 0) {
      min_height = MIN(min_height, height[v]);
      height[u] = min_height + 1;
    }
  }
};

void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) {
  while (excess[u] > 0) {
    if (seen[u] < NODES) {
      int v = seen[u];
      if ((C[u][v] - F[u][v] > 0) && (height[u] > height[v])) {
        push(C, F, excess, u, v);
      } else {
        seen[u] += 1;
      }
    } else {
      relabel(C, F, height, u);
      seen[u] = 0;
    }
  }
}

void moveToFront(int i, int *A) {
  int temp = A[i];
  int n;
  for (n = i; n > 0; n--) {
    A[n] = A[n-1];
  }
  A[0] = temp;
}

int pushRelabel(const int * const * C, int ** F, int source, int sink) {
  int *excess, *height, *list, *seen, i, p;

  excess = (int *) calloc(NODES, sizeof(int));
  height = (int *) calloc(NODES, sizeof(int));
  seen = (int *) calloc(NODES, sizeof(int));

  list = (int *) calloc((NODES-2), sizeof(int));

  for (i = 0, p = 0; i < NODES; i++){
    if ((i != source) && (i != sink)) {
      list[p] = i;
      p++;
    }
  }

  height[source] = NODES;
  excess[source] = INFINITE;
  for (i = 0; i < NODES; i++)
    push(C, F, excess, source, i);

  p = 0;
  while (p < NODES - 2) {
    int u = list[p];
    int old_height = height[u];
    discharge(C, F, excess, height, seen, u);
    if (height[u] > old_height) {
      moveToFront(p, list);
      p = 0;
    } else {
      p += 1;
    }
  }
  int maxflow = 0;
  for (i = 0; i < NODES; i++)
    maxflow += F[source][i];

  free(list);

  free(seen);
  free(height);
  free(excess);

  return maxflow;
}

void printMatrix(const int * const * M) {
  int i, j;
  for (i = 0; i < NODES; i++) {
    for (j = 0; j < NODES; j++)
      printf("%d\t",M[i][j]);
    printf("\n");
  }
}

int main(void) {
  int **flow, **capacities, i;
  flow = (int **) calloc(NODES, sizeof(int*));
  capacities = (int **) calloc(NODES, sizeof(int*));
  for (i = 0; i < NODES; i++) {
    flow[i] = (int *) calloc(NODES, sizeof(int));
    capacities[i] = (int *) calloc(NODES, sizeof(int));
  }

  // Sample graph
  capacities[0][1] = 2;
  capacities[0][2] = 9;
  capacities[1][2] = 1;
  capacities[1][3] = 0;
  capacities[1][4] = 0;
  capacities[2][4] = 7;
  capacities[3][5] = 7;
  capacities[4][5] = 4;

  printf("Capacity:\n");
  printMatrix(capacities);

  printf("Max Flow:\n%d\n", pushRelabel(capacities, flow, 0, 5));

  printf("Flows:\n");
  printMatrix(flow);

  return 0;
}
Pythonの実装例
def relabel_to_front(C, source: int, sink: int) -> int:
    n = len(C)  # C is the capacity matrix
    F = [[0] * n for _ in range(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    height = [0] * n  # height of node
    excess = [0] * n  # flow into node minus flow from node
    seen   = [0] * n  # neighbours seen since last relabel
    # node "queue"
    nodelist = [i for i in range(n) if i != source and i != sink]

    def push(u, v):
        send = min(excess[u], C[u][v] - F[u][v])
        F[u][v] += send
        F[v][u] -= send
        excess[u] -= send
        excess[v] += send

    def relabel(u):
        # Find smallest new height making a push possible,
        # if such a push is possible at all.
        min_height = ∞
        for v in range(n):
            if C[u][v] - F[u][v] > 0:
                min_height = min(min_height, height[v])
                height[u] = min_height + 1

    def discharge(u):
        while excess[u] > 0:
            if seen[u] < n:  # check next neighbour
                v = seen[u]
                if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
                    push(u, v)
                else:
                    seen[u] += 1
            else:  # we have checked all neighbours. must relabel
                relabel(u)
                seen[u] = 0

    height[source] = n  # longest path from source to sink is less than n long
    excess[source] = ∞  # send as much flow as possible to neighbours of source
    for v in range(n):
        push(source, v)

    p = 0
    while p < len(nodelist):
        u = nodelist[p]
        old_height = height[u]
        discharge(u)
        if height[u] > old_height:
            nodelist.insert(0, nodelist.pop(p))  # move to front of list
            p = 0  # start from front of list
        else:
            p += 1

    return sum(F[source])

脚注

編集
[脚注の使い方]
  1. ^ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001). “§26 Maximum flow”. Introduction to Algorithms (2nd ed.). The MIT Press. pp. 643–698. ISBN 978-0262032933 
  2. ^ a b c d Goldberg, A V; Tarjan, R E (1986). “A new approach to the maximum flow problem”. Proceedings of the eighteenth annual ACM symposium on Theory of computing – STOC '86. pp. 136. doi:10.1145/12130.12144. ISBN 978-0897911931 
  3. ^ Ahuja, Ravindra K.; Kodialam, Murali; Mishra, Ajay K.; Orlin, James B. (1997). “Computational investigations of maximum flow algorithms”. European Journal of Operational Research 97 (3): 509. doi:10.1016/S0377-2217(96)00269-X. 
  4. ^ a b Goldberg, Andrew V. (2008). “The Partial Augment–Relabel Algorithm for the Maximum Flow Problem”. Algorithms – ESA 2008. Lecture Notes in Computer Science. 5193. pp. 466–477. doi:10.1007/978-3-540-87744-8_39. ISBN 978-3-540-87743-1 
  5. ^ Goldberg, Andrew V (1997). “An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm”. Journal of Algorithms 22: 1–29. doi:10.1006/jagm.1995.0805. 
  6. ^ Ahuja, Ravindra K.; Orlin, James B. (1991). “Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems”. Naval Research Logistics 38 (3): 413. doi:10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J. 
  7. ^ Goldberg, Andrew V.; Tarjan, Robert E. (2014). “Efficient maximum flow algorithms”. Communications of the ACM 57 (8): 82. doi:10.1145/2628036. 
  8. ^ Goldberg, Andrew V.; Tarjan, Robert E. (1988). “A new approach to the maximum-flow problem”. Journal of the ACM 35 (4): 921. doi:10.1145/48014.61051. 
  9. ^ Shiloach, Yossi; Vishkin, Uzi (1982). “An O(n2log n) parallel max-flow algorithm”. Journal of Algorithms 3 (2): 128–146. doi:10.1016/0196-6774(82)90013-X. 
  10. ^ Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications (1st ed.). Prentice Hall. ISBN 978-0136175490 
「https://ja.wikipedia.org/w/index.php?title=プリフロープッシュ法&oldid=104005630」から取得