Рекурсивные алгоритмы обречены на провал на большой сетке. Java не предназначен для глубоких рекурсий и может выдерживать несколько тысяч рекурсивных вызовов до сбоя с помощью StackOverflowException. Только итеративные решения - разумный подход для больших проблем с поиском путей в Java.
Конечно, вы всегда можете использовать классический алгоритм поиска пути, такой как A *, но вам придется применять его для каждой ячейки, что было бы чрезвычайно дорого.
Действительно, ваша проблема немного конкретна в том смысле, что вы хотите рассчитать минимальное расстояние до все ячейки, а не только один. Поэтому вы можете сделать это более умным способом.
Одно свойство вашей проблемы является то, что данный A и B, если минимальный путь от A к B содержит C этот путь также является минимальным из A в C и от C к B. Это то, что мне подсказывает моя интуиция, но перед тем, как применить мое предложение, нужно проверить его.
Алгоритма Я предлагаю эффективно использует O(n) памяти и имеет O(n^2) выполнение сложности (не может быть быстрее, так как вам нужно установить это множество ячеек в массиве):
- начать с первой точкой и установить расстояние от всех своих действительных соседей до
1. Сделав это, вы запишете границу , которая является всеми ячейками на расстоянии 1 от первой ячейки.
- Затем вы перебираете границу и берете всех своих соседей, которым еще не назначено расстояние, и назначьте их расстояние
2. Все ячейки дальности 2 станут вашей новой границей.
- итерация до границы пусто
Ниже приводится полный рабочий раствор. Код может быть улучшена различными способами, используя более удобные методы для инициализации и печати матриц объектов и простых чисел, но вы получите идею:
public class Solution {
public enum Cell { FREE, BLOCKED }
// assuming cells is a rectangular array with non-empty columns
public static int[][] distances(Cell[][] cells, ArrayCoordinate startingPoint) {
int[][] distances = new int[cells.length][cells[0].length];
// -1 will mean that the cell is unreachable from the startingPoint
for (int i = 0; i < cells.length; i++) {
for (int j = 0; j < cells[0].length; j++) {
distances[i][j] = -1;
}
}
distances[startingPoint.i][startingPoint.j] = 0;
Set<ArrayCoordinate> border = startingPoint.validNeighbours(cells);
for (int currentDistance = 1; !border.isEmpty(); currentDistance++) {
Set<ArrayCoordinate> newBorder = new HashSet<>();
for (ArrayCoordinate coord : border) {
distances[coord.i][coord.j] = currentDistance;
for (ArrayCoordinate neighbour : coord.validNeighbours(cells)) {
if (distances[neighbour.i][neighbour.j] < 0) {
newBorder.add(neighbour);
}
}
}
border = newBorder;
}
return distances;
}
private static class ArrayCoordinate {
public ArrayCoordinate(int i, int j) {
if (i < 0 || j < 0) throw new IllegalArgumentException("Array coordinates must be positive");
this.i = i;
this.j = j;
}
public final int i, j;
public Set<ArrayCoordinate> validNeighbours(Cell[][] cells) {
Set<ArrayCoordinate> neighbours = new HashSet<>();
// inlining for not doing extra work in a loop iterating over (-1, 1) x (-1, 1). If diagonals are allowed
// then switch for using a loop
addIfValid(cells, neighbours, 1, 0);
addIfValid(cells, neighbours, -1, 0);
addIfValid(cells, neighbours, 0, 1);
addIfValid(cells, neighbours, 0, -1);
return neighbours;
}
private void addIfValid(Cell[][] cells, Set<ArrayCoordinate> neighbours, int dx, int dy) {
int x = i + dx, y = j + dy;
if (0 <= x && 0 <= y && x < cells.length && y < cells[0].length && cells[x][y] == Cell.FREE) {
neighbours.add(new ArrayCoordinate(i + dx, j + dy));
}
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ArrayCoordinate point = (ArrayCoordinate) o;
if (i != point.i) return false;
if (j != point.j) return false;
return true;
}
@Override
public int hashCode() {
int result = i;
result = 31 * result + j;
return result;
}
}
public static void main(String[] args) {
int n = 11, m = 5;
Cell[][] cells = new Cell[n][m];
cells[1][1] = Cell.BLOCKED;
cells[1][2] = Cell.BLOCKED;
cells[2][1] = Cell.BLOCKED;
ArrayCoordinate startingPoint = new ArrayCoordinate(5, 2);
System.out.println("Initial matrix:");
for (int i = 0; i < cells.length; i++) {
for (int j = 0; j < cells[0].length; j++) {
if (cells[i][j] == null) {
cells[i][j] = Cell.FREE;
}
if (startingPoint.i == i && startingPoint.j == j) {
System.out.print("S ");
} else {
System.out.print(cells[i][j] == Cell.FREE ? ". " : "X ");
}
}
System.out.println();
}
int[][] distances = distances(cells, startingPoint);
System.out.println("\nDistances from starting point:");
for (int i = 0; i < distances.length; i++) {
for (int j = 0; j < distances[0].length; j++) {
System.out.print((distances[i][j] < 0 ? "X" : distances[i][j]) + " ");
}
System.out.println();
}
}
}
Выход:
Initial matrix:
. . . . .
. X X . .
. X . . .
. . . . .
. . . . .
. . S . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
Distances from starting point:
7 8 7 6 7
6 X X 5 6
5 X 3 4 5
4 3 2 3 4
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4
5 4 3 4 5
6 5 4 5 6
7 6 5 6 7
Bonus
Я почти заплакал, увидев весь этот шаблон в своем решении Java, поэтому я написал более короткую (возможно, немного менее эффективную) версию в Scala:
object ScalaSolution {
sealed abstract class Cell
object Free extends Cell
object Blocked extends Cell
// assuming cells is a rectangular array with non-empty columns
def distances(cells: Array[Array[Cell]], startingPoint: (Int, Int)) = {
// -1 will mean that the cell is unreachable from the startingPoint
val distances = Array.fill[Int](cells.length, cells(0).length)(-1)
distances(startingPoint._1)(startingPoint._2) = 0
var (currentDistance, border) = (1, validNeighbours(cells, startingPoint))
while (border.nonEmpty) {
border.foreach { case (i, j) => distances(i)(j) = currentDistance }
border = border.flatMap(validNeighbours(cells, _)).filter { case (i, j) => distances(i)(j) < 0 }
currentDistance += 1
}
distances
}
private def validNeighbours(cells: Array[Array[Cell]], startingPoint: (Int, Int)) = {
// inlining for not doing extra work in a for yield iterating over (-1, 1) x (-1, 1). If diagonals are allowed
// then switch for using a for yield
Set(neighbourIfValid(cells, startingPoint, (1, 0)),
neighbourIfValid(cells, startingPoint, (-1, 0)),
neighbourIfValid(cells, startingPoint, (0, 1)),
neighbourIfValid(cells, startingPoint, (0, -1)))
.flatten
}
private def neighbourIfValid(cells: Array[Array[Cell]], origin: (Int, Int), delta: (Int, Int)) = {
val (x, y) = (origin._1 + delta._1, origin._2 + delta._2)
if (0 <= x && 0 <= y && x < cells.length && y < cells(0).length && cells(x)(y) == Free) {
Some(x, y)
} else None
}
def main (args: Array[String]): Unit = {
val (n, m) = (11, 5)
val cells: Array[Array[Cell]] = Array.fill(n, m)(Free)
cells(1)(1) = Blocked
cells(1)(2) = Blocked
cells(2)(1) = Blocked
val startingPoint = (5, 2)
println("Initial matrix:")
printMatrix(cells)((i, j, value) => if ((i, j) == startingPoint) "S" else if (value == Free) "." else "X")
val distancesMatrix = distances(cells, startingPoint)
println("\nDistances from starting point:")
printMatrix(distancesMatrix)((i, j, value) => if (value < 0) "X" else value.toString)
}
private def printMatrix[T](matrix: Array[Array[T]])(formatter: (Int, Int, T) => String) = {
for (i <- 0 until matrix.length) {
for (j <- 0 until matrix(0).length) {
print(formatter(i, j, matrix(i)(j)) + " ")
}
println()
}
}
}
Ваша проблема выглядит как путь нахождения. Возможно, вы можете проверить алгоритм A *. – Nico
Эта страница [http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html) точно описывает вашу проблему, пустые пространства сродни препятствиям, которые обсуждались на этой странице. – SomeDude
Проверьте мой ответ, который приведет к значительно лучшей производительности, чем применение A * несколько раз, и будет довольно просто реализовать – Dici