OutOfMemoryException для лабиринта большого размера
Программа работает для массивов размером до 20x20, но для чего-то большего она создает исключение OutOfMemoryException.
Ниже приведен код:
public static Point GetFinalPath(int x, int y) {
queue.Enqueue(new Point(x,y, null));
while(queue.Count>0) {
Point p = queue.Dequeue();
if (arr[p.x,p.y] == 9) {
Console.WriteLine("Found Destination");
return p;
}
if(IsOpen(p.x+1,p.y)) {
arr[p.x,p.y] = 1;
queue.Enqueue(new Point(p.x+1,p.y, p));
}
//similarly for the other directions
}
return null;
}
public int[,] SolutionMaze()
{
Point p = GetFinalPath(0, 0);
while (p.getParent() != null)
{
solvedarray[p.x, p.y] = 9;
p = p.getParent();
}
return solvedarray;
}
ок, люди здесь остальная часть кода
public static Queue<Point> queue=new Queue<Point>();
public static bool IsOpen(int x, int y)
{
//BOUND CHECKING
if ((x >= 0 && x < XMAX) && (y >= 0 && y < YMAX) && (arr[x,y] == 0 || arr[x,y] == 9))
{
return true;
}
return false;
}
public class Point
{
public int x;
public int y;
Point parent;
public Point(int x, int y, Point parent)
{
this.x = x;
this.y = y;
this.parent = parent;
}
public Point getParent()
{
return this.parent;
}
}
Предполагается, что начало 0,0, а конечный пункт назначения равен 9 в конструкторе.
Помогите мне реализовать это для массива размером 500x500
2 ответа
Хорошо, я нашел ответ на OutOfMemory. Теперь код работает даже для матрицы 500x500. Как оказалось, я только что реализовал список узлов, который отслеживает добавленные узлы в очереди, используя формулу y*MAX_X_LENGTH + x
public static Queue<Point> queue=new Queue<Point>();
public SolveMaze(int[,] array,int staX,int staY,int finX,int finY)
{
//sets Destination as 9
arr = array;
XMAX = array.GetLength(0);
YMAX = array.GetLength(1);
finishY = finX; finishX = finY; startY = staX; startX = staY;
solvedarray = new int[XMAX, YMAX];
}
public static List<int> nodelist=new List<int>();
public void AddPointToQueueIfOpenAndNotAlreadyPresent(Point p,int direction)
{
if (nodelist.Contains(XMAX * p.y + p.x))
return;
else
{
switch(direction){
case 1:
//north
if (IsOpen(p.x, p.y - 1))
{
arr[p.x, p.y] = 1;
queue.Enqueue(new Point(p.x, p.y - 1, p));
nodelist.Add(XMAX * (p.y - 1) + p.x);
}
break;
case 0:
//east
if (IsOpen(p.x + 1, p.y))
{
arr[p.x, p.y] = 1;
queue.Enqueue(new Point(p.x + 1, p.y, p));
nodelist.Add(XMAX * (p.y) + p.x + 1);
}
break;
case 3:
//south
if (IsOpen(p.x, p.y + 1))
{
arr[p.x, p.y] = 1;
queue.Enqueue(new Point(p.x, p.y +1, p));
nodelist.Add(XMAX * (p.y + 1) + p.x);
}
break;
case 2:
//west
if (IsOpen(p.x - 1, p.y))
{
arr[p.x, p.y] = 1;
queue.Enqueue(new Point(p.x - 1, p.y, p));
nodelist.Add(XMAX * (p.y) + p.x-1);
}
break; }
}
}
public Point GetFinalPath(int x, int y) {
if (arr[finishX, finishY] == 0)
arr[finishX, finishY] = 9;
else
return null;
queue.Enqueue(new Point(x, y, null));
nodelist.Add(XMAX * y + x);
while(queue.Count>0) {
Point p = queue.Dequeue();
nodelist.Remove(p.y * XMAX + p.x);
if (arr[p.x,p.y] == 9) {
Console.WriteLine("Exit is reached!");
return p;
}
for (int i = 0; i < 4; i++)
{
AddPointToQueueIfOpenAndNotAlreadyPresent(p, i);
}
}
return null;
}
public static bool IsOpen(int x, int y)
{
//BOUND CHECKING
if ((x >= 0 && x < XMAX) && (y >= 0 && y < YMAX) && (arr[x,y] == 0 || arr[x,y] == 9))
{
return true;
}
return false;
}
public int[,] SolutionMaze()
{
Point p = GetFinalPath(startX, startY);
if(p!=null)
while (p.getParent() != null)
{
solvedarray[p.x, p.y] = 9;
p = p.getParent();
}
return solvedarray;
}
}
public class Point
{
public int x;
public int y;
Point parent;
public Point(int x, int y, Point parent)
{
this.x = x;
this.y = y;
this.parent = parent;
}
public Point getParent()
{
return this.parent;
}
}
Ну, глядя на ваш код, я обнаружил одну проблему. Вы выполняете неправильную проверку. Вы должны проверить, добавлена ли ваша точка в очередь. Чем вы сейчас занимаетесь? Мы просто помечаем обработанную ячейку как не открытую. Легко видеть, что вы можете добавить в очередь один и тот же узел дважды.
Давайте последуем моему примеру:
1 | . .
0 | ! .
--+----
yx| 0 1
Queue: point (0,0)
Мы начинаем с точки (0,0). В этот момент мы добавляем точки (0, 1) и (1,0) в нашу очередь и отмечаем точку (0,0) как обработанную
1 | . .
0 | X !
--+----
yx| 0 1
Queue: point (0,1), point (1,0)
Теперь мы снимаем точку с точки (0,1), отмечаем ее обработкой и добавляем точку (1,1) в очередь.
1 | ! .
0 | X X
--+----
yx| 0 1
Queue: point (1,0), point(1,1)
Теперь мы удаляем точку (1,0), помечая ее как обработанную и добавляя точку (1,1) в очередь:
1 | X !
0 | X X
--+----
yx| 0 1
Queue: point (1,1), point (1,1)
И теперь мы имеем одну и ту же точку дважды в очереди. И это не твоя последняя проблема. Ваши баллы имеют отношение ко всем родителям, поэтому ваши предыдущие баллы (тоже удвоенные) не могут быть обработаны с помощью сборщика мусора.