1

我在java中编程以下问题时遇到问题，这是一个约束满足问题：

如果我有这样的限制：

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

每个x1tox5都在域中{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）等是约束输入的元组，（x0，x1，x2）用于约束1，（x2，x4）用于约束2等。

因此，对于约束 1，首先我们用所有可能的组合填充一个列表：

    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]);
    }

接下来，我们要过滤，所以我们将得到约束 1 允许的元组：

    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() 的结果，它接受一个列表（要过滤的输入）和一个 Predicate，它有一个重写的方法 apply()，您可以在其中决定输入列表的哪个元素应该是结果列表的一部分。在这里，我们基本上只是对约束本身进行编码，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 回答