遍历n维空间

Question

我正在尝试编写一种算法,让我迭代n维空间内的所有所需点,找到函数f(x)的最小值,其中x是大小为n的向量.

显然,搜索二维或三维空间相当简单,你可以简单地做:

for(int i = 0; i < x; i++) {
    for(int j = 0; j < y; j++) {
        //and so on for however many dimensions you want

不幸的是,对于我的问题,空间的维度并没有固定(我正在为统计程序中的许多函数编写一个通用的最小查找器),因此我必须为我想要使用的每个n值编写循环 - 最终可能会相当大.

我一直试图了解如何使用递归来实现这一点但却无法完全看到解决方案 - 尽管我确信那里有一个.

解决方案不一定是递归的,但它必须是通用的和有效的(嵌套循环中最内层的行将被称为非常多......).

我代表要搜索的卷的方式是double的2d数组:

double[][] space = new double[2][4];

这将表示4d空间,其分别在阵列的位置0或1中的每个维度中具有最小和最大界限.例如:

dim         0   1   2   3
    min(0):-10  5  10  -0.5
    max(1): 10 55  99   0.2

有任何想法吗？

Answer 1

这是一般的想法:

interface Callback {
   void visit(int[] p); // n-dimensional point
}

// bounds[] - each number the limits iteration on i'th axis from 0 to bounds[i]
// current - current dimension
// callback - point
void visit(int[] bounds, int currentDimension, int[] p, Callback c) {
   for (int i = 0; i < bounds[currentDimension]; i++) {
        p[currentDimension] = i;
        if (currentDimension == p.length - 1) c.visit(p);
        else visit(bounds, currentDimension + 1, p, c);
   }
}

/// now visiting
visit(new int[] {10, 10, 10}, 0, new int[3], new Callback() {
   public void visit(int[] p) {
        System.out.println(Arrays.toString(p));
   }
});