java - 多维空间算法

Question

我一直在尝试设计一种算法，可以从另一个 N 维空间中减去 N 维空间的 block 。

为了简单起见，底部的餐巾纸草稿使用二维空间显示了一些数学和视觉效果。

业务问题: 想象一下有 30 组数据(在本例中意味着 30 维空间)的所有可能组合。笛卡尔积会向我显示所有可能的组合，但问题是我需要反转它。做到这一点，当我获得 15 个 30 维数据实例时，我可以在最初的 30 维空间中分块，看看是否还有任何未被覆盖的内容。

第一个问题是我没有找到任何第三方 JAVA 库来处理这个问题 - 也许我没有使用正确的关键字，我的教育不是英语。

现在第二个问题是我正在尝试用 java 来解决这个问题。正如您所看到的，代表结构的 XY 坐标空间旁边有一个简化的 UML 图。对于数据存储，我想使用 Map<Object, Set<String>> (对象是维度，集合是其值)因为我不想限制哪个键应该代表维度，并且我希望我的维度保存字符串值，因为它们已经具有 hashCode 和重写等于方法。

所以我一直在研究 SimpleSpace 的减法算法:

    public AbstractSpace subtract(AbstractSpace abstractSpace) {
        //Some checks
                if (!(abstractSpace instanceof SimpleSpace)) {
                    return null;
                }
                if (getDimensions().size() != abstractSpace.getDimensions().size()) {
                    return null;
                }
                if (!getDimensions().equals(abstractSpace.getDimensions())) {
                    return null;
                }

                SimpleSpace spaceToRemove = (SimpleSpace) abstractSpace;
                final Map> template = Maps.newHashMap();
                final Set prevDimension = Sets.newHashSet();
                final List result = Lists.newArrayList();
                //getDimensions() just retrieves the SimpleSpace Map.keySet()
                for (Object dimension : getDimensions()) {
                //copy method makes a deep copy of current simpleSpace map as I do not want to change state of SimpleSPace instance
                    SimpleSpace editSpace = copy();
                    editSpace.remove(dimension, spaceToRemove.getValues(dimension));
                    //This bit over here is implementation of my poor math understandment
                    for (Object prevKey : prevDimension) {
                        editSpace.getValues(prevKey).removeAll(template.get(prevKey));
                    }
                    prevDimension.add(dimension);
                    template.put(dimension, editSpace.getValues(dimension));
                    result.add(editSpace);
                }
                 //I remove all simpleSpaces which have a dimension with empty set (this is not efficient but this is the first iteration) 
                Iterables.removeIf(result, new Predicate() {
                    @Override
                    public boolean apply(SimpleSpace input) {
                        return input.isEmpty();
                    }
                });

                return new CompositeSpace(result);
            }

虽然这有效，但我似乎使用二维示例，但我不完全理解如何使用 N 维空间测试它。

我是否应该将所有复合空间重新组合在一起，看看是否可以将分解的 N 维空间重新组合在一起？顺便问一下，也许有人可以建议一种更有效的算法？

如果缺少任何信息，请告诉我。

谢谢。

Answer 1

这实际上是一个变相的约束规划问题。每个维度对应一个变量及其可能的值。每个 SimpleSpace 对应一个约束，要求至少一个变量具有指定子集之外的值。未发现的点和可行解是一一对应的。即使是基本的约束编程库也会比暴力破解有相当大的改进。