Um im Avaloqix Wettbewerb einen einigermassen sinnvollen Agenten zustande zu kriegen, braucht es sehr wahrscheinlich eine Funktion, die den maximalen Fluss eines gegebenen Netzwerkes berechnet. Dafür gibt es eine Vielzahl von Algorithmen mit verschiedenen Aufwänden und in verschiedenen Komplexitätsstufen.
Der erste, älteste und einfachste Algorithmus ist wohl derjenige von Ford und Fulkerson. Er ist aber relativ aufwändig in der Berechnung (O(#Kanten*#Knoten*Grösste-Kapazität)), da der maximale Fluss in den Aufwand hineinspielt. Etwas besser ist der Algorithmus von Tarjan und Goldberg. Er wird von der Uni Karlsruhe anschaulich erklärt und bei Google Code findet man auch eine Implementation davon.
Für Graphen mit kleiner Kantendichte ist allerdings der Edmonds-Karp-Algorithmus schneller (laut Wikipedia).
Wenn man die von der Avaloqix-Oberfläche unter Wettbewerbsbedingungen erzeugten Graphen anschaut, ergibt sich folgendes Bild:
- Bei 20 Knoten werden 40-50 Kanten generiert, das ergibt eine Dichte von ungefähr 0,263
- Bei 60 Knoten werden 160 Kanten generiert, das ergibt eine Dichte von ungefähr 0,090
Das darf wohl mit Fug und Recht als undicht, ääh, geringe Dichte bezeichnet werden, also machen wir uns doch an Edmonds Karp!
Implementation
Bei der Implementation habe ich mich sehr nahe an die Beispielimplementation von Wikipedia gehalten. Die einzelnen Teile sind etwas aufgeräumter und kommentierter:
* Edmonds-Karp algorithm with O(V³E) complexity
*
* This implementation is a slightliy modified source from Wikipedia. See
* http://en.wikipedia.org/wiki/Edmonds_karp
*/
class MaxFlow {
public static final int UNVISITED = 0, VISITED = 1;
private int[][] res_capacity; // Residual capacity
private int[] parent; // Parent node in Breadth First Search (BFS)
private int[] mark; // BFS: Already visited?
private int[] min_capacity; // Minimal flow
private int size; // Number of nodes
private int sink;
public MaxFlow() {
}
public int getMaxflow(int[][] graphMatrix, int source, int sink) {
this.sink = sink;
this.size = graphMatrix.length;
int max_flow = 0; // THE max flow for which we are doing this
// circus
int[][] flow = new int[size][size]; // Our flow
res_capacity = new int[size][size]; // Remaining capacity
parent = new int[size];
min_capacity = new int[size];
mark = new int[size];
// Before we start, all capacities are residual
// System.arraycopy may be faster: see http://www.javaspecialists.eu/archive/Issue124.html
// The following is wrong, as Feri in the comments has found out.
// clone() is one-dimensional! *pats-head*
// res_capacity=graphMatrix.clone();
//
//Faster:
for (int i = 0; i < size; i++) {
System.arraycopy(graphMatrix[i], 0, res_capacity[i], 0, size);
}
// Search in BFS manner through the graph, Path by Path
while (BFS(source)) {
max_flow += min_capacity[sink];
int v = sink, u;
while (v != source) {
u = parent[v];
flow[u][v] += min_capacity[sink];
flow[v][u] -= min_capacity[sink];
res_capacity[u][v] -= min_capacity[sink];
res_capacity[v][u] += min_capacity[sink];
v = u;
}
}
return max_flow;
}
/**
* Breadth First Search in O(V²)
*
* @param source
* The source node
*/
private boolean BFS(int source) {
int first, last; // Queue pointers
int[] queue; // Queue pointers
queue = new int[size];
for (int i = 0; i < size; i++) {
mark[i] = UNVISITED;
min_capacity[i] = Integer.MAX_VALUE;
}
first = last = 0;
queue[last++] = source;
mark[source] = VISITED;
while (first != last) { // While "queue" not empty.
int v = queue[first++];
for (int u = 0; u < size; u++)
if (mark[u] == UNVISITED && res_capacity[v][u] > 0) {
min_capacity[u] = Math.min(min_capacity[v],
res_capacity[v][u]);
parent[u] = v;
mark[u] = VISITED;
if (u == sink)
return true;
queue[last++] = u;
}
}
return false;
}
}
Resultat
Als innere Klasse angelegt, arbeitet diese Implementation wunderbar in einem Avaloqix-Agenten. Tests haben gezeigt, dass das Resultat nicht nur stimmt, sondern auch mit den Ausgaben der Spieloberfläche korrespondiert. Auch bei sehr grossen Netzwerken braucht sie auf meinem Schlaftop nur ein paar wenige Millisekunden.
Hallo skaldrom,
danke für die Veröffentlichung Deiner Implementierung.
Allerdings gibt es einen Schönheitsfehler: Während der Berechnung wird die übergebene graphMatrix zerstört. Kann leicht getestet werden, indem man mit der selben Matrix zwei mal maxFlow berechnen lässt. Der erste Aufruf liefert das korrekte Ergebnis, der zweite liefert dann nur noch „0“.
Der Grund liegt in der flachen Hierarchie von clone(). Der clone des int[][] erzeugt nur für die erste Dimension eine Kopie, die zweite Dimension ist wiederum eine Referenz auf das Original-Array:
Also: res_capacity != graphMatrix
aber: res_capacity[0] == graphMatrix[0]
Änderungen an res_capacity[0] wirken sich somit direkt auf graphMatrix aus!
Lösung:
...
private int[][] cloneMatrix(int[][] matrix) {
int[][] result = new int[matrix.length][];
for (int i = 0; i < result.length; i++) {
result[i] = matrix[i].clone();
}
return result;
}
Viele Grüße,
feri
@Feri: Ui ja, das stimmt! Intern habe ich das schon korrigiert, nicht aber hier im Blog.
Vielen Dank!
Man merke sich: Nur immer eine Dimension clonen!!!
Auch von mir vielen Dank für diese Implementierung, aber
müsste auskommentiert sein.
Yup, vielen Dank, da bin ich übers Ziel hinausgeschossen….