1

ブロックパズルを解くためのアルゴリズムを作りたいのですが、できるだけ効率的です。私はすでに簡単な方法(後戻り)をしました。

私はすべてをマトリックスとして表現しました. ピースが収まる必要がある大きなマトリックスは最初はすべて0で、ピースはスペースがいっぱいの場合は1、スペースが空の場合は0のマトリックスです. 次に考えられるより効率的なアイデアは、次の行に進む前に行が完了しているかどうかを常に確認することです。私が言いたいのは、 (十字架)として表現されたピースがあるかもしれないということです。クロスが隅に置かれている場合、プログラムは無効なソリューションに対してバックトラック全体を無用に実行するため、戻って別のピースを試す必要があります。
0 1 0
1 1 1
0 1 0

必要に応じてコードの一部を提供できますが、先ほど述べたように、単純で非効率的なバックトラッキングのみを行いました。
誰かがより良いアイデアを持っていますか? この場合、動的計画法を使用できますか?

4

1 に答える 1

2

問題をグラフと考えてください。ノードはブロックを配置できるさまざまな状態であり、エッジはあるノードから別のノードへの可能な移動です。その場合、解は現在の位置からターゲットまでの最短距離であり、ダイクストラのアルゴリズムを使用して計算できます。

于 2013-02-22T21:31:14.360 に答える