프로그래밍 이론 : 미로 풀기

프로그래밍 이론 : 미로 풀기

---

미로를 풀 수있는 방법은 무엇입니까?
두 가지 아이디어가 있지만 그다지 우아하지 않다고 생각합니다.

기본 상황 : 우리는 행렬을 가지고 있으며,이 행렬의 요소는 미로를 나타내는 방식으로 정렬되어 있습니다.

나의 첫 번째 아이디어는 미로에서 나올 때까지 한쪽을 따라 미로를 통해 로봇을 보내는 것이 었습니다. 나는 이것이 매우 느린 해결책이라고 생각합니다.

두 번째는 1로 표시된 모든 연속 항목을 통과하여 이동할 수있는 위치 (위, 오른쪽, 아래, 왼쪽)를 확인하고 한 방향을 선택하고 경로를 계속합니다. 이것은 첫 번째 것보다 훨씬 느립니다.

물론 모든 교차점에서 두 개의 봇을 다중 스레드로 만들면 조금 더 빠르지 만, 이것이 최선의 방법은 아닙니다.

미로를 통해 봇을 보내려면 더 나은 솔루션이 필요합니다.

먼저 편집 : 좋은 답변에 감사드립니다!

제 질문의 두 번째 부분은 다차원 그래프가있는 경우 어떻게해야합니까? 그것에 대한 특별한 관행이 있습니까, 아니면 저스틴 L.의 대답도 그것을 위해 사용할 수 있습니까?
이 사건에 대한 최선의 방법은 아니라고 생각합니다.

세 번째 질문 :
이러한 미로 솔버 알고리즘 중 가장 빠른 것은 무엇입니까? (순전히 가설 적으로)

---

미로를 나무로 생각할 수 있습니다.

     ㅏ
    / \
   / \
  기원전
 / \ / \
DEFG
   / \ \
  HIJ
 / \
LM
   / \
  ** O

(대표 할 수있는)

        스타트
        + + --- + --- +
        | ACG |
    + --- + + + +
    | DB | F | J |
+ --- + --- + + --- + --- +
| LHEI |
+ --- + + --- + --- +
    | MO |
    + + --- +
    끝

(트리에서 왼쪽-오른쪽 순서 무시)

각 노드는 경로의 교차점입니다. D, I, J, L 및 O는 막 다른 골목이고 **는 목표입니다. 물론 실제 트리에서 각 노드는 최대 3 개의 자식 을 가질 수 있습니다.

이제 목표는 단순히 마무리를 찾기 위해 통과 할 노드를 찾는 것입니다. 모든 트리 검색 알고리즘이 가능합니다.

트리를 보면 트리의 가장 깊은 부분에있는 **에서 "추적"하여 올바른 솔루션을 쉽게 볼 수 있습니다.

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

미로의 특성으로 인해 너비 우선은 확인하는 평균 노드 수가 훨씬 더 많습니다. Breadth-first는 검색 할 경로의 대기열을 사용하여 쉽게 구현하고, 각 반복은 대기열에서 경로를 팝하고, 한 단계 후에 바뀔 수있는 모든 경로를 가져 와서 새로운 경로를 넣어 "폭발"합니다. 대기열 끝에. 코드에 대한 명시적인 "다음 수준"명령은 없으며 이해를 돕기위한 것입니다.

사실, 트리를 검색하는 방법에 대한 광범위한 목록이 있습니다. 방금 가장 간단하고 직접적인 두 가지 방법을 언급했습니다.

미로가 매우 길고 깊고 루프와 미친 짓이 있고 복잡하다면 Breadth-First 검색과 휴리스틱 스를 결합한 업계 표준 경로 찾기 알고리즘 인 A * 알고리즘을 제안합니다 . "지능형 폭 우선 검색"입니다.

기본적으로 다음과 같이 작동합니다.

1. 하나의 경로를 대기열에 넣으십시오 (미로로 한 걸음 만 똑바로 걸어가는 경로). 경로는 현재 길이 + 끝에서 직선 거리 (수학적 계산 가능)로 제공되는 "가중치"를 갖습니다.
2. 대기열에서 가중치가 가장 낮은 경로를 팝합니다.
3. 한 단계 후에있을 수있는 모든 경로로 경로를 "폭발"합니다. (즉, 경로가 오른쪽 왼쪽 왼쪽 오른쪽 인 경우 분해 된 경로는 RLLRR 및 RLLRL이며 벽을 통과하는 불법 경로는 포함되지 않습니다.)
4. 이 경로 중 하나에 목표가 있으면 승리! 그렇지 않으면:
5. 분해 된 경로의 가중치를 계산하고 모든 경로를 대기열에 다시 넣습니다 (원래 경로 제외).
6. 가중치를 기준으로 대기열을 가장 낮은 것부터 정렬합니다. 그런 다음 2 단계부터 반복합니다.

그리고 그것은 제가 특별히 강조한 A *입니다 . 왜냐하면 그것은 오프로드 길이나 산 등을 피하면서지도의 한 가장자리에서 다른 가장자리로 이동하는 것을 포함하여 길 찾기의 모든 애플리케이션에 대해 어느 정도 업계 표준 길 찾기 알고리즘이기 때문입니다 . 가능한 최단 거리 휴리스틱을 사용하기 때문에 매우 좋습니다. 이는 "지능"을 제공합니다. A *는 매우 다재다능합니다. 어떤 문제가 주어지면 가능한 최단 거리 휴리스틱을 사용할 수있는 경우 (우리는 간단합니다-직선) 적용 할 수 있기 때문입니다.

