13

この質問を CodeReviewに投稿しましたが、Haskell に関する質問ではなく、アルゴリズムに関する質問であることに気付きました。

Haskell コードは私の github リポジトリにありますが、コードは一般的な概念ほど重要ではないと思います。

基本的に、プログラムは Kalaha (スウェーデンのバリエーション) のゲームで最適な最初の一連の動きを見つけ出します。最初の「ターン」のみが考慮されるため、あなたが開始し、対戦相手が移動する時点から何も計算されないと仮定します。

カラハボード http://www.graf-web.at/mwm/kalaha.jpg

ボードは、空の店舗と各ポットに同量のビー玉から始まります。

自分の側にある空でないポットを選択してターンを開始し、そのポットからビー玉をすべて拾い上げ、ポットを通過するときにビー玉を 1 つ落としてボードの周りを移動します。最後のビー玉が店に着地すると、次のターンになります。空でもストアでもないポットに着地した場合、そのポットの内容をすべて拾い上げて続行します。最後に、空のポットに着地すると、ターンは対戦相手に渡されます。

これまでのところ、考えられるすべてのパスを選択し、最終的に店舗内のビー玉の量に従ってそれらを並べ替えることで、これを解決しました。パスとは、ポットの 1 つから開始し、必要なすべてのピックアップと移動を行い、店に着陸するか空のポットに着陸するかを確認することを意味します。店に到着すると、続行できます。今では、あなたの側に空ではないポットと同じ数の新しいブランチがあります.

問題は、ポットにビー玉が 5 つある状態で開始すると、すでにかなりの数のパスになっているという事実にあります。6 つまでジャンプすると、ghci はメモリ不足になります。

これを安くする方法がわからないのは、計算時に各パスが必要だと思うからです。生成された数千 (または数百万) のパスのうち、多くても 3 つのパス (最良のもの) しか必要ありませんが、残りのパスは、以前のものよりも実際に優れているかどうかを確認するために実行する必要があります。
1 つが長い場合 (一般的には優れています)、それは良いことですが、コストがかかります。それが以前のどのパスよりも短い場合でも、プログラムはそれを見つけるためにそのパスを計算する必要がありました。

これを回避する方法はありますか、それとも定義上必要なすべてのパスを計算していますか?

4

2 に答える 2

2

この並列バージョンのマップを使用して並列化を試すことができます。

parMap :: (a -> b) -> [a] -> Eval [b]
parMap f xs = map f xs `using` parList rseq

次に、ブランチの選択肢ごとに新しいスレッドを開始します。

asを再帰として使用するparMap pathFunction kalahaPotsと、多くのスレッドが発生しますが、高速になる可能性があります。チャンクすることもできますが、私は並列ハスケラーがあまり得意ではありません。

于 2012-07-13T14:42:48.163 に答える
2

一連の動きを順番に 1 から 6 の数字 (ビー玉を拾うポットを表す) として記録し、そのたびに一連のシーケンス全体を最初から再生します。3 つの勝者と最後の一連の動きだけを保持して更新することで、次に何を試すかがわかります。次の法的な動きがない場合は、1 ノッチ戻ります。

おそらく法外に遅くなるでしょうが、使用するメモリはほとんどありません。結果のポジションを保存せず、選択したポットの数のみを保存し、開始ポジションから毎回新たにシーケンスを再生し、最後の移動を変更します (2 の代わりに、次は 3、4 などを試します; 正当な移動がそれ以上ない場合、1 レベル後戻りします)。または、バックトラックを容易にするために、試行された最後の一連の動きの位置を保存することもできます。

スピードトレードオフの典型的なスペースです。

于 2012-07-12T20:15:20.090 に答える