编程理论:解迷宫

你可以把迷宫想象成一棵树。

     A
    / \
   /   \
  B     C
 / \   / \
D   E F   G
   / \     \
  H   I     J
 / \
L   M
   / \
  **  O

(which could possibly represent)

        START
        +   +---+---+
        | A   C   G |
    +---+   +   +   +
    | D   B | F | J |
+---+---+   +---+---+
| L   H   E   I |
+---+   +---+---+
    | M   O |
    +   +---+
    FINISH

(ignoring left-right ordering on the tree)

其中每个节点都是路径的连接点。D、I、J、L和O是死胡同,目标是**。 当然,在实际的树中,每个节点都有可能拥有 三 孩子们。

现在,您的目标只是找到要遍历哪些节点才能找到完成点。任何一种树搜索算法都可以。

从树的最深处的**可以很容易地看到正确的解决方案:

A B E H M **

注意,这种方法 只有轻微 更复杂的是,当你在迷宫中有“循环”(也就是说,如果可能的话,没有回溯,你就重新进入一个你已经穿过的通道)。检查注释以获得一个好的解决方案。

现在,让我们看看您提到的第一个解决方案,应用于此树。

您的第一个解决方案基本上是 Depth-First Search 这还不错。实际上这是一个很好的递归搜索。基本上,它说,“总是先采用最右边的方法。如果什么都没有的话,回溯到第一个地方,你可以直行或左行,然后重复。

深度优先搜索将按以下顺序搜索上述树:

A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J

请注意,找到**后可以立即停止。

但是,当您实际对深度优先搜索进行编码时,使用 递归编程 使一切变得更容易。即使是迭代方法也可以工作,而且您永远不必显式地编程如何回溯。查看链接的文章以了解实现。

另一种搜索树的方法是 Breadth-First 解决方案,按深度搜索树。它将按以下顺序搜索上面的树:

A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O

请注意,由于迷宫的性质,宽度优先检查节点的平均数量要高得多。宽度优先是很容易实现的,它有一个要搜索的路径队列,每次迭代都会从队列中弹出一条路径,“分解它”,方法是在一个步骤之后获取它可以转化为的所有路径,并将这些新路径放在队列的末尾。没有明确的“下一级”命令来编码,而这些命令只是用来帮助理解。

事实上,有一个整体 expansive list of ways to search a tree . 我刚刚提到了两种最简单、最直接的方法。

如果你的迷宫非常,非常长和深,并且有环形和疯狂,并且很复杂,我建议 A* 算法,这是行业标准的寻路算法,它结合了广度优先搜索和启发式搜索…有点像“智能广度优先搜索”。

它基本上是这样工作的:

1. 把一条路排成一列(你只走一步就进入迷宫的那条路)。路径的“权重”由其当前长度+其与末端的直线距离(可通过数学计算得出)得出。
2. 从队列中弹出权重最小的路径。
3. 将路径“分解”为每一条可能经过一步的路径。(例如,如果您的路径是右左右,则分解的路径是R L L R和R L L R L,不包括穿过墙壁的非法路径)
4. 如果其中一条路有目标,那就胜利吧!否则:
5. 计算分解路径的权重,并将所有分解路径放回队列(不包括原始路径)
6. 按重量对队列进行排序,最低者优先。然后重复步骤2

那就是 A* 这是我特别强调的,因为它或多或少是行业标准的寻路算法 全部的 寻路的应用,包括从地图的一个边缘移动到另一个边缘,同时避开非公路路径或山脉等。由于它使用了 最短可能距离启发式 这给了它“智慧”。A*是如此的通用,因为在任何问题上,如果你有一个最短的可能距离启发式可用(我们的是容易的——直线),你可以应用它。

但是 值得注意的是 不 你唯一的选择。

事实上, wikipedia category of tree traversal algorithms 仅列出97个!(最好的仍然在 this page 链接较早)

对不起,长度=P(我喜欢闲聊)

有很多迷宫求解算法:

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://www.astrolog.org/labyrnth/algrithm.htm#solve

对于机器人来说, Tremaux's algorithm 看起来很有前途。

一个有趣的方法,至少我觉得它有趣,是使用细胞自动机。简而言之,由3个“墙”单元包围的“空间”单元变成“墙”单元。在最后,剩下的空间单元只有在通往出口的路线上。

如果你看贾斯汀在他的答案中写的树,你会发现叶节点有三个墙。修剪这棵树直到你有一条路。

如何从矩阵中构建一个图,并使用广度优先搜索、深度优先搜索或dijkstras算法?

这是我最喜欢的算法之一…

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

这是一个非常简单的表示来模拟C++中的迷宫。

#ifndef vAlgorithms_Interview_graph_maze_better_h
#define vAlgorithms_Interview_graph_maze_better_h

static const int kMaxRows = 100;
static const int kMaxColumns = 100;

