Távolságmátrix számolása a Floyd-Warshall algoritmussal

May 18, 2020 / Írta: Ambrus

Különböző okokból néha szükségünk lehet egy gráf, vagy térkép két adott pontja közötti távolságra. Ha csak pár ilyen adatra van szükségünk, akkor a szélességi bejárást is alkalmazhatjuk, de ebben a cikkben most a Floyd-Warshall algortmusról, vagy WFI algoritmusról, ami egy térkép összes pontja között kiszámolja, és elmenti a távolságot. Ezt a 2020 májusában megrendezett CodinGame Spring Challenge verseny alkalmával ismertem meg, ahol PacManeket kellett irányítani a játékban úgy, hogy a lehető legtöbb pontot gyűjtsünk össze. A játék elején 1 másodperc áll rendelkezésre a mindenféle számolásra, majd minden egyes parancs leadására 50 milliszekundum. Az utóbbi kevésnek bizonyult a szélességi bejárás használatához több pontból, így inkább azt a megoldást választottuk, hogy a játék elején a térkép bekérése után kiszámoljuk az összes pont között a távolságot, és azt egy távolságmátrixban eltároljuk.

Az algoritmus működik súlyozott élekkel is, illetve kettőnél több dimenziós vektorokkal, de most a 2D-s térképünkön nem volt ilyenre szükség.

A most megvalósított program a futása elején egy ilyen 2D-s térképet fog kapni:

A zöld, T betűvel jelölt mezőkön lehet menni, az F mezők pedig falak. Készítettem egy kis segédprogramot, amivel könnyen létre tudunk hozni ilyen térképeket anélkül, hogy a forráskódban kelljen megírni a boolean tömböt. A generátort ezen a linken érhetitek el: https://editor.p5js.org/palpista11/present/6kS7as4o1

Illesszük be a kódba tehát a térképet:

boolean[][] map = new boolean[][]{
    {true, false, true, true, ...},
    ...
};

Az algoritmus megírása csak most kezdődik. Hozzunk létre neki egy függvény! A visszatérési értéke egy 4 dimenziós mátrix lesz, aminek a d[x1][y1][x2][y2] eleme megadja az (x1;y1) és az (x2;y2) pontok távolságát az utakon haladva.

static int[][][][] floydWarshall(boolean[][] map){
     // Létrehozunk két változót a pálya méreteinek tárolására
     int w = map[0].length;
     int h = map.length;
        
     int[][][][] d = new int[w][h][w][h];   // Mátrix deklarálása
        
     // TODO megírni a kódot
        
     return d;
}

A következő lépés az lesz, hogy minden olyan egymás melletti pontot össze kell kötni egy 1 hosszú távolsággal, amiken mehetünk, tehát amik a map-en true-val vannak jelölve. Erre létrehoztam 4 darab for ciklust egymásban. A külső kettő a pár első pozícióján megy végig, a második kettő pedig a pár második pozícióin. A ciklusokon belül csak meg kell nézni, hogy egymás mellett vannak-e, és hogy mehetünk-e mindkét pozíción. Ha igen, akkor beállíthatjuk a távolságukat 1-re, ha nem, akkor pedig végtelenre (esetünkben 10000000). Ha mindkét koordináta egyenlő, a távolságuk természetesen 0 lesz.

int x1, y1, x2, y2;
for (x1 = 0; x1 < w; x1++) {
    for (y1 = 0; y1 < h; y1++) {
        for (x2 = 0; x2 < w; x2++) {
            for (y2 = 0; y2 < h; y2++) {
                if (map[y1][x1] && map[y2][x2]) {
                    if (x1 == x2 && y1 == y2) {
                        d[x1][y1][x2][y2] = 0; // Ugyanaz a mező
                    } else if (Math.abs(x1-x2) + Math.abs(y1-y2) == 1) {
                        d[x1][y1][x2][y2] = 1; // 1 Távolságra lévő mezők
                    } else {
                        d[x1][y1][x2][y2] = 10000000; // Tök random koordináták
                    }
                } else {
                    d[x1][y1][x2][y2] = 10000000; // Falról nem mehetünk sehova
                }
            }
        }
    }
}

A következő lépésben végigmegyünk az összes C pozíción két egymásba ágyazott for ciklussal. Ezen belül az a dolgunk, hogy megtaláljuk azokat a pontpárokat, amiknek a távolságát rövidítené az, ha nem A-ból B-be mennénk, hanem A-ból C-be, majd onnan B-be.

Az alábbi példán látható A és B pont távolsága kezdetben végtelen, mivel nem közvetlen szomszédjai egymásnak. Ha viszont a C ponton keresztülmegyünk, akkor az AC=1 és a CB=1 hosszok összege kisebb lesz, mint az eredeti hossz, tehát a C pont bevonása már hasznos.

Ha belegondolunk, akkor ez működni fog a távolabb levő pontpárokra is, de én nem gondolok bele, csak letesztelem a kódot.

int A_x, A_y, B_x, B_y, C_x, C_y;

for (C_x = 0; C_x < w; C_x++) {
    for (C_y = 0; C_y < h; C_y++) {
        for (A_x = 0; A_x < w; A_x++) {
            for (A_y = 0; A_y < h; A_y++) {
                for (B_x = 0; B_x < w; B_x++) {
                    for (B_y = 0; B_y < h; B_y++) {
                        if (d[A_x][A_y][B_x][B_y] > d[A_x][A_y][C_x][C_y] 
                                                   +d[C_x][C_y][B_x][B_y]) {
                            
                            d[A_x][A_y][B_x][B_y] = d[A_x][A_y][C_x][C_y] 
                                                   +d[C_x][C_y][B_x][B_y];
                        }
                    }
                }
            }
        }
    }
}

Ezután return-ölhetjük a d-t, azaz a distance matrixot.

return d;

A program végére írhatunk egy kijelzést, ami kiírja JSON-ben a mátrixot, így segíthet a tesztelésben.

int[][][][] d = floydWarshall(map);

String json = "[";
int A_x = 4;
int A_y = 1;

for (int B_y = 0; B_y < map.length; B_y++) {
    json += "[";
    for (int B_x = 0; B_x < map[0].length; B_x++) {
        json += d[A_x][A_y][B_x][B_y];
        if (B_x != map[0].length - 1) {
            json += ",";
        }
    }
    json += "]";
    if (B_y != map.length - 1) {
        json += ",";
    }
}
json += "]";
System.out.println(json);

Készítettem egy újabb csodálatos segédprogramot, aminek a bemenetébe beírhatjuk az előbb kiírt JSON tömböt, és kirajzol egy ilyen táblázatot: