1

http://ideone.com/QXyVzR

上記のリンクには、BFS アルゴリズムを使用して迷路を解くために作成したプログラムが含まれています。迷路は 2D 配列として表され、最初は数値として渡されます (0 は訪問可能な空のブロックを表し、その他の数値は「壁」ブロックを表します)、定義したレコード タイプに変換されます。さまざまなデータの追跡:

type mazeBlock = {
    walkable   : bool;
    isFinish   : bool;
    visited    : bool;
    prevCoordinate : int * int
}

出力は、最初から最後まで迷路を通る最短経路をたどる順序付けられたペア (座標/インデックス) のリストであり、その両方の座標がパラメーターとして渡されます。

分岐係数が低い小さな迷路では問題なく動作しますが、大きな迷路 (たとえば 16 x 16 以上)、特に壁のない (分岐係数が高い) 迷路でテストすると、多くの時間とメモリが必要になります。これがアルゴリズムに固有のものなのか、実装方法に関連しているのか疑問に思っています。そこにいる OCaml ハッカーは私に専門知識を提供してくれますか?

また、私は OCaml の経験がほとんどないため、コードをスタイル的に改善する方法についてアドバイスをいただければ幸いです。ありがとう！

編集：

http://ideone.com/W0leMv

これは、クリーンアップされ、編集されたプログラムのバージョンです。いくつかの文体の問題を修正しましたが、セマンティクスは変更していません。いつものように、2 番目のテストはまだ大量のリソースを消費しており、まったく終了していないように見えます。この問題についてまだ助けを求めています...

EDIT2：

解決しました。両方の回答者に感謝します。最終的なコードは次のとおりです。

http://ideone.com/3qAWnx

4

2 に答える 2

2

クリティカル セクション、つまり ではmazeSolverLoop、以前にアクセスしたことのない要素のみをアクセスする必要があります。キューから要素を取得するときは、まずその要素がアクセスされているかどうかを確認し、その場合は何もせずに次の要素を取得するために再帰する必要があります。これこそが、アルゴリズムの時間の複雑さを適切なものにしている理由です (ある場所を 2 回訪れることはありません)。

そうでなければ、あなたの OCaml スタイルは改善される可能性があります。いくつかのコメント:

  • OCaml ランドでの規則は、むしろ toではなく towrite_like_thisですwriteLikeThis。それに従うことをお勧めしますが、それは好みの問題であり、客観的な基準ではありません.

  • 更新された可変構造である場合、データ構造を返す意味はありません。(grid, pair)キューが入力とまったく同じなのに、なぜ常にキューを返すようにするのですか? これらの関数を返しunitて、よりシンプルで読みやすいコードにすることができます。

  • ペアによって許可される抽象化レベルは良好であり、それを維持する必要があります。あなたは現在していません。などと書いても意味がありませんlet (foo, bar) = dimension grid in if in_bounds pos (foo, bar)。dimの代わりに寸法に名前を付けるだけ(foo, bar)です。別々に必要でない場合、2 つのコンポーネントに分割しても意味がありません。隣人については、今のところ配列アクセスにneighborXandneighborYを使用していることに注意してください。ただし、これはスタイルの間違いです。ペアを入力として取り、配列内の値を取得および設定するための補助関数が必要です。メイン関数でペアを破棄します。単一の関数内のすべてのコードを同じレベルの抽象化に保つようにしてください。すべてが別々の座標で動作するか、すべてがペアで動作します (常に構築/分解されるのではなく、そのように名前が付けられます)。

于 2013-05-31T17:43:26.970 に答える
0

私があなたを正しく理解していれば、壁のない N x N グリッドの場合、N^2 ノードとおよそ 4*N^2 エッジを持つグラフがあります。これらは、N = 16 の大きな数のようには見えません。

唯一の秘訣は、訪問したノードを適切に追跡することだと思います。私はあなたのコードをざっと見ましたが、あなたがやっている方法に明らかに間違っているものは何もありません。

これは良い OCaml イディオムです。あなたのコードは言う：

let isFinish1 = mazeGrid.(currentX).(currentY).isFinish in
let prevCoordinate1 = mazeGrid.(currentX).(currentY).prevCoordinate in
mazeGrid.(currentX).(currentY) <-
    { walkable = true;
     isFinish = isFinish1;
     visited = true;
     prevCoordinate = prevCoordinate1}

これは、次のようにもう少し経済的に言えます。

mazeGrid.(currentX).(currentY) <-
    { mazeGrid.(currentX).(currentY) with visited = true }
于 2013-05-31T17:39:03.900 に答える