- represent they circle as a directed, connected cycle graph $G(V,E)$ with vertices $V\ =\ \lbrace v_i\ |\ 1\le i\le n\rbrace$ and directed edges $E=\lbrace e_{ij}=(v_i,v_{i+1})\ |\ 1\le i \lt n\rbrace \cup\lbrace (v_n,v_1)\rbrace$
- map each vertex $v_i$ to $A_i$
- while $E\ne\emptyset$
- determine edge $e_{i,j}^*$ that minimizes the sum $A_i^*+A_j^*$$A_i^*+A_j^* $ of adjacent-vertex weights
- record $A_i^*+A_j^*$$A_i^*+A_j^* $
- assuming $(v_j^*,v_k)\in E$
- $A_i^* := A_i^*+A_j^*$,
- $E = E\cup (v_i^*,v_k)$,
- $V=V\setminus v_j^*$
running the algorithm with the sequence provided by the PO in a comment yields
$9,\ 4,\ (2+3),\ 2,\ 9\ \mapsto\ 9,\ 4,\ (5+2),\ 9\ \mapsto\ 9,\ (4+7),\ 9\ \mapsto\ (9+9),\ 11\ \mapsto\ (18+11)$, resp.
$9,\ 4,\ 2,\ (3+2),\ 9\ \mapsto\ 9,\ (4+2),\ 5,\ 9\ \mapsto\ 9,\ (6+5),\ 9\ \mapsto\ (9+9),\ 11\ \mapsto\ (18+11)$
the numbers generated by additon are $5,7,11,18,29$, resp. $5,6,11,18,29$, demonstrating that the heuristic fails to generate the optimal sequence of additions; please keep in mind that the numbers are arranged on a circle, which is why the $(9+9)$ sums are "legal".
Edit 2019-07-07:
An improvement on the above heuristic is possible, if one asks the right questions; if one encodes the order of additions via braces, as is customary in programming languages, two basic questions come up:
- how does nesting depth affect the sum of intermediate sums?
- how does the order of numeric values affect the result if the nesting pattern of the braces is the same?
these questions can be investigated by checking simple illustrative examples, albeit that doesn't qualify as a proof of correctness.
for **investigating the first question**, we consider an arrangemnt of eight ones around the circle and compare the linear nesting:$(((((((1+1)+1)+1)+1)+1)+1)+1)$which generates as the sequence of intermediate results of additions$2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8$, which sums up to$35$with the "binary tree" nesting:$(((1+1)+(1+1))+((1+1)+(1+1)))$which generates the sequence(level by level from leaf "node" to root "node") of intermediate results$2,\ 2,\ 2,\ 2,\ 4,\ 4,\ 8$, which sums up to$24$
The conclusion is that summation with low nesting depth is preferable to high nesting depth.
for **investigating the second question**, we compare the "linear" addition of an arithmetic sequence in ascending and in descending order:$(((((((1+2)+3)+4)+5)+6)+7)+8)$generates$3,\ 6,\ 10,\ 15,\ 21,\ 28,\ 36$, which sums up to$119$$(((((((8+7)+6)+5)+4)+3)+2)+1)$generates$15,\ 21,\ 26,\ 30,\ 33,\ 35,\ 36$, which sums up to$196$
The conclusion is that small values should be added before large ones
**An improved$O(n^2)$ heuristic based on the observations:**- in every iteration determine a minimum weight maximal matching and combine the pairs of values via addition that are adjacent to the same matching edge; that halves the number of values in each iteration, resulting in$O(n)$ iterations.- the minimum weight maximal matching of a cycle graph can be determineded in$O(n)$ time, which amounts to a total of$O(n)\cdot O(n) = O(n^2)$ time complexity$
applying the algorithm on the example sequence$9,\ 4,\ 2,\ 3,\ 2,\ 9$:the two maximal matchings are$\lbrace(9,4),\ (2,3),\ (2,9)\rbrace$, generating sum$13+5+11=29$and$\lbrace(4,3),\ (3,2),\ (9,9)\rbrace$, generating sum$7+5+18=30$
in the next iteration the number of nodes is odd and we thus have three maximal matchings in $7,\ 5,\ 18$ the one with minimum weight is
$\lbrace(7,5)\rbrace$, yielding $(7+5)+18\ =\ 12+30\ =\ 52$
for the other two matchings we have:
$\lbrace(5,18)\rbrace$ yields $(5+18)+7\ =\ 23+30\ =\ 53$
$\lbrace(18,7)\rbrace$ yields $(18+7)+5\ =\ 25+30\ =\ 55$
which gives a strong indication of the correctness of the improved heuristic.
It remains to show that values of the $2k+1$ maximal matchings in case of a cycle graph with an odd number of vertices can be calculated in $O(2k+1)$ time:
suppose the value of a maximal matching is known and that $u$ is the vertex not adjacent to any of the matching's edges. If vertex $v$ is immediate neighbor to $u$ and $w$ on the circle, then the value of the matching $M_w$ with $w$ not adjacent to a matching edge can be calculated in $O(1)$ from the value of $M_u$ by adding $\left(|(u,v)|\ -\ |(v,w)|\right)$