class MazeSolver
    {
private:
    char m_matrix[kMaxRows][kMaxColumns]; //matrix representation of graph
    int rows, cols; //actual rows and columns

    bool m_exit_found;
    int m_exit_row, m_exit_col;
    int m_entrance_row, m_entrance_col;

    struct square //abstraction for data stored in every verex
        {
        pair<int, int> m_coord; //x and y co-ordinates of the matrix
        square* m_parent; //to trace the path backwards

        square() : m_parent(0) {}
        };

    queue<square*> Q;

public:
    MazeSolver(const char* filename)
        : m_exit_found(false)
        , m_exit_row(0)
        , m_exit_col(0)
        , m_entrance_row(0)
        , m_entrance_col(0)
        {
        ifstream file;
        file.open(filename);

        if(!file)
            {
            cout << "could not open the file" << endl << flush;
            // in real world, put this in second phase constructor
            }
        init_matrix(file);
        }
    ~MazeSolver()
        {
        }
    void solve_maze()
        {
        //we will basically use BFS: keep pushing squares on q, visit all 4 neighbors and see
        //which way can we proceed depending on obstacle(wall)

        square* s = new square();
        s->m_coord = make_pair(m_entrance_row, m_entrance_col);

        Q.push(s);

        while(!m_exit_found && !Q.empty())
            {
            s = Q.front();
            Q.pop();

            int x = s->m_coord.first;
            int y = s->m_coord.second;
            //check if this square is an exit cell
            if(x == m_exit_row && y == m_exit_col)
                {
                m_matrix[x][y] = '>'; // end of the path
                m_exit_found = true;
                //todo: try breaking? no= queue wont empty
                }
            else
                {
                //try walking all 4 neighbors and select best path
                //NOTE: Since we check all 4 neighbors simultaneously,
                //      the path will be the shortest path
                walk_path(x-1, y, s);
                walk_path(x+1, y, s);
                walk_path(x, y-1, s);
                walk_path(x, y+1, s);
                }
            } /* end while */

        clear_maze(); //unset all previously marked visited shit

        //put the traversed path in maze for printing
        while(s->m_parent)
            {
            m_matrix[s->m_coord.first][s->m_coord.second] = '-';
            s = s->m_parent;
            } /* end while */
        }

    void print()
        {
        for(int i=0; i<rows; i++)
            {
            for(int j=0; j<cols; j++)
                cout << m_matrix[i][j];
            cout << endl << flush;
            }
        }

private:
    void init_matrix(ifstream& file)
        {
        //read the contents line-wise
        string line;
        int row=0;
        while(!file.eof())
            {
            std::getline(file, line);
            for(int i=0; i<line.size(); i++)
                {
                m_matrix[row][i] = line[i];
                }
            row++;
            if(line.size() > 0)
                {
                cols = line.size();
                }
            } /* end while */
        rows = row - 1;

        find_exit_and_entry();
        m_exit_found = false;
        }

    //find and mark ramp and exit points
    void find_exit_and_entry()
        {
        for(int i=0; i<rows; i++)
            {
            if(m_matrix[i][cols-1] == ' ')
                {
                m_exit_row = i;
                m_exit_col = cols - 1;
                }
            if(m_matrix[i][0] == ' ')
                {
                m_entrance_row = i;
                m_entrance_col = 0;
                }
            } /* end for */
        //mark entry and exit for testing
        m_matrix[m_entrance_row][m_entrance_col] = 's';
        m_matrix[m_exit_row][m_exit_col] = 'e';
        }

    void clear_maze()
        {
        for(int x=0; x<rows; x++)
            for(int y=0; y<cols; y++)
                if(m_matrix[x][y] == '-')
                    m_matrix[x][y] = ' ';
        }
        // Take a square, see if it's the exit. If not, 
        // push it onto the queue so its (possible) pathways
        // are checked.
    void walk_path(int x, int y, square* parent)
        {
        if(m_exit_found) return;
        if(x==m_exit_row && y==m_exit_col)
            {
            m_matrix[x][y] = '>';
            m_exit_found = true;
            }
        else
            {
            if(can_walk_at(x, y))
                {
                //tag this cell as visited
                m_matrix[x][y] = '-';

                cout << "can walk = " << x << ", " << y << endl << flush;

                //add to queue
                square* s = new square();
                s->m_parent = parent;
                s->m_coord = make_pair(x, y);
                Q.push(s);
                }
            }
        }

    bool can_walk_at(int x, int y)
        {
        bool oob = is_out_of_bounds(x, y);
        bool visited = m_matrix[x][y] == '-';
        bool walled = m_matrix[x][y] == '#';

        return ( !oob && !visited && !walled);
        }
    bool is_out_of_bounds(int x, int y)
        {
        if(x<0 || x > rows || y<0 || y>cols)
            return true;
        return false;
        }
    };


void run_test_graph_maze_better()
        {
        MazeSolver m("/Users/vshakya/Dropbox/private/graph/maze.txt");
        m.print();
        m.solve_maze();
        m.print();
        }


#endif

