74

迷路を解決するための可能な方法は何ですか？
私は2つのアイデアを持っていますが、それらはあまりエレガントではないと思います。

基本的な状況：マトリックスがあり、このマトリックスの要素は、迷路を表すように順序付けられており、1つの方法で1つの方法で、1つの方法で順序付けられています。

私の最初のアイデアは、迷路の外に出るまで、ロボットを迷路の片側に沿って送ることでした。これは非常に遅い解決策だと思います。

2つ目は、1でマークされたすべての連続するアイテムを通過し、どこに移動できるか（上、右、下、左）をチェックして、1つの方法を選択し、そこにパスを続行します。これは最初のものよりもさらに遅いです。

もちろん、すべてのジャンクションで2つのボットをマルチスレッド化すると少し速くなりますが、それも最善の方法ではありません。

迷路を介してボットを送信するには、より良いソリューションが必要です。

最初に編集
：いい答えをありがとう！

私の質問の2番目の部分は、多次元グラフがある場合にどうするかということです。そのための特別な慣行はありますか、それともジャスティンL.の答えはそのためにも使用できますか？
この場合、それは最善の方法ではないと思います。

3番目の質問：
これらの迷路ソルバーアルゴリズムのどれが最速ですか？（純粋に仮説的に）

4

14 に答える 14

168

あなたはあなたの迷路を木と考えることができます。

     A
    / \
   / \
  紀元前
 / \ / \
DEFG
   / \ \
  HIJ
 / \
LM
   / \
  ** O

（おそらく表すことができます）

        始める
        + + --- + --- +
        | ACG |
    + --- + + + +
    | DB | F | J |
+ --- + --- + + --- + --- +
| LHEI |
+ --- + + --- + --- +
    | MO |
    + + --- +
    終了

（ツリーの左右の順序を無視します）

各ノードはパスのジャンクションです。D、I、J、L、Oは行き止まりで、**が目標です。もちろん、実際のツリーでは、各ノードに最大3つの子が存在する可能性があります。

あなたの目標は、フィニッシュを見つけるためにトラバースするノードを見つけることです。どんな古いツリー検索アルゴリズムでもかまいません。

ツリーを見ると、ツリーの最深部にある**から「トレースアップ」するだけで、正しい解決策を簡単に見つけることができます。

A B E H M **

迷路に「ループ」がある場合、このアプローチは少しだけ複雑になることに注意してください（つまり、可能であれば、バックトレースせずに、すでに通過したパッセージに再度入ります）。コメントを確認して、1つの優れた解決策を見つけてください。

それでは、このツリーに適用された、最初に言及したソリューションを見てみましょう。

最初の解決策は基本的に深さ優先探索ですが、これはそれほど悪くはありません。これは実際にはかなり良い再帰検索です。基本的には、「常に一番右のアプローチを最初に取ってください。そこに何もない場合は、最初の場所まで直進または左に戻ってから、繰り返してください。

深さ優先探索では、上記のツリーが次の順序で検索されます。

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

**を見つけたらすぐに停止できることに注意してください。

ただし、実際に深さ優先探索をコーディングする場合は、再帰的プログラミングを使用するとすべてがはるかに簡単になります。反復法でも機能し、バックトラックの方法を明示的にプログラムする必要はありません。実装については、リンクされた記事を確認してください。

樹木を検索するもう1つの方法は、幅優先探索ソリューションです。これは、樹木を深さで検索します。上記のツリーを次の順序で検索します。

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

迷路の性質上、幅優先ではチェックするノードの平均数がはるかに多いことに注意してください。幅優先は、検索するパスのキューを用意し、各反復でパスをキューからポップし、1つのステップの後に変換できるすべてのパスを取得して「展開」し、それらの新しいパスを配置することで、簡単に実装できます。キューの最後に。コーディングするための明示的な「次のレベル」のコマンドはなく、理解を助けるためにそこにありました。

実際、ツリーを検索する方法の完全なリストがあります。最も単純で最も簡単な2つの方法について説明しました。

迷路が非常に長く、深く、ループやクレイジーがあり、複雑な場合は、幅優先探索とヒューリスティックを組み合わせた業界標準のパスファインディングアルゴリズムであるA*アルゴリズムをお勧めします... 「インテリジェントな幅優先探索」。

