Код для sokobansolver использует слишком много памяти и работает слишком медленно - PullRequest
Новая
       36

Код для sokobansolver использует слишком много памяти и работает слишком медленно

0 голосов
/ 30 июня 2019

У меня есть это консольное приложение SokobanSolver в c #, оно в основном с какого-то сайта, но я немного его изменил.Проблема в том, что он слишком медленный, и когда я использую большие головоломки (например, сетку 192x24), происходит сбой из-за исключения из памяти.У меня есть разные идеи, чтобы это исправить, но ни одна из них, похоже, не работает.

Проблема в том, что он создает список больших строк, с сеткой 192x24, которая содержит 4608 символов.Из-за BFS он проверяет каждую возможность, и даже с небольшим примером требуется около 400 попыток, чтобы найти правильный путь.Так что теперь у меня есть массив длиной 859251 из 4608 символов каждый, что в итоге слишком много.Это займет около 6-8 минут.

Ниже приведен пример, где W - стена,?это цель,это поле, а + это игрок.Решение будет 9, LLUUULURR.(влево, вверх, вправо). 

      WWWWWWWW
      W....?.W
      W....WWW
      W....WWW
      W..!...W
      W....+.W
      W......W
      WWWWWWWW

это мой метод, чтобы увидеть, может ли игрок выдвинуть ящик, у меня почти точно такой же для игрока.Конечный метод - это когда коробка находится у цели. 

    public string Push(string smap, int x, int y, int dx, int dy)
    {
        // w = width 
        int cur = y * w + x;
        int newcur = (y + 2 * dy) * w + x + 2 * dx;
        int player = (y + dy) * w + (x + dx);

        if (smap[newcur] != '.')
            return "false";

        char[] map = smap.ToCharArray();
        map[player] = '+';
        map[cur] = '.';
        map[newcur] = '!';

        string res = string.Join("", map);
        return res;

    }

И это мой метод BFS, который использует очередь 

    public string BFS()
    {

        Queue<Node> Q = new Queue<Node>();
        Dictionary<Node, char> D = new Dictionary<Node, char>();
        ISet<string> visited = new HashSet<string>();
        Queue<string> steps = new Queue<string>();
        Queue<string> blueprint = new Queue<string>();
        steps.Enqueue("");

        Node North = new Node(-1, 0);
        Node South = new Node(1, 0);
        Node East = new Node(0, 1);
        Node West = new Node(0, -1);

        D.Add(North, 'U');
        D.Add(South, 'D');
        D.Add(East, 'R');
        D.Add(West, 'L');

        Q.Enqueue(new Node(posx, posy));
        // mapvar is the original blueprint 
        blueprint.Enqueue(mapvar);

        while (Q.Count > 0)
        {
            Node start = Q.Dequeue();
            int x = start.x;
            int y = start.y;
            string map1 = blueprint.Dequeue();
            string step = steps.Dequeue();

            for (int i = 0; i < 4; i++)
            {
                int DX = 0; int DY = 0;
                List<int> dxl = new List<int>();
                List<int> dyl = new List<int>();
                string map = map1;


                foreach (KeyValuePair<Node, char> kp in D)
                {
                    DX = kp.Key.x;
                    DY = kp.Key.y;

                    dxl.Add(kp.Key.x);
                    dyl.Add(kp.Key.y);
                }

                int dx = dxl[i];
                int dy = dyl[i];
                int move = b * (y + dy) + x + dx;                    

                if (map[(y + dy) * b + x + dx] == '!')
                {
                    if ((map = Push(map, x, y, dx, dy)) != "false")
                    {
                        if (!visited.Contains(map))
                        {

                            string st = "";
                            if (dy == -1)
                                st = step + D[North];
                            if (dy == 1)
                                st = step + D[South];
                            if (dx == 1)
                                st = step + D[East];
                            if (dx == -1)
                                st = step + D[West];


                            steps.Enqueue(st);
                            Q.Enqueue(new Node(x + dx, y + dy));
                            visited.Add(map);
                            blueprint.Enqueue(map);
                            if (End(map))
                                return st;

                        }
                    }
                }
                else if ((map = Push(map, x, y, dx, dy)) != "false")
                {
                    if (!visited.Contains(map))
                    {

                        string st = "";
                        if (dy == -1)
                            st = step + D[North];
                        if (dy == 1)
                            st = step + D[South];
                        if (dx == 1)
                            st = step + D[East];
                        if (dx == -1)
                            st = step + D[West];

                           steps.Enqueue(st);
                        Q.Enqueue(new Node(x + dx, y + dy));
                        blueprint.Enqueue(map);
                        visited.Add(map);
                    }
                }

            }
        }
        return "false";
    }

Я подумал, может быть, разумнее сделать это сузлы или координаты вместо строки.Проблема в том, что я не уверен, как, потому что методы, которые я попробовал, не работали.Я надеюсь, что кто-то может помочь.Это работает, но это слишком медленно.Я действительно хочу использовать BFS, поэтому я надеюсь, что найдется решение, в котором я смогу его использовать.

...