0

我在迷宫中导航的递归算法花费的时间太长了。关于如何加快速度以提高效率的任何建议？现在，它通过了所有可能的解决方案。当我试图减少它时，它会跳过许多解决方案，包括最短的解决方案。如何减少解决方案的数量，或提前结束一些解决方案，同时不跳过最短的解决方案？

 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 查找最短路径（数字）。

4

1 回答 1

0

在初始位置（“开始”）设置一个矩阵 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
于 2013-11-01T22:25:06.933 回答