基本的には次のように機能します。

  1. 1つのパスをキューに入れます（迷路の中に1歩だけまっすぐ歩くパス）。パスには、現在の長さ+端からの直線距離（数学的に計算できます）によって与えられる「重み」があります。
  2. キューから重みが最も小さいパスをポップします。
  3. パスを1つのステップの後にある可能性のあるすべてのパスに「分解」します。（つまり、パスが右左左右の場合、分解されたパスはRLLRRとRLLRLであり、壁を通過する違法なパスは含まれません）
  4. これらのパスの1つに目標がある場合は、Victory！さもないと：
  5. 展開されたパスの重みを計算し、それらすべてをキューに戻します（元のパスを除く）
  6. キューを重みで並べ替えます。一番小さいものから順に並べ替えます。次に、ステップ2から繰り返します。

これはA*です。これは、オフロードのパスや山などを避けながら、マップの一方の端からもう一方の端に移動するなど、パスファインディングのすべてのアプリケーションで業界標準のパスファインディングアルゴリズムであるため、特に強調表示されています。可能な限り最短の距離ヒューリスティックを使用しているため、非常に優れています。これにより、「インテリジェンス」が得られます。A *は非常に用途が広いので、問題があれば、可能な限り最短の距離ヒューリスティックが利用できる場合（私たちの方法は簡単です-直線）、それを適用できます。

しかし、A*が唯一の選択肢ではないことに注意することは非常に価値があります。

実際、ツリートラバーサルアルゴリズムのウィキペディアカテゴリには、 97個だけがリストされています。（最高のものは、以前にリンクされたこのページにまだあります）

長さ=Pでごめんなさい（私は歩き回る傾向があります）

于 2010-06-22T22:40:32.090 に答える
14

多くの迷路解決アルゴリズムが存在します：

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

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

ロボットにとって、Tremauxのアルゴリズムは有望に見えます。

于 2010-06-22T22:21:55.910 に答える
12

興味深いアプローチは、少なくとも私が面白いと思ったのは、セルオートマトンを使用することです。要するに、3つの「壁」セルに囲まれた「スペース」セルは「壁」セルに変わります。最後に残っているスペースセルは、出口に向かう途中のスペースセルだけです。

ジャスティンが答えた木を見ると、葉のノードに3つの壁があることがわかります。パスができるまで木を剪定します。

于 2010-06-22T23:22:16.560 に答える
5

これは私のお気に入りのアルゴリズムの1つです。

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
于 2010-06-22T22:47:21.247 に答える
4

マトリックスからグラフを作成し、幅優先探索、深さ優先探索、またはダイクストラアルゴリズムを使用してみませんか？

于 2010-06-22T22:21:55.903 に答える
3

大学のコンプの1つでも同様の問題が発生しました。科学 コース。私たちが思いついた解決策は、左側の壁をたどることでした（右側の壁も同様に機能します）。ここにいくつかの擬似コードがあります

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が開始と終了です。

壁に従わないものがあると、行き止まりに陥ったときに必要に応じてバックトラックできるように、また捕まらないように、行ったことのある場所のリストを保持する必要があります。ループで。壁をたどれば、どこに行ったかを追跡する必要はありません。迷路を通る最適な道を見つけることはできませんが、常にそれを通り抜けることができます。

于 2010-06-23T01:26:46.273 に答える
3

これは、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
于 2014-09-18T00:26:09.120 に答える
2

ロボットがその位置を追跡できる場合、ロボットが以前にその位置に行ったことがあるかどうかを知ることができる場合、深さ優先探索が明白なアルゴリズムです。敵対的な議論によって、深さ優先探索よりも優れた最悪の場合のパフォーマンスを得ることができないことを示すことができます。

ロボットでは実装できない手法を利用できる場合は、グラフ内の最短経路を見つけるためのダイクストラのアルゴリズムと同様に、幅優先探索の方が多くの迷路で優れたパフォーマンスを発揮する可能性があります。

于 2010-06-23T01:56:19.317 に答える
2