只是一个想法。为什么不以蒙特卡洛的方式在那里扔一些机器人呢? 让我们称第一代僵尸为gen0。 我们只将机器人程序与gen0保持距离,因为gen0有一些连续的道路:
-从一开始到某一点
或者-从某一点到最后

我们在新的随机点中运行一个新的gen1机器人程序,然后我们尝试将gen1机器人程序的道路与gen0机器人程序的道路连接起来,看看我们是否从开始到结束都有一条连续的道路。

所以对于genn,我们尝试连接gen0,gen1,…,genn-1形式的僵尸。

当然,一代人只持续有限的时间。

我不知道该算法的复杂性是否会证明对小数据集是可行的。
同时,该算法假定我们知道起始点和结束点。

一些好的创意网站:
http://citeseerx.ist.psu.edu/
http://arxiv.org/

我的大学毕业典礼上也遇到了类似的问题。SCI。课程。我们提出的解决方案是沿着左手边的墙(右手边的墙也会起作用)。这是一些伪代码

While Not At End
    If Square To Left is open,
        Rotate Left
        Go Forward
    Else
        Rotate Right
    End If
Wend

基本上就是这样。复杂的部分是跟踪你的面向哪个方向,并根据这个方向找出你左边的网格位置。它适用于我提出的任何测试用例。有趣的是,教授们的解决方案是:

While Not At End
    If Can Go North
        Go North
    ElseIf Can Go East
        Go East
    ElseIf Can Go South
        Go South
    ElseIf Can Go West 
        Go West
    EndIf
Wend

这对于大多数简单的迷宫都很有效,但在如下迷宫中失败:

SXXXXXXXXXXXXX
   X         X
   X         X
   X         X
 XXX         X
 X X         X
 X XXXXXXXXXXX     XXXE
 X                 X
 XXXXXXXXXXXXXXXXXXX

以S和E为起点和终点。

如果有什么东西跟不上墙,你就得把你去过的地方列一个清单,这样当你陷入死胡同时,你可以在必要的时候回溯,这样你就不会陷入循环。如果你沿着墙走,就没有必要跟踪你去过的地方。虽然你找不到穿过迷宫的最佳路径,但你总能通过迷宫。

如果机器人能跟踪到它的位置,那么它就知道它以前是否去过某个位置,那么深度优先搜索就是显而易见的算法。您可以通过一个敌对的论点来证明,不可能比深度优先搜索获得更好的最坏情况性能。

如果你可以使用机器人无法实现的技术,那么广度优先搜索对于许多迷宫可能会更好,就像Dijkstra在图中找到最短路径的算法一样。

有很多算法,很多 不同的设置 指定哪种算法是最好的。 这只是一个关于有趣环境的想法:

假设您具有以下属性…

• 你移动一个机器人,你想 使其移动最小化 ,而不是它的CPU使用率。
• 那个机器人要么只能检查邻近的细胞要么观察 走廊 不管是看到还是没有看到交叉路口。
• 它有 全球定位系统 .
• 它知道目的地的坐标。

然后你可以设计一个自动识别系统…

• 每次收到关于迷宫的新信息时,绘制地图。
• 计算已知的最小值 路径 长度 之间 全部的 未观察到的位置 (以及它本身和目的地)。
• 可以根据以下情况优先考虑未观察到的位置进行检查 周围结构 . (如果无论如何都无法从那里到达目的地…)
• 可以根据以下情况优先考虑未观察到的位置进行检查 方向和距离 到达目的地。
• 可以根据以下情况优先考虑未观察到的位置进行检查 收集信息的经验 . (它平均能看到多远,走多远?)
• 可以优先考虑未观察到的职位 查找可能的快捷方式 . (经验:有很多吗? 循环 ?)

与所有有关堆栈溢出的问题的答案相同;)

使用vi!

http://www.texteditors.org/cgi-bin/wiki.pl?Vi-Maze

看到一个文本编辑器解决一个ASCII迷宫真的很有意思,我相信Emacs的人有一个等价物。

这个azkaban算法也可以帮助你, http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

求解迷宫的最佳方法是使用连通性算法,如联合查找(union find),它是假设路径压缩完成的准线性时间算法。

联合查找是一种数据结构,它告诉您一个集合中的两个元素是否是可传递连接的。

为了利用联合查找数据结构来解决迷宫问题,首先利用邻接数据构建联合查找数据结构。然后压缩联合查找。为了确定迷宫是否可解,对入口和出口值进行了比较。如果它们有相同的值,那么它们是相连的,迷宫是可解的。最后,为了找到一个解决方案,您从入口开始,并检查与每个邻居关联的根。一旦找到与当前单元格具有相同根目录的以前未访问的邻居,就访问该单元格并重复该过程。

这种方法的主要缺点是,如果有多条路径,它不会告诉你迷宫中最短的路径。

不是专门针对您的情况,但我在发现 Lee's algorithm 很容易快速编码。它不是所有情况下最有效的,但很容易启动。这里是 one 我参加了一个竞赛。