2

さて、これは宿題の質問です。どのように始めればよいかわかりません。いくつかのヘルプとヒントをいただければ幸いです。

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

5x5 のグリッドがあり、ロボットが (1,5) の位置にあり、ロボットを (5,1) に移動することが目標であるとします。道に沿っていくつかの障害があり(X,1,3)ます(X,2,3)(X,5,3)(X,4,2)

ロボットが通過したルートを印刷します。

貪欲な最良の最初の検索アルゴリズムを使用して、ロボットがゴールまでの経路を見つけることを考えています

私の問題は、私はスキームに慣れていないため、このような問題の解決をどのように開始すればよいかわかりません。

するべきか ?

(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)

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

グリッドを作成するにはどうすればよいですか? この問題にどのようにアプローチすればよいですか? ロボットが移動するステップを印刷するにはどうすればよいですか?

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

4

2 に答える 2

3

さて、あなたが最初にすることはあなたの検索空間を離散化することです。5x5グリッドの例を使用すると、これは、ロボットが占有できる合計25ポイントがあることを意味します。

次に、検索アルゴリズムを選択します。貪欲な最良優先探索(GBFS)を選択したので、それを使用しましょう。ただし、実際の状況では、問題の要件に従って選択する必要があります。

GBFSは単純なアルゴリズムであり、次のものが必要です(パスファインディングアルゴリズムには、これらのモジュールのほとんどが必要です)。

  1. 任意のノードのすべてのネイバーを一覧表示する関数。たとえば、上記で指定したグリッドでは、近傍は自明に決定されます(境界チェックを使用して、両方向に+ 1、-1の順列を設定し、もちろん、それが障害物であるかどうかをチェックします)。

  2. Openノードを追跡するためのデータ構造Openノードはまだ調査されていないノードです。したがって、ウィキペディアのサンプルコードでは、初期位置から開始し、後継者を見つけ(上記の関数を使用)、ヒューリスティック(ゴールと後継者の間のユークリッドまたはマンハッタン距離をヒューリスティックとして使用できます)に基づいて追加しますそれをOpen「リスト」に追加します。これは、優先キューとしてより適切に実装されます。

  3. あなたの主な機能:これは基本的に初期位置から始まり、(1,5)その隣人を見つけて、ゴールまでのユークリッド距離に基づいて優先キューに追加します。次に、目標が見つかるまで、そのリストで繰り返します(つまり、最初の位置で行ったのと同じことを行います)。

したがって、Greedy Best Firstについて注意する必要があるのは、最適なパスがない可能性があることですが、終了とパス(存在する場合)は保証されています。A *、幅優先、深さ優先などの他のアルゴリズムについて考え、要件に合ったものを確認する必要があります。

于 2009-10-16T01:56:18.153 に答える
0

おそらく関連: C#: CodeProject でA-Star が誕生

于 2009-10-16T00:57:20.597 に答える