ただのアイデア。モンテカルロ方式でボットをそこに投げてみませんか。第一世代のボットをgen0と呼びましょう。このように、いくつかの連続した道路を持つgen0からのボットのみを保持します：
-開始からあるポイントまで
、または-あるポイントから最後まで

新しいランダムドットでボットの新しいgen1を実行し、次にgen1のボットの道路をgen0の道路に接続して、最初から最後まで連続した道路が得られるかどうかを確認します。

したがって、gennの場合、gen0、gen1、...、genn-1のボットと接続しようとします。

もちろん、世代は実行可能な最終的な時間だけ持続します。

アルゴリズムの複雑さが小さなデータセットに実用的であることが証明されるかどうかはわかりません。
また、アルゴリズムは、開始点と終了点がわかっていることを前提としています。


アイデアのためのいくつかの良いサイト：http：
//citeseerx.ist.psu.edu/
http://arxiv.org/

于 2010-06-23T00:05:05.657 に答える
1

スタックオーバーフローに関するすべての質問と同じ答え;）

viを使用してください！

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

テキストエディタがASCII迷路を解決するのを見るのは本当に魅力的です、私はemacsの人が同等のものを持っていると確信しています..

于 2010-06-23T06:08:16.977 に答える
1

多くのアルゴリズムがあり、どのアルゴリズムが最適かを指定するさまざまな設定があります。これは、興味深い設定に関する1つのアイデアにすぎません。

次のプロパティがあると仮定しましょう...

  • ロボットを動かし、 CPU使用率ではなく、その動きを最小限に抑えたいとします。
  • そのロボットは、隣接するセルのみを検査するか、交差点が見えるか見えないかのどちらかで廊下に沿って見ることができます。
  • GPSがあります。
  • それはその目的地の座標を知っています。

次に、AIを設計できます...

  • マップを描画します–迷路に関する新しい情報を受け取るたびに。
  • 観測されていないすべての位置（およびそれ自体と宛先）間の最小の既知のパス長を計算します。
  • 周囲の構造に基づいて、検査のために観察されていない位置に優先順位を付けることができます。（とにかくそこから目的地に到達することが不可能な場合...）
  • 目的地までの方向と距離に基づいて、検査のために観察されていない位置に優先順位を付けることができます。
  • 情報収集の経験に基づいて、検査のために観察されていない位置に優先順位を付けることができます。（平均してどこまで見ることができ、どこまで歩く必要がありますか？）
  • 観察されていない位置に優先順位を付けて、可能なショートカットを見つけることができます。（経験：ループはたくさんありますか？）
于 2013-12-03T19:14:37.803 に答える
0

このアズカバンアルゴリズムも役立つかもしれません、 http：//journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

于 2011-10-07T09:59:20.970 に答える
0

迷路を解決する最良の方法は、パス圧縮が行われることを前提とした準線形時間アルゴリズムであるunion-findなどの接続アルゴリズムを使用することです。

Union-Findは、セット内の2つの要素が推移的に接続されているかどうかを示すデータ構造です。

ユニオンファインドデータ構造を使用して迷路を解決するには、最初にネイバー接続データを使用してユニオンファインドデータ構造を構築します。次に、ユニオン検索が圧縮されます。迷路が解けるかどうかを判断するために、入口と出口の値が比較されます。それらが同じ値である場合、それらは接続されており、迷路は解決可能です。最後に、解決策を見つけるために、入り口から始めて、その隣人のそれぞれに関連付けられているルートを調べます。現在のセルと同じルートを持つ以前にアクセスしていないネイバーを見つけるとすぐに、そのセルにアクセスしてプロセスを繰り返します。

このアプローチの主な欠点は、複数のパスがある場合、迷路を通る最短ルートが表示されないことです。

于 2016-07-07T22:36:30.113 に答える
0

特にあなたの場合ではありませんが、プログラミングコンテストの質問に出くわしました。そこでは、Leeのアルゴリズムをすばやくコーディングするのに非常に便利であることがわかりました。すべての場合に最も効率的というわけではありませんが、簡単に実行できます。これが私がコンテストのためにハックしたものです。

于 2016-07-15T18:52:57.957 に答える