그러나 A *가 유일한 옵션 이 아니라는 점에 유의하는 것이 매우 중요합니다 .

사실, 트리 순회 알고리즘 의 위키피디아 카테고리 에는 97 개만 나열되어 있습니다! (최상의 정보는 이전에 링크 된 이 페이지에 있습니다.)

길이에 대해 죄송합니다 = P (나는 흔들리는 경향이 있습니다)

---

많은 미로 해결 알고리즘이 있습니다.

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

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

로봇의 경우 Tremaux의 알고리즘 이 유망 해 보입니다.

---

흥미로운 접근 방식은 적어도 나는 그것이 흥미 롭다는 것을 알았는데, 세포 자동 장치를 사용하는 것입니다. 간단히 말해서 3 개의 "벽"셀로 둘러싸인 "공간"셀은 "벽"셀로 변합니다. 마지막에 남은 공간 셀은 출구로가는 길에있는 셀뿐입니다.

Justin이 대답에 넣은 나무를 보면 리프 노드에 3 개의 벽이 있음을 알 수 있습니다. 길을 찾을 때까지 나무를 가지 치십시오.

---

매트릭스에서 그래프를 만들고 Breadth First Search, Depth First Search 또는 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

---

그냥 아이디어. 몬테카를로 패션에 봇을 던져 보는 건 어떨까요? 1 세대 봇을 gen0이라고 부르겠습니다. 다음과 같은 방식으로 연속 도로가있는 gen0의 봇만 유지합니다.-
시작부터 특정 지점
또는-특정 지점에서 끝까지

우리는 새로운 무작위 점에서 새로운 gen1의 봇을 실행 한 다음 gen1의 봇의 도로를 gen0의 도로와 연결하고 처음부터 끝까지 연속적인 도로가 있는지 확인합니다.

따라서 genn의 경우 gen0, gen1, ..., genn-1 형식의 봇과 연결하려고합니다.

물론 한 세대는 가능한 한 유한 한 시간 동안 만 지속됩니다.

I don't know if the complexion of the algorithm will prove to be practical for small data sets.
Also the algorithm assumes we know start and finish points.

some good sites for ideas:
http://citeseerx.ist.psu.edu/
http://arxiv.org/

---

I had a similar problem in one of my University Comp. Sci. courses. The solution we came up with was to follow the left hand wall (right hand wall will work just as well). Here is some pseudocode

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

That's basically it. The complex part is keeping track of which direction your facing, and figuring out which grid position is on your left based on this direction. It worked for any test case I put up against it. Interesting enough the Professors solution was something along the lines of:

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

Which will work well for most simple mazes, but fails on the a maze that looks like the following:

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

With S and E being the start and end.

With anything that doesn't follow the wall, you end up having to keep a list of the places you have been, so that you can backtrack if necessary, when you fall into a dead end, and so that you don't get caught in a loop. If you follow the wall, there's no need to keep track of where you've been. Although you won't find the most optimal path through the maze, you will always get through it.

---

If the robot can keep track of its location, so it knows if it has been to a location before, then depth-first search is the obvious algorithm. You can show by an adversarial argument that it is not possible to get better worst-case performance than depth-first search.

If you have available to you techniques that cannot be implemented by robots, then breadth-first search may perform better for many mazes, as may Dijkstra's algorithm for finding the shortest path in a graph.

---

there are many algorithms, and many different settings that specify which algorithm is best. this is just one idea about an interesting setting:

let's assume you have the following properties...

• you move a robot and you want to minimize its movement, not its CPU usage.
• that robot can either inspect only its neighbouring cells or look along corridors either seeing or not seeing cross-ways.
• it has GPS.
• it knows the coordinates of its destination.

then you can design an A.I. which...

• draws a map – every time it receives new information about the maze.
• calculates the minimal known path lengths between all unobserved positions (and itself and the destination).
• can prioritize unobserved positions for inspection based upon surrounding structures. (if it is impossible to reach the destination from there anyway...)
• can prioritize unobserved positions for inspection based upon direction and distance to destination.
• can prioritize unobserved positions for inspection based upon experience about collecting information. (how far can it see on average and how far does it have to walk?)
• can prioritize unobserved positions to find possible shortcuts. (experience: are there many loops?)

---

Same answer as all questions on stack-overflow ;)

Use vi!

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

It's truly fascinating to see a text editor solve an ascii-maze, I'm sure the emacs guys have an equivalent ..

---

This azkaban algorithm might also help you, http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

---

The best way to solve a maze is to use a connectivity algorithm such as union-find which is a quasi-linear time algorithm assuming path compression is done.

Union-Find is a data structure that tells you whether two elements in a set are transitively connected.

To use a union-find data structure to solve a maze, first the neighbor connectivity data is used to build the union-find data structure. Then the union find is compressed. To determine whether the maze is solvable the entrance and exit values are compared. If they have the same value, then they are connected and the maze is solvable. Finally, to find a solution, you start with the entrance and examine the root associated with each of its neighbors. As soon as you find a previously unvisited neighbor with the same root as the current cell, you visit that cell and repeat the process.

The main disadvantage of this approach is that it will not tell you the shortest route through the maze, if there is more than one path.

---

Not specifically for your case, but I've come across several programming contest questions where I found the Lee's algorithm quite handy to code up quickly. Its not the most efficient for all cases, but is easy to crank out. Here's one I hacked up for a contest.

참고URL : https://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze