编程知识 cdmana.com

定位导航算法高级框架设计

1、蒙特卡罗树搜索 - 图形化模拟 Upper Confidence bound applied to Trees(UCT)

2、 calculation_time来控制时间

3、选举(selection)是根据当前获得所有子步骤的统计结果，选择一个最优的子步骤。

4、扩展(expansion)在当前获得的统计结果不足以计算出下一个步骤时，随机选择一个子步骤。

5、模拟(simulation)模拟决策过程，进入下一步。

6、反向传播(Back-Propagation)根据决策的结果，计算对应路径上统计记录的值。

7、置信区间(confidence intervals)是指由样本统计量所构造的总体参zhi数的估计区间，窄的置信区间比宽的置信区间能提供更多的有关总体参数的信息。越小的置信区间置信度就越高。

``````package tools;

import java.util.ArrayList;
import java.util.Calendar;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class Sampler {
private static Random rng = new Random(
Calendar.getInstance().getTimeInMillis() +

public static Random getRandom() {
return rng;
}

public static boolean sampleCoin() {
return rng.nextBoolean();
}

public static double sampleBeta(double alpha, double beta) {
double x, y;
x = sampleGamma(alpha, 1);
y = sampleGamma(beta, 1);
return x / (x + y);
}

// Sample from the 1 - X where X ~ beta( alpha , beta)
public static double one_minus_sampleBeta(double alpha, double beta) {
double x, y;
x = sampleGamma(alpha, 1);
y = sampleGamma(beta, 1);
return y / (x + y);
}

public static long nextPoisson(double lambda) {
return (long) (-1.0 * Math.log(1.0 - rng.nextDouble() * 1.0) / lambda);
}

public static double nextExponential(double b) {
double randx;
double result;
randx = rng.nextDouble();
result = -1 * b * Math.log(randx);
return result;
}

public static double sampleGamma(double k, double theta) {
boolean accept = false;
if (k < 1) {
// Weibull algorithm
double c = (1 / k);
double d = ((1 - k) * Math.pow(k, (k / (1 - k))));
double u, v, z, e, x;
do {
u = rng.nextDouble();
v = rng.nextDouble();
z = -Math.log(u);
e = -Math.log(v);
x = Math.pow(z, c);
if ((z + e) >= (d + x)) {
accept = true;
}
} while (!accept);
return (x * theta);
} else {
// Cheng's algorithm
double b = (k - Math.log(4));
double c = (k + Math.sqrt(2 * k - 1));
double lam = Math.sqrt(2 * k - 1);
double cheng = (1 + Math.log(4.5));
double u, v, x, y, z, r;
do {
u = rng.nextDouble();
v = rng.nextDouble();
y = ((1 / lam) * Math.log(v / (1 - v)));
x = (k * Math.exp(y));
z = (u * v * v);
r = (b + (c * y) - x);
if ((r >= ((4.5 * z) - cheng)) ||
(r >= Math.log(z))) {
accept = true;
}
} while (!accept);
return (x * theta);
}
}

public static Double[] subSampleNaive(List<Double> samples, int m) {
int n = samples.size();
int nm = Math.min(m, n);
Double[] sub = new Double[nm];
if (nm == n) {
sub = samples.toArray(sub);
return sub;
}
for (int k = 0; k < nm; k++) {
int i = rng.nextInt(n);
Double aux = samples.get(k);
samples.set(k, samples.get(i));
samples.set(i, aux);
}
sub = samples.subList(0, nm).toArray(sub);
return sub;
}

public static Double[] subSample(List<Double> samples, int m) {
//System.out.println(samples.size() +" " + m);

int n = samples.size();
int nm = Math.min(m, n);
Double[] sub = new Double[nm];
if (nm == n) {
sub = samples.toArray(sub);
return sub;
}
if (m < n / 2) {
for (int k = 0; k < nm; k++) {
int i = rng.nextInt(n);
Double aux = samples.get(0);
samples.set(0, samples.get(i));
samples.set(i, aux);
}
sub = samples.subList(0, nm).toArray(sub);
} else {
for (int k = 0; k < n - nm; k++) {
int i = rng.nextInt(n);
Double aux = samples.get(0);
samples.set(0, samples.get(i));
samples.set(i, aux);
}
sub = samples.subList(n - nm, n).toArray(sub);
}
return sub;
}

}
``````

https://my.oschina.net/u/4383709/blog/4816195

Scroll to Top