5

私のC++vec割り当てでは、基本的に、左側の2番目の上の文字から始まるテキストファイル（ベクターにストリーミングされる）内のテキストのチャンクを検索しようとしています。それはテキスト迷路のためのものであり、私のプログラムは最終的にそれを通るパスの文字を印刷することになっています。

迷路の例は次のようになります。

###############
Sbcde####efebyj
####hijk#m#####
#######lmi#####
###############
###############
###############
###############
###############
###############
###############
###############
###############
###############
###############

ここで、「＃」は歩けない壁であり、常に左側の2番目の上の文字から開始します。アルファベット文字は歩きやすい正方形を表します。出口は常に右側にあります。迷路は、maze.textファイルでは常に15x15サイズです。アルファベットの文字は同じ迷路の中で繰り返されますが、互いに直接並んでいるわけではありません。

私がここでやろうとしているのは、現在の正方形の隣の正方形にアルファベット文字がある場合、それをベクトルに追加しvec、迷路の終わりに到達するまでこのプロセスを繰り返します。最終的には、いくつかの迷路に存在する複数のパスを画面に印刷することで、これをより複雑にすることになっています。

これまでのところ、アルゴリズム自体にこれがありますが、これは間違っていることがわかっています。

    void pathcheck()
{
    if (isalpha(vec.at(x)) && !(find(visited.begin(), visited.end(), (vec.at(x))) != visited.end()) )
    {
        path.push_back(vec.at(x));
        visited.push_back(vec.at(x));
        pathcheck(vec.at(x++));
        pathcheck(vec.at(x--));
        pathcheck(vec.at(x + 16));
        pathcheck(vec.at(x - 16));
    }
}

visited訪問した正方形を追跡する私のベクトルです。

これを更新して実際に機能させ、最終的に複数のパスを管理できるようにするにはどうすればよいですか（つまり、パスが2つある場合、プログラムは両方のパスを画面に出力します）。すでにアクセス/チェックした正方形を追跡する別のベクトル/配列が必要になる可能性があると言われたことを思い出しますが、それをここで正確に実装するにはどうすればよいですか？

4

1 に答える 1

3

あなたは正しい方向に進んでいます。迷路に関しては、一般的な解決方法は、深さ優先探索（パスを見つけるための最も効率的なソリューション）または幅優先探索（効率は劣りますが、最適なパスを見つけることが保証されています）のいずれかを使用します。あなたは徹底的な検索をしたいと思うように思われるので、これらの選択は基本的に交換可能です。私はあなたがそれらを読むことをお勧めします：

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

基本的に、迷路を解析してグラフとして表す必要があります（ここで、「＃」以外の各ノードはノードであり、各リンクはウォーク可能なパスです）。次に、部分パスのリストを保持します（つまり、ノードのリストを、ノードにアクセスした順序で保持します。たとえば、[S、b、c]はSから始まりcで終わる部分パスです）。DFSとBFSの主な考え方は、部分パスのリストを用意し、リストから項目を1つずつ削除し、その部分パスから続くすべての可能な部分パスを生成してから、それらをリストに配置して繰り返すことです。DFSとBFSの主な違いは、DFSがこのリストをスタックとして実装し（つまり、新しいアイテムの優先度が最も高く）、BFSがキューを使用する（つまり、新しいアイテムの優先度が最も低い）ことです。

したがって、DFSを使用する迷路の場合、次のように機能します。

  1. 初期ノードはSなので、初期パスは[S]です。[S]をスタックに押し込みます（[[S]]）。
  2. 最初のアイテム（この場合は[S]）をポップします。
  3. 現在のノードから1回の移動で到達できるすべての可能なノードのリストを作成します（この場合はbのみ）。
  4. 手順3のノードごとに、現在の部分パスの一部であるノードをすべて削除します。これにより、ループが防止されます。（つまり、部分パス[S、b]の場合、bからcおよびSに移動できますが、Sはすでに部分パスの一部であるため、戻ることは無意味です）
  5. 手順4のノードの1つが目標ノードである場合は、それを部分パスに追加して、完成したパスを作成します。パスを印刷します。
  6. 目標ノードではないステップ4のノードごとに、新しい部分パスを生成してスタックにプッシュします（つまり、[S]の場合、[S、b]を生成してスタックにプッシュします。これで、次のようになります。 [[S、b]]）
  7. スタックが空になるまで、つまり開始ノードから可能なすべてのパスを通過するまで、手順2〜6を繰り返します。

注：この例では、重複する文字があります（たとえば、3つの「e」）。あなたの場合、文字を保持する変数を含む単純な「Node」クラスを作成するかもしれません。そうすれば、各「e」は独自のインスタンスを持ち、ポインターは異なる値になり、簡単に区別できるようになります。私はC++を正確には知りませんが、擬似コードでは次のようになります。

class Node:
    method Constructor(label):
        myLabel = label
        links = list()

    method addLink(node):
        links.add(node)

ファイル内のすべての文字を読み取ることができ、それが「＃」でない場合は、その文字のノードの新しいインスタンスを作成し、隣接するすべてのノードを追加します。

編集：私は過去3年間Python開発者として過ごしましたが、少し甘やかされてきました。次のコードを見てください。

s = "foo"
s == "foo"

Pythonでは、その主張は真実です。Pythonの"=="は、文字列の内容を比較します。Java開発者としての日々から忘れていたのは、多くの言語で「==」が文字列のポインタを比較することです。そのため、JavaやC ++などの多くの言語では、文字列がメモリのさまざまな部分を指しているため、アサーションはfalseになります。

私のポイントは、このアサーションが正しくないため、Nodeクラスを作成するのをやめて、文字を比較するだけでよいということです（==を使用し、strcmp（）を使用しないでください！）が、このコードは読むのが少し混乱する可能性があり、文書化する必要があります。

全体として、実装が非常に簡単で、コードが読みやすく、迷路を1回解析するだけでよいという理由だけで、ある種のNodeクラスを使用します。

幸運を

于 2012-05-26T03:10:20.047 に答える