10

これは、非機能的な方法で簡単に解決できる問題です。

しかし、Haskell でそれを解決すると、大きな問題が発生します。関数型プログラミングに関しては、私が未経験であることは確かに理由です。

問題：

同じサイズの長方形に分割された 2D フィールドがあります。シンプルなグリッド。一部の長方形は空のスペース (通過可能) ですが、他の長方形は通過できません。開始長方形Aと宛先長方形Bが与えられた場合、2 つの間の最短経路をどのように計算しますか? 移動は垂直方向と水平方向にのみ可能で、ステップは 1 つの長方形を大きくします。

Haskellでこれを達成するにはどうすればよいですか? コード スニペットは確かに歓迎されますが、必須ではありません。また、その他のリソースへのリンクも大歓迎です。

ありがとう！

4

2 に答える 2

12

グリッドをリストのリストとして表します。タイプは[[Bool]]。そして、グリッド要素がいっぱいかどうかを知るための関数を定義します。

type Grid = [[Bool]]
isFullAt :: Grid -> (Int, Int) -> Bool  -- returns True for anything off-grid

次に、ネイバーを見つける関数を定義します。

neighbors :: (Int, Int) -> [(Int, Int)]

完全でないネイバーを見つけるには、でpointフィルタリングできますfilter (not . isFullAt) $ neighbors point。

この時点で、2つのデータ構造を定義します。

  • 各ポイントをにマップしますMaybe Cost
  • 既知のコストのすべてのポイントをヒープに格納します

コストゼロで、ヒープ内の開始正方形Aのみで初期化します。

次に、次のようにループします。

  • ヒープから最小コストの正方形を削除します。
  • まだ有限マップにない場合は、それとそのコストcを追加し、完全でないすべてのネイバーをコスト付きのヒープに追加しますc+1。

ヒープが空の場合、到達可能なすべてのポイントのコストが発生し、有限マップでBを検索できます。（このアルゴリズムは「ダイクストラのアルゴリズム」と呼ばれることがあります。忘れてしまいました。）

で有限マップを見つけることができますData.Map。広大なライブラリのどこかにヒープ（優先キュー）があると思いますが、どこにあるのかわかりません。

これで始められるといいのですが。

于 2010-03-16T01:02:45.133 に答える
3

さて、あなたのタイプはあなたのアルゴリズムを決定します。

グリッドを表すためにどのデータ型を使用しますか？二次元配列？リストのリスト？木？グラフ？

有向グラフで最短経路が必要な場合は、FGL（機能グラフパッケージ）の何かを使用するのが最適です。

于 2010-03-15T23:25:58.363 に答える