2


0

Schemeのベストファーストサーチアルゴリズム

さて、これは宿題の質問です、そして、私はどうやって始めようとしているかについての手がかりを持っていません。 いくつかの助けとヒントは大いに感謝されるでしょう。

迷路タイプの問題を解決するためにヒューリスティック関数を使用する必要があります。

5x5のグリッドがあり、ロボットの位置が(1,5)で、ロボットを(5,1)に移動することが目標です。 障害物はほとんどなく、「(X、1,3)」、「(X、2,3)」、「(X、5,3)」、「(X、4,2)」と言ってください。

ロボットが通過した経路を印刷します。

私は目標へのロボットの道を見つけるためにhttp://en.wikipedia.org/wiki/Best-first_search[greedy最良の最初の検索アルゴリズム]を使うことを考えています

私の問題は、私がschemeに慣れていないのは、このようなちょっとした問題を解決することから始める方法がわからないことです。

するべきか ?

(define grid l w) --define the length and width of the grid ?

(define robot) --define the initial position

(define goal) --define the goal position

(define blocks) --define the obstacle blocks

and create a main function (define bestfirstslove)

この問題を解決するために ?

グリッドを作成する方法 どうやってこの問題に取り組むべきですか? ロボットが移動する歩数を印刷するにはどうすればよいですか?

助けていただければ幸いです:)

2 回答


3


わかりました、それであなたが最初にすることはあなたのサーチスペースを*離散化*することです。 あなたの5x5グリッドの例を使用すると、これはあなたがあなたのロボットが占めることができる合計25ポイントを持っていることを意味します。

次に、検索アルゴリズムを選択します。 あなたはGreedy Best First Search(GBFS)を選んだので、それを始めましょう、しかし実際の状況ではあなたはあなたの問題の要求に従ってそれを選ぶべきです。

GBFSは単純なアルゴリズムであり、次のものが必要です(そして、パス検出アルゴリズムにはこれらのモジュールのほとんどが必要になります)。

  1. * _任意のノードのすべての隣接ノードを一覧表示する機能。 グリッド内 上記で指定したように、隣人は自明に決定されます(境界チェックを使用して両方向に+ 1、-1の並べ替えを行い、もちろん_それが障害物である_をチェックします)。

  2. * 「Open」ノードを追跡するデータ構造 :「Open」ノードは まだ調査されていないノード。 そのため、ウィキペディアのコード例では、最初の位置から開始し、(上記の関数を使用して)その後継者を見つけ、*ヒューリスティック*に基づいています(ヒューリスティックとして、目標と後継者間のユークリッド距離またはマンハッタン距離を使用できます)あなたはそれを `Open`リストに追加します - これは priority queue *としてより良く実装されています。

  3. * あなたのメイン関数 *:これは基本的に最初の `(1,5)`を配置し、その近傍を見つけて、ユークリッド距離に基づいて優先度キューに追加します。 その後再帰的に あなたがあなたのゴールを見つけるまで、あなたがそのリストの最初のポジションでしたのと同じことをしなさい。

したがって、Greedy Best Firstについて注意する必要があるのは、最適なパスがない可能性がありますが、終了とパス(存在する場合)が保証されているということです。 あなたはA *やBreadth FirstやDepth Firstのような他のアルゴリズムについて考えて、あなたの要求に対して何がうまくいくかを見るべきです。


0


おそらく関連しています: C#:A-Starが生まれた CodeProject