3
$\begingroup$

I want to write an algorithm that takes an $n \times n$ grid and a number $L$, generate a random walk of length $L$ on the grid that doesn't visit the same cell twice.

One simple solution would be keep randomly choosing a neighbour of the last cell to add to the path. I found that for small density (i.e. $L < 0.625n^2$), I can repeat this algorithm a large amount (at least $1000$) times and can almost find some complete path without deadlock, i.e. without a a state where the path is incomplete but there is no more move available (i.e. all neighbours of the current cell is already filled). A DFS can lead to a deadlock state, and from my experiments, most of the end states are deadlocks, hence it is very hard to get to a complete state with DFS. But for larger density, it is nearly impossible to avoid deadlock no matter how many times I repeat.

My second attempt is to backtrack one step if the current $i^{th}$ step results in a deadlock (i.e. delete the last action from the list of possible actions at $(i-1)^{th}$ step and randomly choose a remaining action to retry). However it apparently took forever to finish the path (it kept going forward and backward when $i$ reaches $0.625n^2$).

Is there any suggestion for a fast algorithm that have fairly high probability of avoiding deadlocks? I'm fine with pseudo-randomness.

Improve this question
$\endgroup$
7
  • $\begingroup$ I'd expect most wasted time to be of this form: You create a loop, and then go inside the loop in which there isn't enough space to finish your path. $\endgroup$
    – xavierm02
    Mar 22 '17 at 15:16
  • 1
    $\begingroup$ To prevent this, you could maintain a partition of your grid, elements of the partition being the inside of loops (and an extra one for stuff that's outside of all loops). Then, whenever you close a loop, you split whatever area this loop was in into two. You can then either go inside the loop or outside it, but then the other part becomes unaccessible. So what you can do is compute the area in each part and only try to go in parts that have an area bigger than the remaining number of steps. $\endgroup$
    – xavierm02
    Mar 22 '17 at 15:16
  • $\begingroup$ @xavierm02 Your observation is correct. Getting inside a big loop is the main issue. Actually my original problem was to maximise a function computed on the path. I have to generate random paths to use methods such as Monte Carlo Search. Now if I try to avoid going inside loops, the function will likely not be very much maximised. $\endgroup$
    – thbl2012
    Mar 22 '17 at 16:31
  • 1
    $\begingroup$ I'm not telling you to avoid getting inside loops, in fact you may have to (imagine that you do a big loop at distance 1 from the border, then you clearly want to go inside the loop and not outside if you still need to add many steps). I'm just saying that in some cases, you can know in advance that it just isn't going to work, because even if you miraculously walked on every single square of the delimited area, your path still wouldn't be long enough. So you can, in those cases, deterministically go to one side of the wall you just created because going to the other side is bound to fail. $\endgroup$
    – xavierm02
    Mar 22 '17 at 17:04
  • $\begingroup$ Also, you may want to post your original problem because there are many ways to pick a path randomly, and the best one is going to depend on what you do with those random paths. $\endgroup$
    – xavierm02
    Mar 22 '17 at 17:06
1
$\begingroup$

You have a solid grid graph, and want to generate a random Hamiltonian path in it. The following paper describes a polynomial-time algorithm to generate such a path, randomly (from a distribution that is close to uniform):

Self-testing algorithms for self-avoiding walks. Dana Randall, Alistair Sinclair. Journal of Mathematical Physics, vol 41 no 3, pp. 1570–1584, 2000.

Be warned that the algorithm is fairly complex.

Here is a more recent paper that also proposes an algorithm to solve this problem:

Secondary Structures in Long Compact Polymers. Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen, Jane' Kondev. arxiv.org:cond-mat/0508094

On cursory inspection, it looks like it might be easier to implement.

Other related work that might possibly be of interest:

The following paper proposes an algorithm to count the number of such Hamiltonian paths:

A matrix method for counting hamiltonian cycles on grid graphs. Y. H. Harris Kwong, D. G. Rogers. European Journal of Combinatorics, vol 15 no 3, pp.277-283, 1994.

I found a reference that claims that the following paper describes

Enumeration of tours in Hamiltonian rectangular lattice graphs. Basil R. Myers. Mathematics Magazine, vol 54, no 1, Jan 1981.

Often, if you can count the number of objects of a particular type, you can sample uniformly at random from the set of such objects. So, that would be a good starting point to look, if you don't like either of the two papers mentioned above.

The following paper describes how to find a Hamiltonian path of such a solid grid graph (but with no guarantees of any particular random distribution on the output):

Hamiltonian Cycles in Solid Grid Graphs. Christopher Umans, William Lenhart. FOCS 1997.

See also https://mathoverflow.net/q/1592/37212, https://stackoverflow.com/q/7371227/781723, Hamiltonian path in grid graph.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.