Рекурсия и алгоритм Дейкстры

Мой рекурсивный алгоритм навигации по лабиринту занимает слишком много времени. Любые предложения о том, как ускорить его, чтобы быть более эффективным? Прямо сейчас он перебирает все возможные решения. Когда я пытался сократить это, он пропускал многие решения, включая самые короткие. Как сократить количество решений или закончить некоторые решения раньше, не пропуская при этом самые короткие?

 private static void turnsforshortestmove(Vector2 location, int[,] board, int endrow, ref Boolean done, ref int[,] BOARDCHANGE, ref HashSet<int> h)
 //location is current location. board is the maze, endrow is the end y value to get to. it doesn't matter which x value, but as long as they get to the y value it's considered finishing.
 // done is a mistake, ignore it. BOARDCHANGE stores 
{
    //i need to compare all results for shortest
    //i need to cut off those that cant move
    if (location.Y == endrow)
    {
        h.Add(parseInt(board)); //counts how long the path is
        for (int r = 0; r < 19; r++)
            for (int c = 0; c < 19; c++)
                BOARDCHANGE[r, c] = board[r, c]; //sets the "real" board to have the path shown
    }
    else
    {

        int[,] boardCopy = new int[19, 19];
        for (int r = 0; r < 19; r++)
            for (int c = 0; c < 19; c++)
                boardCopy[r, c] = board[r, c];

        boardCopy[(int)location.X, (int)location.Y] = 8;


 //this part is saying if the square above isnt a wall, and two squares above isn't occupied, then do this function again

        if (boardCopy[(int)location.X, (int)location.Y - 1] == 1)
        {
            if (boardCopy[(int)location.X, (int)location.Y - 2] == 0)
            {
                turnsforshortestmove(new Vector2(location.X, location.Y - 2), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
            }
        }    
        if (boardCopy[(int)location.X - 1, (int)location.Y] == 1)
        {
            if (boardCopy[(int)location.X - 2, (int)location.Y] == 0)
            {
                turnsforshortestmove(new Vector2(location.X - 2, location.Y), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
            }
        }
        if (boardCopy[(int)location.X + 1, (int)location.Y] == 1)
        {
            if (boardCopy[(int)location.X + 2, (int)location.Y] == 0)
            {
                turnsforshortestmove(new Vector2(location.X + 2, location.Y), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
            }
        }
        if (boardCopy[(int)location.X, (int)location.Y + 1] == 1)
        {
            if (boardCopy[(int)location.X, (int)location.Y + 2] == 0)
            {
                turnsforshortestmove(new Vector2(location.X, location.Y + 2), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
            }
        }
    }
}

В конце он просматривает Hashset, чтобы найти кратчайший путь (число).


c# recursion dijkstra maze xna
person user2939446    schedule 01.11.2013    source источник
comment
Это не особо понятно. Вы используете здесь алгоритм Дейкстры?   -  person Oliver Charlesworth    schedule 02.11.2013
comment
@OliCharlesworth Я думаю, что его код сейчас грубо форсирует решение.   -  person DashControl    schedule 02.11.2013
comment
Это решается простым поиском в ширину. Начните с матрицы с 0 в начальной позиции, max int везде. Поместите начальную позицию в очередь. Затем продолжайте проходить через очередь и для каждой позиции в очереди, если сосед, не являющийся стеной, является › текущим + 1 в матрице, установите соседа в текущий + 1 в матрице и добавьте его позицию в очередь. Как только вы доберетесь до первой позиции с y = желаемое y, вы можете вернуться от нее, чтобы получить кратчайший путь.   -  person svinja    schedule 02.11.2013
comment
Таким образом, плата будет передаваться по ссылке, чтобы каждое ответвление лабиринта имело доступ к основной плате?   -  person user2939446    schedule 02.11.2013
comment
Я не понимаю, что вы имеете в виду. Обхода нет, алгоритм, который я описываю, не использует рекурсию. Он использует матрицу целых чисел, очередь позиций и цикл while.   -  person svinja    schedule 02.11.2013

Ответы (1)


arrow_upward
0
arrow_downward

Настройте матрицу M с 0 в начальном месте («начало») и max int везде. Также создайте очередь позиций.

Затем:

end = null
enqueue start
while queue is not empty
    p = dequeue
    if p.Y == desired_y
        end = p
        break
    for each neighbour of p // up, down, left, right
        if neighbour is not a wall and M[neighbour.X, neighbour.Y] > M[p.X, p.Y] + 1
            M[neighbour.X, neighbour.Y] = M[p.X, p.Y] + 1
            enqueue neighbour


if end == null
    return // no path exists

// now let's get the actual path, in reverse - from end to start
pos = end
path.add(pos)
while pos != start
    for each neighbour of pos
        if M[neighbour.X, neighbour.Y] == M[pos.X, pos.Y] - 1
            pos = neighbour
            path.add(pos)
            break


path.reverse // this is now your shortest path
person svinja    schedule 01.11.2013
comment
Что вы подразумеваете под очередью позиций? - person user2939446; 02.11.2013
comment
Структура данных очереди: en.wikipedia.org/wiki/Queue_(abstract_data_type) . В С# есть один, Queue<T>. Под положением я подразумеваю какую-то структуру/класс, который содержит координаты X и Y одного места на доске. Я предполагаю, что это ваш Vector2. Таким образом, вы должны использовать Queue<Vector2>. - person svinja; 02.11.2013
comment
Похоже на стеки в Java? - person user2939446; 02.11.2013
comment
Нет, очередь и стек — понятия противоположные. Стек - последний вошел - первый вышел, очередь - первый пришел - первый вышел. В стеке вы добавляете и берете с одного конца. В очереди вы добавляете к одному концу и берете с другого конца. - person svinja; 02.11.2013