遍历n维空间

Question

我将翻译以下内容，涉及IT技术：

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

显然，在2维或3维空间中搜索相对简单，你可以简单地执行以下操作：

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

很不幸，对于我的问题，空间的维度并不是固定的（我正在为统计程序中的许多函数编写广义最小值查找器），因此我必须为我想要使用的每个n值编写循环 - 这可能最终会相当大。

我一直在试图想出如何使用递归来解决这个问题，但是还没有看到解决方案 - 尽管我确定有一个解决方案。

解决方案不一定要是递归的，但它必须是通用和高效的（在那个嵌套循环中最内层的行将被调用很多次...）。

我表示要搜索的体积的方式是一个双精度的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

有什么想法吗？

- Chilly

---

我其实不是新手，只是很久以前丢失了我的账户 :P - Chilly

你如何处理带有小数的范围，例如 -0.5 到 0.2？此外，在内部循环中需要什么数据来处理它？是点的数组吗？ - mellamokb

你可以从这个问题中获得一些灵感，因为它是一个等价的问题：https://dev59.com/1F_Va4cB1Zd3GeqPQR4g（我毫不羞耻地推广它，因为我在那里有被接受的答案...）其中提出了递归和迭代解决方案。 - Oliver Charlesworth

mellamokb：我使用一个分辨率函数来生成我需要的每个维度的步长。我不会实际使用 int i = 0; i < 10; i++，而是使用 double i = 0; i < 0.44; i+=0.002。 - Chilly

根据您使用的函数类型，可能存在一些微积分知识可以减少您需要搜索的空间大小，例如找到主函数导数的最小值和最大值。 - mellamokb

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

- Eugene Retunsky

---

应该是 currentDimension + 1，而不是 currentDimension++，这样就可以完美地工作了。否则是+1。 - mellamokb

我收回之前的话。这个解决方案还有一些杂项问题，我已经通过编辑进行了修复，希望没问题。 - mellamokb

这可能是你能得到的最好的结果。你的解决方案平均需要约50毫秒才能从{0,0,0,0}运行到{50,50,50,50}：http://ideone.com/oxJDe。我通过在这里消除递归，使其稍微快了一点（约为`40毫秒`）：http://ideone.com/uJ4jn。 - mellamokb

感谢您修复我的解决方案。我只是在匆忙中输入了几分钟:) 是的，如果我最初输入currentDimension ++，那就是明显的错误。而且它应该是== p.lenght-1。 - Eugene Retunsky

对于整数索引很好用，但是对于实数索引就有点棘手了。 - Chilly

啊，但将真实索引映射到固定的整数范围很容易。这非常棒。 - Chilly

Answer 2

我建议使用递归，并将Object作为参数，再加上一个dim参数，在深度为1时将其转换为相关的数组类型[在我的示例中，它是一个int[]]。

public static int getMin(Object arr, int dim) {
    int min = Integer.MAX_VALUE;
    //stop clause, it is 1-dimensional array - finding a min is trivial
    if (dim == 1) { 
        for (int x : ((int[])arr)) {
            min = Math.min(min,x);
        }
    //else: find min among all elements in an array of one less dimenstion.
    } else { 
        for (Object o : ((Object[])arr)) { 
            min = Math.min(min,getMin(o,dim-1));
        }
    }
    return min;
}

例子：

public static void main(String[] args) {
    int[][][] arr = { { {5,4},{2}, {35} } , { {2, 1} , {0} } , {{1}}};
    System.out.println(getMin(arr, 3));
}

将产生：

0

这种方法的优点是不需要对数组进行任何处理 - 你只需按原样发送它，并将维数作为参数发送。
缺点是类型不安全，因为我们动态地将 Object 强制转换为数组。

- amit

Answer 3

另一个选择是从0到x*y*z*...进行迭代，就像在二进制和十进制表示之间转换数字时所做的那样。这是一种非递归解决方案，因此您不会遇到性能问题。

ndims = n;
spacesize = product(vector_sizes)
int coords[n];

for (i = 0; i < spacesize; i++) {
    k = i;
    for (j = 0; j < ndims; j++ ) {
         coords[j] = k % vector_sizes[j];
         k /= vector_sizes[j];
    }
    // do something with this element / these coords
}

