7

私は、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の値ごとにループを作成する必要があります-最終的にはかなり大きくなる可能性があります。

私は再帰を使用してこれを行う方法について頭を悩ませようとしてきましたが、解決策を完全に理解することはできません-確かにそこにあるとは思いますが。

解決策は再帰的である必要はありませんが、一般的かつ効率的である必要があります（ネストされたループの最も内側の行は、ひどいロットと呼ばれることになります...）。

検索するボリュームを表す方法は、doubleの2次元配列です。

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

これは、配列の位置0または1の各次元で、それぞれ最小および最大の境界を持つ4d空間を表します。例えば：

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

何か案は？

4

6 に答える 6

5

一般的な考え方は次のとおりです。

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));
   }
});
于 2012-04-05T22:36:09.703 に答える
2

私はreucrsionに固執し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配列にキャストするため、タイプ[un]safetyです。

于 2012-04-05T22:38:22.550 に答える
1

n次元配列は、1次元配列にフラット化できます。あなたが必要とするのは、これらのことのために数学をすることです：

  • 必要な一次元配列のサイズを計算します。
  • n次元のインデックスから1次元のインデックスに戻すために必要な式を理解します。

これは私がすることです：

  • n次元配列のサイズとインデックスを。として表しますint[]。したがって、4要素配列 `{5、7、13、4}'として表される5x7x1​​3x44次元配列のサイズ。
  • n次元配列は、各次元のサイズの積であるサイズの1次元配列として表されます。したがって、5x7x1​​3x4配列は、サイズ1,820のフラット配列として表されます。
  • n次元のインデックスは、乗算と加算によってフラット配列内の一意のインデックスに変換されます。したがって、5x7x1​​3x4配列へのインデックス<3、2、6、0>はとして変換され3 + 2*5 + 6*5*7 + 0*5*7*13 == 223ます。その4次元インデックスにアクセスするには、フラット配列のインデックス223にアクセスします。
  • フラット配列インデックスからn次元インデックスに逆変換することもできます。これは演習として残しておきます（ただし、基本的にn個のモジュロ計算を実行しています）。
于 2012-04-05T23:04:51.437 に答える
1

もう1つのオプションは、2進数表現と10進数表現の間で数値を変換するときと同じように、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
}
于 2012-04-05T22:45:27.830 に答える
0

これは、値のリスト（整数）のリストを実行し、各リストの最小値を選択します。

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 ();
    }   
}
于 2012-04-05T23:06:38.037 に答える
0

関数だけではありません：

Function loopDimension(int dimensionNumber)
    If there is no more dimension, stop;
    for(loop through this dimension){
         loopDimension(dimensionNumber + 1);
    }
于 2012-04-05T22:35:42.227 に答える