Recorrido de un espacio n-dimensional

Question

Estoy tratando de escribir un algoritmo que me permita iterar sobre todos los puntos deseados dentro de un espacio n-dimensional para encontrar el mínimo de una función f (x) donde x es un vector de tamaño n.

Obviamente, la búsqueda de un espacio de 2-D o 3-D es bastante sencillo, sólo tiene que hacer:

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

Desafortunadamente, para mi problema, la dimensionalidad del espacio no es fijo (soy escribir un buscador mínimo generalizado para muchas funciones en un programa estadístico) y entonces tendría que escribir bucles para cada valor de n que quiero usar, que en última instancia podría ser bastante grande.

He estado tratando de entender cómo podría hacer esto utilizando recursividad pero no puedo ver la solución, aunque estoy seguro de que hay uno allí.

La solución no tiene que ser recursiva, pero debe ser general y eficiente (a la línea más interna de ese bucle anidado se le llamará muchísimo ...).

La forma en que estoy que representa el volumen de búsqueda es una matriz 2D de doble:

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

Esto representaría un espacio 4d con el mínimo y máximo atado en cada dimensión en la posición 0 o 1 de la matriz, respectivamente. Por ejemplo:

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

¿Alguna idea?

Answer 1

Aquí es la idea general:

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

Answer 2

no es la función simplemente:

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

Answer 3

me quedo con reucrsion, y el uso de Object como un parámetro, con un parámetro adicional de dim, y emitirlo cuando se alcanza una profundidad de 1 a la matriz pertinente [en mi ejemplo, es un 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; 
} 

ejemplo:

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

producirá:

0 

La ventaja de este enfoque es necesario ningún procesamiento de la matriz - que acaba de enviar tal cual es, y enviar la dimensión como un parámetro.
La desventaja es la seguridad de tipo [un], ya que dinámicamente lanzamos el Object a una matriz.

Answer 4

Otra opción es repetir de 0 a x * y * z * ... como lo hace al convertir un número entre representaciones binarias y decimales. Esta es una solución no recursiva, por lo que no se encontrará con problemas de rendimiento.

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 
} 

Answer 5

Las matrices n-dimensionales se pueden aplanar en matrices unidimensionales.Lo que necesita es hacer los cálculos para estas cosas:

• Calcule el tamaño de la matriz unidimensional necesaria.
• Descubre las fórmulas necesarias para traducir desde el índice n-dimensional al unidimensional.

Esto es lo que haría:

• Representar tamaños de matriz n-dimensional e índices como int[]. Entonces, el tamaño de una matriz de 4 dimensiones de 5x7x13x4 representada como la matriz de 4 elementos `{5, 7, 13, 4} '.
• Una matriz n-dimensional se representa como una matriz unidimensional cuyo tamaño es el producto de los tamaños de cada una de las dimensiones. Entonces, una matriz de 5x7x13x4 se representaría como una matriz plana de tamaño 1,820.
• Un índice n-dimensional se traduce en un índice único en la matriz plana por multiplicación y adición. Entonces, el índice < 3, 2, 6, 0> en la matriz 5x7x13x4 se traduce como 3 + 2*5 + 6*5*7 + 0*5*7*13 == 223. Para acceder a ese índice de 4 dimensiones, accede al índice 223 en la matriz plana.
• También puede traducir al revés de índices de matriz plana a índices n-dimensionales. Lo dejo como ejercicio (pero básicamente está haciendo n cálculos de módulo).

Answer 6

Esto se ejecuta a través de una lista de lista de valores (enteros) y recoge el mínimo de cada lista:

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