- j13r

---

这是一个非递归解决方案，因此您不会遇到性能问题。但这并不是一个相关的陈述。递归解决方案实际上可能更有效，因为它们不必不断重新填充内部数组，并且递归级别永远不会比维度数更深。此外，由于所有值都是双精度浮点数，因此您的解决方案可能会遇到舍入误差的问题。 - mellamokb

你将调用spacesize个函数（完整的树），并通过复制或指针传递坐标（在Eugene的解决方案中为p）。你需要做更多的工作。 - j13r

如果您的coords[j] = stepfunction(k, vector_sizes[j])且为双精度坐标，则不会出现舍入误差。 - j13r

例如，我对您的解决方案和@Eugene的解决方案进行了一些分析。 从{0,0,0,0}到{50,50,50,50}运行，您的解决方案需要约650毫秒，而@Eugene的解决方案需要约50毫秒。 如果您不相信我，请查看http://ideone.com/oxJDe和http://ideone.com/nUdrl，这是我两个解决方案的工作实现，带有输出和时间记录。 - mellamokb

有趣。我没想到。 - j13r

Answer 4

n维数组可以压缩成一维数组。您需要做的是针对以下事项进行数学计算：

• 计算所需一维数组的大小。
• 找出从n维索引转换回一维索引所需的公式。

这就是我会做的：

• 将n维数组的大小和索引表示为int[]。因此，5x7x13x4四维数组的大小表示为4元素数组`{5, 7, 13, 4}`。
• n维数组表示为一维数组，其大小是每个维度大小的乘积。因此，5x7x13x4数组将表示为大小为1,820的平坦数组。
• n维索引通过乘法和加法转换为平坦数组中的唯一索引。因此，5x7x13x4数组中的索引<3, 2, 6, 0>被翻译为3 + 2*5 + 6*5*7 + 0*5*7*13 == 223。要访问该4维索引，请在平坦数组中访问索引223。
• 您还可以从平坦数组索引向后转换为n维索引。我会把它留作练习（但基本上是进行n模运算）。

- Luis Casillas

---

Java支持锯齿数组。对于这种情况，它不会失败吗？（即：{{1,2,3},{1}}） - amit

@amit：我本来想评论你的回答。OP不是在寻找不规则数组，而是要搜索整个n维网格空间。 - mellamokb

那么这个解决方案就适合了。我认为你应该为它添加一个明确的指示，以便未来的读者。 - amit

Answer 5

这个函数不就是：

Function loopDimension(int dimensionNumber)
    If there is no more dimension, stop;
    for(loop through this dimension){
         loopDimension(dimensionNumber + 1);
    }

- Alderath

Answer 6

这个程序遍历一个值（整数）的列表，选择每个列表中的最小值：

import java.util.*;
/**
    MultiDimMin

    @author Stefan Wagner
    @date Fr 6. Apr 00:37:22 CEST 2012

*/
public class MultiDimMin
{
    public static void main (String args[])
    {
        List <List <Integer>> values = new ArrayList <List <Integer>> ();
        Random r = new Random ();
        for (int i = 0; i < 5; ++i)
        {   
            List<Integer> vals = new ArrayList <Integer> ();            
            for (int j = 0; j < 25; ++j)
            {   
                vals.add (100 - r.nextInt (200));   
            }
            values.add (vals);
        }
        showAll (values);
        List<Integer> res = multiDimMin (values);
        show (res);
    }

    public static int minof (List <Integer> in)
    {
        int res = in.get (0);
        for (int v : in)
            if (res > v) res = v;
        return res;
    }

    public static List<Integer> multiDimMin (List <List <Integer>> in)
    {
        List<Integer> mins = new ArrayList <Integer> ();
        for (List<Integer> li : in) 
            mins.add (minof (li));
        return mins; 
    }

    public static void showAll (List< List <Integer>> lili)
    {
        for (List <Integer> li : lili) {
            show (li);
            System.out.println ();
        }
    }   

    public static void show (List <Integer> li)
    {
        for (Integer i: li) {
            System.out.print (" " + i);
        }
        System.out.println ();
    }   
}

- user unknown