रिकर्सिव एल्गोरिदम बड़े ग्रिड पर असफल होने के लिए बर्बाद हो जाते हैं। जावा गहरे रिकर्सन के लिए डिज़ाइन नहीं किया गया है और StackOverflowException के साथ विफल होने से पहले केवल कुछ हजार रिकर्सिव कॉल का सामना कर सकता है। जावा में बड़ी पथदर्शी समस्याओं के लिए केवल पुनरावृत्त समाधान ही एक तर्कसंगत दृष्टिकोण हैं।
बेशक आप हमेशा ए * जैसे क्लासिक पथदर्शी एल्गोरिदम का उपयोग कर सकते हैं, लेकिन आपको इसे प्रत्येक सेल के लिए लागू करना होगा, जो बेहद महंगा होगा।
दरअसल, आपकी समस्या इस अर्थ में थोड़ा सा विशेष है कि आप न्यूनतम दूरी की गणना सभी कोशिकाओं की गणना करना चाहते हैं और केवल एक ही नहीं। इसलिए, आप इसे अधिक चालाक तरीके से कर सकते हैं।आपकी समस्या का
एक संपत्ति है कि A और B दिया, अगर B को A से कम से कम पथ है 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
बोनस
जब मैंने अपने जावा समाधान में इस बॉयलरप्लेट को देखा तो मैंने लगभग रोया, इसलिए मैंने स्कैला में एक छोटा (शायद थोड़ा कम कुशल) संस्करण लिखा:
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()
}
}
}
आपकी समस्या पथ खोज की तरह एक सा लग रहा है के बारे में अपनी शर्त पर जानकारी दे सकता है। आप शायद ए * एल्गोरिदम देख सकते हैं। – Nico
यह [पेज] (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html) आपकी समस्या का बिल्कुल वर्णन करता है, खाली स्थान उस पृष्ठ में बात की बाधाओं के समान हैं। – SomeDude
, मेरा उत्तर की जाँच करें जो एक * कई बार आवेदन करने की तुलना में बेहतर प्रदर्शन में परिणाम होगा, और बहुत लागू करने के लिए – Dici