java - n维空间的遍历

Question

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

显然，搜索 2-d 或 3-d 空间非常简单，您可以简单地执行以下操作：

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[][] 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

有任何想法吗？

score 5 · Accepted Answer

这是一般的想法：

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

score 2 · Accepted Answer

我会坚持使用递归，并将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));
}

将产生：

这种方法的优点是不需要对数组进行任何处理 - 您只需按原样发送它，并将维度作为参数发送。
不利的一面是类型 [un]safety，因为我们动态地将其Object转换为数组。

score 1 · Accepted Answer

n 维数组可以展平为一维数组。您需要对这些事情进行数学计算：

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

这就是我要做的：

将 n 维数组大小和索引表示为int[]。因此，5x7x13x4 4 维数组的大小表示为 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 模计算）。

score 1 · Accepted Answer

另一种选择是从 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
}

score 0 · Accepted Answer

这将遍历值列表（整数）并选择每个列表的最小值：

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

score 0 · Accepted Answer

功能不只是：

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

java - n维空间的遍历

6 回答 6

Related

Reference