## An incremental approximate algorithm

```	int lookahead
while there are acids to place
explore all positions for the next lookahead acids
that minimize the energy of configuration so far
place the first step of those lookahead acids
```
The algorithm decides between ties by choosing to progress in a straight line, insofar as possible. Thus if the sequence is ...-A-B-C-... and B has been placed to the East of A then the algorithm will try to place C in direction E, NE, SE, NW or SW in that preference order on the hexagonal grid. Of course C can't be West of B since A is already there.

When lookahead = step = 1 this is a straightforward greedy algorithm. When step is greater than the length of the chain this is the brute force algorithm.

The time complexity of this algorithm is big-O of

```	 n * (nbrs-1)lookahead
----------------------
step
```
where ` n` is the length of the chain and ` nbrs` is the number of neighbors of a cell on the grid. For the hex, square, cubic and dodecahedral grids that number is 6, 4, 6, 12. The good news is that for fixed ` step` and ` lookahead` this is linear in ` n` . The bad news is that the constant is exponential in ` lookahead` and can be quite large. The actual exponent for the hexagonal grid seems to be about 4.4, which is less than the bound of 6-1 = 5 but not sufficiently less to make much practical difference.

(Truth in advertising. There's really a quadratic term too, but the constant there is negligible. And I could probably rewrite that part of the code to make it linear, but it's not worth the effort.)

You might try the incremental algorithm on a random chain of length 50, seed 7676, with ` lookahead 6` and ` step 3` and then again with ` lookahead 8` and ` step 4` (it takes a fair bit longer). Don't even think about folding this one with brute force.

The larger the value of lookahead the more global information about the chain can contribute to the final folded shape.

There are biological arguments for and against the appropriateness of the incremental algorithm. Some proteins do seem to fold while they are being constructed. Others can refold themselves into their proper shape even after being completely denatured - that is, straightened out.