大尺寸迷宫求解器的 OutOfMemoryException

Question

该程序适用于最大 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 的数组

Answer 1

嗯，看了你的代码我发现了一个问题。您执行了错误的检查。您应该检查您的点是否已添加到队列中。你现在做什么？我们会的，您只是将已处理的单元格标记为未打开。很容易看出您可以将同一节点添加到队列两次。

让我们以我的例子为例：

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)

现在我们在队列中有两次相同的点。那不是你的最后一个问题。您的点数引用了它的所有父项，因此您之前的点数（也加倍）无法使用垃圾收集器处理。

Answer 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;
            }

        }

大尺寸迷宫求解器的 OutOfMemoryException

OutOfMemoryException For Maze Solver of Large Dimensions

c#

arrays

maze