Блог

Я программирую уже около пяти лет, и у меня не было проблем с созданием динамического лабиринта. Но теперь, когда дело доходит до рекурсивного обратного отслеживания, я совершенно не знаю, с чего начать. Я прочитал много руководств, тем и некоторых вики-алгоритмов (алгоритм Дейкстры), и они не имеют для меня никакого смысла.

Я знаю, как работает базовая рекурсия, но я просто не могу начать понимать, как рекурсивное обратное отслеживание вообще возможно без (как мне кажется) сохранения ранее найденных путей или что произойдет, если отслеживаемый путь внезапно разделится на две части.

Моя программа работает следующим образом: лабиринт состоит из 484 панелей (массив Panel[] с именем mazeTiles). Есть 22 строки, и каждая строка содержит 22 панели. Черные панели — это стены, белые — проходимые.

Вот как это выглядит во время выполнения (и сообщение об ошибке, которое должно отображаться только в том случае, если нет допустимого пути от начального квадрата (красного) до зеленого квадрата в левом верхнем углу:

http://postimg.org/image/6c7wgxtz1/

Отображаемое сообщение об ошибке гласит: «Лабиринт не может быть решен», хотя его явно можно решить. Это сообщение об ошибке находится в методе Button2_Click .

И ниже приведен код, который я взял из учебника (и модифицировал), проблема определенно находится внутри метода, но я понятия не имею, как устранить это.

     private void button2_Click(object sender, EventArgs e)
    {
        int startPosition = 0;

        for (int i = 0; i < mazeTiles.Length; i  )
        {
            if (mazeTiles[i].BackColor == Color.Red)
            {
                startPosition = i;
            }
        }

        bool[] alreadySearched = new bool[484];

        if (!solveMaze(startPosition, alreadySearched))
            MessageBox.Show("Maze can not be solved.");
    }

    private bool solveMaze(int position, bool[] alreadySearched)
    {
        bool correctPath = false;

        //should the computer check this tile
        bool shouldCheck = true;

        //Check for out of boundaries
        if (position >= mazeTiles.Length || position < 0 )
            shouldCheck = false;
        else
        {
            //Check if at finish, not (0,0 and colored light blue)
            if (mazeTiles[position].BackColor == Color.Green)
            {
                correctPath = true;
                shouldCheck = false;
            }
            //Check for a wall
            if (mazeTiles[position].BackColor == Color.Black)
                shouldCheck = false;
            //Check if previously searched
            if (alreadySearched[position])
                shouldCheck = false;
        }
        //Search the Tile
        if (shouldCheck)
        {
            //mark tile as searched
            alreadySearched[position] = true;
            //Check right tile
            correctPath = correctPath || solveMaze(position   1, alreadySearched);
            //Check down tile
            correctPath = correctPath || solveMaze(position   22, alreadySearched);
            //check left tile
            correctPath = correctPath || solveMaze(position - 1, alreadySearched);
            //check up tile
            correctPath = correctPath || solveMaze(position - 22, alreadySearched);
        }

        //make correct path gray
        if (correctPath)
            mazeTiles[position].BackColor = Color.Gray;

        return correctPath;
    }
  

Мне нужно найти и сохранить все пути или самый быстрый (и отметить только самый быстрый) от красного квадрата до зеленого. Зеленый квадрат статичен, но красный квадрат и весь лабиринт генерируются случайным образом.

Прошло два года, и этот пост не получил ответа. Ответ, который я искал тогда, был объяснением, которое заставило меня понять, как работает рекурсивное обратное отслеживание. У меня было много проблем с выяснением, как метод знал, где он был раньше, по-видимому, без сохранения посещенных областей, чтобы не повторять один и тот же путь снова и снова (бесконечный цикл). Но как только я понял, как это работает, я сразу понял, как написать код.

Так что, если кто-нибудь наткнется на это, задаваясь тем же вопросом. Простой способ понять рекурсивное обратное отслеживание — понять, как работают рекурсивные методы. Рекурсивные методы продолжают вызывать себя снова и снова, пока не будет найден правильный ответ. Рекурсивное обратное отслеживание продолжает вызывать себя внутри себя, чтобы найти правильный ответ. Таким образом, многие базовые рекурсивные методы заменяют себя, поэтому часто существует только один его экземпляр за раз, в то время как рекурсивные методы обратного отслеживания часто накладываются друг на друга.

При решении головоломки метод продолжает вызывать себя снова и снова внутри себя (в стиле начала), постоянно делая один шаг в направлении, пока в этом направлении больше не будет шагов. На этом этот экземпляр заканчивается, а предыдущий, который его вызвал, продолжает работать. И как только этот экземпляр завершится, предыдущий экземпляр будет продолжен (и он может сделать тысячу собственных включений).

Если у вас все еще возникают проблемы с пониманием, подумайте о том, как вы теперь оказались в ловушке внутри лабиринта. У вас есть одна сверхдержава, и она не летает, а клонирует. Таким образом, вы продолжаете двигаться вперед, пока путь не разделится. Это когда вы клонируете себя и отправляете его на свое место, в то время как оригинал you не двигается, пока клон не найдет выход или не зайдет в тупик, тогда клон телепортируется обратно к вам и делится своей информацией. Но если ваш клон также сталкивается с разделенным путем, он клонирует себя и ждет, пока его клон вернется со знанием лабиринта. И этот клон вашего клона также может создавать бесконечное количество клонов в зависимости от того, сколько раз путь разделяется. В конечном итоге все эти объединенные знания возвращаются к вам. И тогда вы будете точно знать, где найти выход из лабиринта.

Ваша проблема слишком широка. Вам нужно опубликовать конкретный вопрос. Похоже, вы пытаетесь выполнить домашнее задание.

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

Вероятно, вам потребуется свойство уровня класса для хранения кратчайшего пути, поскольку вы уже возвращаете bool, или вы можете использовать переменную out . Массив, который вы передаете рекурсивному методу, будет тем местом, где вы храните все ранее проверенные индексы, которые я предполагаю.