我花了大量時間來弄清楚如何為
我們有
u^2 h^2 = C^2v^2 h^2 = B^2A = u v
然后給定A向量，我們可以找到相反的頂點并創建兩個新的基。
使用蠻力（我們可以使用一些啟發式方法，但問題指出n將小于 9，然后：
public class ConstructionToy {
static class V2 { double x, y; V2(double X, double Y) { x = X; y = Y; } }
static class Vec { V2 from, to; double length; Vec(V2 f, V2 t, double l) {from = f; to = t; length = l; } }
static V2 sub(V2 a, V2 b) { return new V2(a.x - b.x, a.y - b.y); }
static V2 sum(V2 a, V2 b) { return new V2(a.x b.x, a.y b.y); }
static V2 mul(V2 a, double k) { return new V2(a.x * k, a.y * k); }
static class Step { Vec e1, e2; V2 vertex; Step(Vec E1, Vec E2, V2 vx) { e1 = E1; e2 = E2; vertex = vx; }}
// triangle with base A adding edges B and C generate new two bases (over B and over C)
// triangle is generated on the clockwise side of A vector
static Step next(Vec A, double B, double C) {
V2 delta = sub(A.to, A.from);
V2 vec = mul(delta, 1.0 / A.length);
V2 tan = new V2(vec.y, -vec.x);
double v = (A.length * A.length - B * B C * C) / (2 * A.length); // could be optimized memoizing
double h2 = C * C - v * v;
if(h2 < 0.0)
return null;
double h = Math.sqrt(h2);
V2 vertex = sum(sum(A.from, mul(vec, v)), mul(tan, h));
return new Step(new Vec(vertex, A.to, B), new Vec(A.from, vertex, C), vertex);
}
static double bruteForce(double [] edges, Set<Integer> used, Vec base) {
if(edges.length - used.size() < 2)
return 0.0;
double max = 0.0;
// for every two (not used) edges we can construct a new triangle
for(int i = 0; i < edges.length; i )
if(!used.contains(i)) {
used.add(i);
for (int j = 0; j < edges.length; j )
if(!used.contains(j)) {
used.add(j);
Step s = next(base, edges[i], edges[j]);
if(s != null) {
max = Math.max(max, s.vertex.x);
max = Math.max(max, bruteForce(edges, used, s.e1));
max = Math.max(max, bruteForce(edges, used, s.e2));
max = Math.max(max, bruteForce(edges, used, new Vec(s.e1.to, s.e1.from, s.e1.length)));
max = Math.max(max, bruteForce(edges, used, new Vec(s.e2.to, s.e2.from, s.e2.length)));
}
used.remove(j);
}
used.remove(i);
}
return max;
}
static double bruteForce(double [] edges) {
Set<Integer> used = new HashSet<>();
double max = 0.0;
for(int i = 0; i < edges.length; i ) {
used.add(i);
max = Math.max(max, bruteForce(edges, used, new Vec(new V2(0.0, 0.0), new V2(0.0, edges[i]), edges[i])));
used.remove(i);
}
return max;
}
public static void main(String... args) {
double r = bruteForce(new double [] {42, 40, 32, 30, 25, 18, 15});
System.out.println(" " r " (err: " Math.abs(66.9495287 - r) ")");
}
帶輸出
66.94952872219118 (err: 2.2191173343344417E-8)
代替蠻力，我們可以使用簡單的啟發式方法，即，由于每個三角形都需要兩條邊，因此從我們所在的點開始，我們最多可以將突出邊的總和除以二，如果不是夠了，不值得繼續
static double heuristic(double best, double [] edges, Set<Integer> used, Vec base) {
if(edges.length - used.size() < 2)
return 0.0;
double max = best;
// for every two (not used) edges we can construct a new triangle
for(int i = 0; i < edges.length; i )
if(!used.contains(i)) {
used.add(i);
for (int j = 0; j < edges.length; j )
if(!used.contains(j)) {
used.add(j);
Step s = next(base, edges[i], edges[j]);
if(s != null) {
// if not enough edges to reatch the best don't try
double maxNext = 0.0;
for(int k = 0; k < edges.length; k )
if(!used.contains(k))
maxNext = edges[k];
if(s.vertex.x > best - 0.5 * maxNext) {
max = Math.max(max, s.vertex.x);
max = Math.max(max, heuristic(max, edges, used, s.e1));
max = Math.max(max, heuristic(max, edges, used, s.e2));
max = Math.max(max, heuristic(max, edges, used, new Vec(s.e1.to, s.e1.from, s.e1.length)));
max = Math.max(max, heuristic(max, edges, used, new Vec(s.e2.to, s.e2.from, s.e2.length)));
}
}
used.remove(j);
}
used.remove(i);
}
return max;
}
static double heuristic(double [] edges) {
Set<Integer> used = new HashSet<>();
double max = 0.0;
for(int i = 0; i < edges.length; i ) {
used.add(i);
max = Math.max(max, heuristic(max, edges, used, new Vec(new V2(0.0, 0.0), new V2(0.0, edges[i]), edges[i])));
used.remove(i);
}
return max;
}
要獲得最佳演算法，請應用相同的啟發式方法，但將每個狀態添加到優先級佇列中，這樣您將始終采取最有可能前進的步驟，從而消除候選者。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344362.html
上一篇：PineScript不繪制框