1

Javaで以下の問題をプログラミングする際に問題があります。これは制約充足の問題です:

次のような制約がある場合:

  1. x1 + x2 > x3
  2. x2 - x4 = 2
  3. x1 + x4 < x5

x1～のそれぞれがx5ドメイン内にある{0,1,2}

{(0,0,0), (0,0,1), (0,1,0),(0,1,1),(1,0,0), ......}タプルのセットが次のようになるように、さまざまな組み合わせをプログラムするにはどうすればよいですか。

これはインスタントの制約1であり、次のようなタプルのドメインがあります{(0,0,0), (0,0,1), (0,1,0),(0,1,1),(1,0,0),(0,1,2),(2,0,1) ......}

どの言語でも返信が必要ですが、できれば Java でお願いします。

4

1 に答える 1

1

これは、google commons collect ライブラリのいくつかのヘルパー メソッドを使用して行うことができます。次のようになります。

タプル (0,0,0) などは、constraint1 の場合は (x0, x1, x2)、constraint2 の場合は (x2, x4) など、制約への入力のタプルであると想定しています。

したがって、constraint1 については、最初に可能なすべての組み合わせをリストに入力します。

    final List<int[]> allCombos = new ArrayList<int[]>();
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                allCombos.add(new int[] {i, j, k});
            }
        }
    }
    for (final int[] i : allCombos) {
        System.out.println(i[0] + ", " + i[1] + ", " + i[2]);
    }

次に、constraint1 で許可されているタプルが残るようにフィルタリングします。

    final List<int[]> constraint1 = ImmutableList.copyOf(Iterables.filter(allCombos, new Predicate<int[]>() {
        @Override
        public boolean apply(@Nullable final int[] input) {
            return input[0] + input[1] > input[2];
        }
    }));

    for (final int[] i : constraint1) {
        System.out.println(i[0] + ", " + i[1] + ", " + i[2]);
    }

これには少し説明が必要かもしれません。

ImmutableList.copyOf は、指定されたリストのコピーを作成するメソッドです。このメソッドには、リスト (フィルタリングされる入力) を取る Iterables.filter() の結果と、オーバーライドされたメソッド apply() を持つ Predicate を渡します。結果リストの一部であるはずです。ここでは、基本的に制約自体をコーディングするだけで、apply メソッドが true を返す場合は、フィルター処理されたリストの一部になります。(タプルを配列として表現することを選択しました。任意のタプル表現でフィルター戦略を使用できます..)

最後の印刷結果 (フィルタリングされたリスト) は次のようになります。

0, 1, 0
0, 2, 0
0, 2, 1
1, 0, 0
1, 1, 0
1, 1, 1
1, 2, 0
1, 2, 1
1, 2, 2
2, 0, 0
2, 0, 1
2, 1, 0
2, 1, 1
2, 1, 2
2, 2, 0
2, 2, 1
2, 2, 2

他の制約についても同じことを行うのはあなたに任せます..

于 2012-09-16T13:35:35.317 に答える