Traversal của một không gian n chiều

Question

Tôi đang cố gắng viết một thuật toán cho phép tôi lặp qua tất cả các điểm mong muốn trong một không gian n chiều để tìm mức tối thiểu của hàm f (x) trong đó x là vectơ kích thước n.

Rõ ràng, việc tìm kiếm một 2-d hoặc 3-d không gian là khá đơn giản, bạn chỉ có thể làm:

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

Thật không may, đối với vấn đề của tôi, số chiều của không gian không cố định (tôi viết một công cụ tìm kiếm tối thiểu tổng quát cho nhiều chức năng trong một chương trình thống kê) và vì vậy tôi phải viết các vòng lặp cho mỗi giá trị của n tôi muốn sử dụng - mà cuối cùng có thể khá lớn.

Tôi đã cố gắng để có được đầu của tôi xung quanh làm thế nào tôi có thể làm điều này bằng cách sử dụng đệ quy nhưng không thể nhìn thấy các giải pháp - mặc dù tôi chắc chắn có một ở đó.

Giải pháp không cần phải đệ quy, nhưng nó phải là chung và hiệu quả (đường bên trong nhất trong vòng lặp lồng nhau đó sẽ được gọi là rất nhiều ...).

Con đường tôi đang đại diện cho khối lượng tìm kiếm là một mảng 2ngày của kép:

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

này sẽ đại diện cho một không gian 4d với mức tối thiểu và tối đa bị ràng buộc trong mỗi chiều ở vị trí 0 hoặc 1 trong những mảng, tương ứng. Ví dụ:

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

Bất kỳ ý tưởng nào?

Answer 1

Đây là ý tưởng chung:

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

Không phải là chức năng chỉ:

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

Answer 3

Tôi muốn gắn bó với reucrsion, và sử dụng Object như một tham số, với một tham số thêm dim và truyền khi bạn đạt đến độ sâu 1 đến mảng có liên quan [trong ví dụ của tôi, nó là một 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; 
} 

dụ:

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

sẽ sản xuất:

0 

Ưu điểm của phương pháp này là không cần bất kỳ xử lý của mảng - bạn chỉ cần gửi nó như nó là, và gửi kích thước như một tham số.
Nhược điểm - là loại [un] an toàn, vì chúng tôi tự động truyền Object vào một mảng.

Answer 4

Một tùy chọn khác là lặp lại từ 0 đến x * y * z * ... giống như khi bạn chuyển đổi một số giữa các biểu diễn nhị phân và thập phân. Đây là giải pháp không đệ quy, do đó bạn sẽ không gặp phải sự cố về hiệu suất.

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

mảng n chiều có thể được làm phẳng thành mảng một chiều.Những gì bạn cần là làm toán cho những việc này:

• Tính kích thước của mảng đơn hướng cần thiết.
• Tìm ra các công thức cần thiết để dịch ngược từ chỉ mục n-chiều sang chỉ số một chiều.

Đây là những gì tôi muốn làm:

• Đại diện cho kích thước mảng n chiều và lập chỉ mục như int[]. Vì vậy, kích thước của mảng 4 chiều 5x7x13x4 được biểu diễn dưới dạng mảng 4 phần tử `{5, 7, 13, 4} '.
• Mảng n chiều được biểu diễn dưới dạng mảng đơn hướng có kích thước là sản phẩm có kích thước của từng kích thước. Vì vậy, một mảng 5x7x13x4 sẽ được biểu diễn như một mảng phẳng có kích thước 1.820.
• Chỉ mục n chiều được dịch thành một chỉ mục duy nhất trong mảng phẳng bằng phép nhân và cộng. Vì vậy, chỉ mục < 3, 2, 6, 0> vào mảng 5x7x13x4 được dịch là 3 + 2*5 + 6*5*7 + 0*5*7*13 == 223. Để truy cập chỉ mục 4 chiều đó, hãy truy cập chỉ mục 223 trong mảng phẳng.
• Bạn cũng có thể dịch ngược từ chỉ mục mảng phẳng sang chỉ mục n chiều. Tôi sẽ để nó như là một bài tập (nhưng về cơ bản nó thực hiện các phép tính modulo n).

Answer 6

này chạy qua một Danh sách Danh sách giá trị (Số nguyên) và chọn mức tối thiểu của mỗi liệt kê:

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