Алгоритм Флойд-Уоршалла

Question

В настоящее время я работаю над небольшим проектом защиты башни на Java, и я застрял с поиском пути. Я много читал об A* dijkstra и подобных вещах, но я решил, что, вероятно, лучше всего использовать Floyd-Warshall для поиска пути (по крайней мере, мне кажется, что он решает проблему кратчайшего пути из всех пар).

Во всяком случае, я пытался реализовать его самостоятельно, но он не работает должным образом. я использовал код в Википедии как начало http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Итак, вот мой код:

public class MyMap {
public class MyMapNode {
    // list of neighbour nodes
    public List<MyMapNode> neighbours;
    // Currently no need for this :)
    public int cellX, cellY;
    // NodeIndex for pathreconstruction
    public int index;
    // this value is checked by units on map to decide wether path needs
    // reconstruction
    public boolean isFree = true;

    public MyMapNode(int cellX, int cellY, int index) {
        this.cellX = cellX;
        this.cellY = cellY;
        this.index = index;
        neighbours = new ArrayList<MyMapNode>();
    }

    public void addNeighbour(MyMapNode neighbour) {
        neighbours.add(neighbour);
    }

    public void removeNeighbour(MyMapNode neighbour) {
        neighbours.remove(neighbour);
    }

    public boolean isNeighbour(MyMapNode node) {
        return neighbours.contains(node);
    }
}
//MapSize
public static final int CELLS_X = 10;
public static final int CELLS_Y = 10;

public MyMapNode[][] map;

public MyMap() {
    //Fill Map with Nodes
    map = new MyMapNode[CELLS_X][CELLS_Y];
    for (int i = 0; i < CELLS_X; i++) {
        for (int j = 0; j < CELLS_Y; j++) {
            map[i][j] = new MyMapNode(i, j, j + i * CELLS_Y);
        }
    }
    //-------------------------------------------------
    initNeighbours();
    recalculatePath();
}

public void initNeighbours() {
    //init neighbourhood without diagonals
    for (int i = 0; i < CELLS_X; i++) {
        for (int j = 0; j < CELLS_Y; j++) {
            int x, y;// untere Grenze
            if (j == 0)
                y = 0;
            else
                y = -1;
            if (i == 0)
                x = 0;
            else
                x = -1;
            int v, w;// obere Grenze
            if (j == CELLS_Y - 1)
                w = 0;
            else
                w = 1;
            if (i == CELLS_X - 1)
                v = 0;
            else
                v = 1;
            for (int h = x; h <= v; h++) {
                if (h != 0)
                    map[i][j].addNeighbour(map[i + h][j]);
            }
            for (int g = y; g <= w; g++) {
                if (g != 0)
                    map[i][j].addNeighbour(map[i][j + g]);
            }

        }
    }
}
//AdjacencyMatrix
public int[][] path = new int[CELLS_X * CELLS_Y][CELLS_X * CELLS_Y];
//for pathreconstruction
public MyMapNode[][] next = new MyMapNode[CELLS_X * CELLS_Y][CELLS_X
        * CELLS_Y];

public void initAdjacency() {
    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map[0].length; j++) {
            path[i][j] = 1000;
            List<MyMapNode> tmp = map[i][j].neighbours;
            for (MyMapNode m : tmp) {
                path[m.index][map[i][j].index] = 1;
                path[map[i][j].index][m.index] = 1;
            }
        }
    }
}

public void floydWarshall() {
    int n = CELLS_X * CELLS_Y;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (path[i][k] + path[k][j] < path[i][j]) {
                    path[i][j] = path[i][k] + path[k][j];
                    next[i][j] = getNodeWithIndex(k);
                }
            }
        }
    }
}

public void recalculatePath() {
    initAdjacency();
    floydWarshall();
}

public MyMapNode getNextWayPoint(MyMapNode i, MyMapNode j) {
    if (path[i.index][j.index] >=1000)
        return null;
    MyMapNode intermediate = next[i.index][j.index];
    if (intermediate == null)
        return j; /* there is an edge from i to j, with no vertices between */
    else
        return getNextWayPoint(i, intermediate);
}

public MyMapNode getNodeWithIndex(int k) {
    //for testing purpose,this can be done faster
    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map[0].length; j++) {
            if (map[i][j].index == k)
                return map[i][j];
        }
    }
    return null;
}

public void removeMapNode(MyMapNode m) {
    //for testing purpose,this can be done faster
    m.isFree = false;
    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map[0].length; j++) {
            if (map[i][j].neighbours.contains(m)) {
                map[i][j].neighbours.remove(m);
            }
        }
    }
}

}

Алгоритм Флойда-Варшалла разработан для работы с графом, поэтому я создаю такой, где каждый узел знает своих соседей (которые являются узлами, к которым он подключен).

Я на самом деле не знаю, где это идет не так, но как-то так. но, по крайней мере, похоже, что инициализация матрицы смежности работает.

в функции floydwarshall я надеялся получить индекс следующего узла в следующем [][], но я получил только ноль или 10/11;

Так что мой вопрос в том, что я делаю неправильно или мой подход вообще неверен? Я надеюсь, что кто-то может помочь мне. если вам нужна дополнительная информация, пожалуйста, спросите

извините за мой плохой английский;)

Answer 1

У меня нет Java, но кажется, что ваша функция initAdjacency() имеет недостатки. путь [] [] имеет размер [CELL_X * CELLS_Y][CELLS_X * CELLS_Y], пока вы перебираете размеры карты [CELL_X][CELL_Y], поэтому вы не устанавливаете для всех элементов без ребер значение по умолчанию значение 1000, и они в конечном итоге 0.

Попробуйте добавить

for (int i = 0; i < CELLS_X * CELLS_Y; i++)
    for (int j = 0; j < CELLS_X * CELLS_Y; j++)
        path[i][j] = 1000;

в начале функции initAdjacency() перед вашим циклом, чтобы правильно инициализировать ее.

Вы также можете сделать

for (int i = 0; i < CELLS_X * CELLS_Y) path[i][i] = 0;

после этого на всякий случай, я не уверен, что это влияет на алгоритм.