Self-avoiding walk

A self-avoiding walk (SAW) is a sequence of moves on a lattice which does not visit the same point more than once. A self-avoiding polygon (SAP) is a closed () self-avoiding walk on a lattice.

As such, SAWs are often used to model the real-life behaviour of chain-like entities such as solvents and polymers, whose physical volume prohibits multiple occupation of the same spatial point.

In computational physics a self-avoiding walk is a chain-like path in ℝ² or ℝ³ with a certain number of nodes, typically a fixed step length and has the imperative property that it doesn't cross itself or another walk. A system of self-avoiding walks satisfies the so called excluded volume condition.

A self-avoiding walk is interesting for simulations because its properties cannot be calculated analytically, thus it is very helpful to understand polymers, e.g. DNA molecules.

SAWs SAPs play a central role in the modelling of the topological and knot-theoretic behaviour of thread- and loop-like molecules such as proteins.

Calculating the number of self-avoiding walks in any given lattice is a common computational problem. There is currently no known formula for determining the number of self-avoiding walks, although there are rigorous methods for approximating them. [cite journal |author=Hayes B |title=How to Avoid Yourself |journal=American Scientist |volume=86 |issue=4 |pages= |month=Jul-Aug |year=1998 |url=http://www.americanscientist.org/issues/pub/how-to-avoid-yourself/] [cite journal |author=Liśkiewicz M, Ogihara M, Toda S |title=The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes |journal=Theoretical Computer Science |volume=304, |issue=1-3 |pages=129–56 |month=Jul |year=2003 |doi=10.1016/S0304-3975(03)00080-X |url=http://linkinghub.elsevier.com/retrieve/pii/S030439750300080X]

Further reading

# cite book
last = Madras | first = N.
coauthors = Slade, G.
year = 1996
title = The Self-Avoiding Walk
publisher = Birkhäuser
id = ISBN 978-0817638917
# cite book
last = Lawler | first = G. F.
year = 1991
title = Intersections of Random Walks
publisher = Birkhäuser
id = ISBN 978-0817638924

References

External links

*MathWorld|urlname=Self-AvoidingWalk|title=Self-Avoiding Walk