6

現在、15 パズル ソルバー (C++) を作成していますが、15 パズルだけでなく、3x4 パズル、8x8 パズルなども解く必要があります... - > X x Y パズル。訪れた州に関する情報をどうにかして保持する必要があります。私の最初のアイデアは、たとえばツリーを作成することでした:
パズル:

状態 1
1 2
3 0

状態 2
1 3
0 2

私は私のツリーに保管します：

root->1->2->3->0
            \_
                \->3->0->2

これは、すべてのパズルの 5x3、6x6 などのパズルでも機能します。

このアイデアは機能しますが、多くのメモリを浪費し、ノードを追加するには時間がかかります:/ したがって、非常に非効率的です。

次のアイデアは、訪問した状態を stl の std::map< > に保持することでしたが、パズル状態からショートカットを作成するための適切なハッシュ関数を作成する方法がわかりません (パズル状態を保存する必要がないため、必要なのはstd::map への鍵、または訪問された状態に関する情報を保持するための他のアイデアについて、何か考えはありますか?

4

3 に答える 3

2

X, Y <= 16 である X*Y のパズルを解くことのみに関心があるとします。パズルの状態は、X*Y バイトの配列で表し、各バイトはパズルの正方形の値を示します。 . 奇妙なベースで BigInteger の代わりにバイトを使用すると、アクセスと変更の時間が短縮される可能性があります。これは、ビット演算が遅くなる傾向があり、メモリと速度のトレードオフの点で全体的なアプローチとして適切ではない可能性があるためです。

template<unsigned X, unsigned Y>
class PuzzleState {
    unsigned char state[X*Y];
    public:
    void set(unsigned x, unsigned y, unsigned char v) {
        state[x+X*y] = v;
    }
    unsigned get(unsigned x, unsigned y) {
        return state[x+X*y];
    }
    bool operator<(const PuzzleState<X, Y>& other) const {
        return memcmp(state, other.state, X*Y) < 0;
    }
};

そして、メソッドとメソッドで astd::set<PuzzleState<8,8 >を使用するだけです。パフォーマンスがまだ適切でないかどうかをテストした後、ローリング ハッシュなどの単純なハッシュ関数を使用して、代わりにハッシュテーブルをスローできます。insertfindstd::set

于 2011-04-14T12:17:34.807 に答える
1

Zobrist ハッシングは、抽象的なゲームをプレイするプログラムではかなり一般的です。

于 2011-04-14T14:12:04.943 に答える
1

単一の状態を BigInteger 数値として表します (C++ の実装はこちらで入手できます。独自の実装を希望する場合は、そのスレッドもここにあります)。

(X,Y) 次元のパズルがあると仮定すると、基数 = X*Y を使用して数値を作成します。この数値の数字は、パズルのピースを 1 次元に平面化したものを表します。

例えば：

State 1
1 2
3 0

これはフラット化されます

1 2 3 0

次に、次のような基数 4 の数値に変換します。

state = (1 * (4^3)) + (2 * (4^2)) + (3 * 4) + 0;

これにより、任意のパズルの任意の状態が一意に識別されます。

于 2011-04-14T10:13:02.330 に答える