"Joe Taicoon" <ask.if.you@need.it> writes:
> Hvis man har n objekter som man vil simulere under gensidig
> tyngdpåvirkning så er det O(n^2) hvis man naivt beregner kraft mellem
> hvert par af objekter.
> Ville en helt banal optimering ikke være at inddele ens rum i et
> oct-tree og i hver celle beregne den gennemsnitlige position (vægtet
> efter masse) og samlede masse for alle objekter i cellen og så
> herefter behandle alle objekterne i en celle som eet objekt med denne
> fælles masse og position?
Jeg nævnte tidligere Appel's artikel, men da den ikke er nem
tilgængelig, vil jeg lige opsummere metoden. Det er efter
hukommelsen, så nogle detaljer kan vere forkerte.
1. Det antages, at alle objekter er kugleformede, så massen kan
betragtes som værende i et punkt.
2. Sæt alle objekter ind i en træstruktur, sådan at objekter tæt ved
hinanden i rummet er tæt på hinanden i træet. Det kan evt. gøres
ved en rekursiv underopdeling af rummet i stil med octtrees.
3. Hver bladknude har koordinater for massen, massens størrelse og en
hastighedsvektor, samt et felt, hvor man kan indsætte
accelerationsvektoren, når den findes.
4. Indre knuder gives en samlet masse, et massemidtpunkt, en radius
samt et felt, hvor den samlede acceleration på undertræet kan
indsættes.
En finæsse er, at koordinater og hastigheder af objekter er relative
til forældreknudens position og hastighed. Dermed kan man flytte et
helt undertræ blot ved at flytte rodknuden af træet.
Algoritmen for beregning af acceleration af hvert objekt er nu:
accel(T1,P1,T2,P2) {
if distance(P1,P2) > k*(radius(T1)+radius(T2))
then {
acceleration(T1) += vector(P1,P2)*mass(T2)*G/distance(P1,P2)^2;
acceleration(T2) += vector(P1,P2)*mass(T1)*G/distance(P1,P2)^2
else if radius(T1) > radius(T2)
then let (T11,T12) = subtrees(T1) in {
accel(T11,P1+position(T11),T2,P2);
accel(T12,P1+position(T12),T2,P2)
}
else let (T21,T22) = subtrees(T2) in {
accel(T1,P1,T21,P2+position(T21));
accel(T1,P1,T22,P2+position(T22))
}
Inden dette gennemløb er acceleration(Ti) sat til 0 for alle
undertræer Ti. Det initielle kald er accel(T,P0,T,P0), hvor T er hele
træet og P0 er positionen af rodknuden. Da alle positioner er
relative, findes den faktiske position ved at summere positionerne fra
rodnkuden ned til den aktuelle position.
k er en konstant, der bestemmer nøjagtigheden af beregningen. Hvis k
er stor, er beregningen mere præcis, men tidsforbruget er større (da
man laver flere underopdelinger). G er gravtitionskonstanten.
Nu laves et gennemløb, hvor man flytter alle objekter:
move(T) {
position(T) += acceleration(T);
if T is not a root node
then let (T1,T2) = subtrees(T) in {
move(T1);
move(T2)
}
Efterhånden bliver træet mindre og mindre optimalt, da knuder, der før
var tæt på hinanden, kan ende med at være langt fra hinanden. En
mulighed er at genopbygge træet efter N gennemløb, men Appel foreslår,
at man i første gennemløb tilføjer en test:
Hvis T1 er en bladknude og radius(T2) > distance(P1,P2), så marker T1
til at flyttes over som undertræ til T2. Flytningen sker efter
move-fasen, og knuder over T1 og T2 får genberegnet deres position,
masse, radius og hastighed.
Appel angiver i artiklen køretiden til O(n*log(n)), men en senere
analyse viser, at køretiden faktisk er O(n), hvor konstantfaktoren
afhænger (ikke-lineært) af k.
Torben