Algorithm to find a random Hamiltonian path in a grid?

I'm looking for an efficient algorithm that is able to find an as random as possible Hamiltonian path in a bidirectional N*M grid.

Does anyone know where I can find, or how to go about constructing such an algorithm?

I've already found an efficient approach (see image below). The end开发者_StackOverflow中文版 result here is a Hamiltonian cycle. Removing a random edge will make it a Hamiltonian path. This algorithm is efficient, but does not provide enough randomness. This approach will always have the begin and end point of the path right next to each other, while I'd like to have those in random locations. Space-filling curve http://img593.imageshack.us/img593/8060/sfc.png Image taken from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type=pdf

First of all, the algorithm displayed on your image from the pdf file is not a solution to the Hamilton path problem but a solution to a maze generation as the final path has several branches.

To find algorithms for a maze generation, see: https://en.wikipedia.org/wiki/Maze_generation_algorithm

Now here is a simple algorithm to generate a Hamiltonian path on a N*M 2D grid:

1. Let a NM grid be (for instance, 45):

    O-O-O-O-O
    | | | | |
    O-O-O-O-O
    | | | | |
    O-O-O-O-O
    | | | | |
    O-O-O-O-O

2. Let's start from the East/North corner and let's create a simple zigzag to the West and to the East:

    O-O-O-O-O
    |
    O-O-O-O-O
            |
    O-O-O-O-O
    |        
    O-O-O-O-O

Now we have a Hamiltonian path.

3. Let's search two glued edges which one front of the other. They are the beginning and the end of a loop:

    O-O-O-O-O
    |        
    O-OXO-O-O
            |
    O-OXO-O-O
    |        
    O-O-O-O-O

4. Ensure that there is at least one edge inside the loop that is glued to an edge outside the loop, otherwise, go to step 3:

    O-O-O-O-O
    |        
    O-OXO-O-O
            |
    O-OXOxO-O
    |        
    O-O-OxO-O

5. Shortcut the loop:

    O-O-O-O-O
    |        
    O-O O-O-O
      | |   |
    O-O OxO-O
    |        
    O-O-OxO-O

6. Reattach the loop by the two other glued edges:

    O-O-O-O-O
    |        
    O-O O-O-O
      | |   |
    O-O O O-O
    |   | |  
    O-O-O O-O

7. If the Hamiltonian path is not randomized enough, go to step 3.

Only the start and the end will not move. To randomize the end or the start, you can replace the initial zigzag by another algorithm:

1. Choose one of the four corners
2. Search all the non-visited neighbors
3. If there is no neighbor, the map is filled, otherwise go to step 4
4. Only keep the neighbors that have a void or a visited cell on one side, left or right (in other words, the neighbors that walk along the border of the non-visited area)
5. Choose one of those neighbors, visit it and go to step 2

The result may look like that:

O-O-O-O-O
        |
O-O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

With this algorithm, the start remains on a corner but the end can be anywhere. To randomize the start AND the end, you can apply an algorithm that you can iterate as many times as you want either on the start or on the end. Let's take the start:

1. Locate the start:

|
v
O-O-O-O-O
        |
O-O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

2. Locate a neighbor that is not directly connected to the start (you will always find one in a 2D grid):

  O-O-O-O-O
          |
->O-O-O-O O
  |     | |
  O O-O O O
  |   | | |
  O-O-O O-O

3. Find from where you arrive to it from the start (respectively from the end):

O-O-O-O-O
        |
OXO-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

4. Cut this link and create a link between this point and the start:

O-O-O-O-O
|       |
O O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

The start has moved two cells. The start and the end are as on a checkerboard and they only can move on a case with the same color.

Now your path is completely randomized.

Here is the whole algorithm in Python. You can run it here: http://www.compileonline.com/execute_python3_online.php

The result is stored in an array (self.gameGrid) that is logged twice (with arrows and with nodes and lines). The first two glued edges are called a permutation and the second ones are called an intersection.

import random
import enum

class From(enum.Enum):
    NOWHERE = 1
    NORTH = 2
    EAST = 3
    SOUTH = 4
    WEST = 5

class Hamiltonian:

    def __init__(self, width: int, height: int, start: tuple = (0, 0)):
        self.arcs = {From.NORTH: (0, -1), From.SOUTH: (0, 1), From.EAST: (1, 0), From.WEST: (-1, 0)}
        self.width = width
        self.height = height
        self.start = start
        self.grid = {(i, j): self._zig_zag(i, j) for i in range(width) for j in range(height)}
        self.grid[start] = From.NOWHERE
        self.curr_loop = []

    def generate(self, count: int = 100):
        for i in range(count):
            sp = self._split_grid()
            self._modify_path(sp)
            tu = self._mend_grid(sp)
            self._modify_path(tu)

    def _modify_path(self, spl):
        pt_a, pt_b = spl
        pta, ptb = self.grid[pt_a], self.grid[pt_b]
        orientation = pta
        if orientation in [From.NORTH, From.SOUTH]:
            if pt_a[0] < pt_b[0]:
                pta, ptb = From.EAST, From.WEST
            else:
                pta, ptb = From.WEST, From.EAST
        else:
            if pt_a[1] < pt_b[1]:
                pta, ptb = From.SOUTH, From.NORTH
            else:
                pta, ptb = From.NORTH, From.SOUTH
        self.grid[pt_a] = pta
        self.grid[pt_b] = ptb

    def _move(self, pt) -> [tuple, None]:
        if pt in self.grid and self.grid[pt] != From.NOWHERE:
            (x, y), (dx, dy) = pt, self.arcs[self.grid[pt]]
            if (x + dx, y + dy) in self.grid:
                return x + dx, y + dy
        return None

    def _set_loop(self, start, stop):
        self.curr_loop = []
        point = start
        while point and len(self.curr_loop) <= len(self.grid) and point != stop and self.grid[point] != From.NOWHERE:
            point = self._move(point)
            self.curr_loop.append(point)
        return point == stop

    def _split_grid(self) -> tuple:
        candidates = []
        for pt, dx in self.grid.items():
            x, y = pt
            if dx == From.NORTH:
                cx = (x+1, y - 1)
                if cx in self.grid and self.grid[cx] == From.SOUTH:
                    candidates.append((pt, cx))
            elif dx == From.SOUTH:
                cx = (x+1, y + 1)
                if cx in self.grid and self.grid[cx] == From.NORTH:
                    candidates.append((pt, cx))
            elif dx == From.EAST:
                cx = (x + 1, y + 1)
                if cx in self.grid and self.grid[cx] == From.WEST:
                    candidates.append((pt, cx))
            elif dx == From.WEST:
                cx = (x - 1, y + 1)
                if cx in self.grid and self.grid[cx] == From.EAST:
                    candidates.append((pt, cx))
        if len(candidates) > 0:
            start, end = random.choice(candidates)
            if self._set_loop(start, end):
                return start, end
            elif not self._set_loop(end, start):
                raise Exception('Cannot split. Loop failed.')
            return end, start

    def _mend_grid(self, sp):
        candidates = []
        for pt, dx in self.grid.items():
            (x, y), lx = pt, pt in self.curr_loop
            if dx == From.NORTH:
                cx = (x+1, y - 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.SOUTH and rx != lx:
                    candidates.append((pt, cx))
            elif dx == From.SOUTH:
                cx = (x+1, y + 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.NORTH and rx != lx:
                    candidates.append((pt, cx))
            elif dx == From.EAST:
                cx = (x + 1, y + 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.WEST and rx != lx:
                    candidates.append((pt, cx))
            elif dx == From.WEST:
                cx = (x - 1, y + 1)
                rx = cx in self.curr_loop
                if cx in self.grid and self.grid[cx] == From.EAST and rx != lx:
                    candidates.append((pt, cx))
        a, b = sp
        if (a, b) in candidates:
            candidates.remove((a, b))
        elif (b, a) in candidates:
            candidates.remove((b, a))
        if len(candidates) > 0:
            return random.choice(candidates)
        else:
            return sp

    def _zig_zag(self, x: int, y: int) -> From:
        even = y % 2 == 0
        if (x == 0 and even) or (x == self.width - 1 and not even):
            return From.NORTH
        return From.WEST if even else From.EAST

    def print_path(self):
        result_str = ''
        for y in range(self.height):
            for x in range(self.width):
                if (self.grid[x, y] == From.NORTH) or ((y > 0) and (self.grid[x, y - 1] == From.SOUTH)):
                    result_str = result_str + ' |'
                else:
                    result_str = result_str + '  '
            result_str = result_str + ' \n'
            for x in range(self.width):
                if (self.grid[x, y] == From.WEST) or ((x > 0) and (self.grid[x - 1, y] == From.EAST)):
                    result_str = result_str + '-O'
                else:
                    result_str = result_str + ' O'
            result_str = result_str + ' \n'
        print(result_str)


if __name__ == '__main__':
    h = Hamiltonian(5, 5)
    h.generate(500)
    h.print_path()

This paper describes a method:

Oberdorf, R.; Ferguson, A.; Jacobsen, J.L.; Kondev, J. - Secondary Structures in Long Compact Polymers (arXiv.org)

The method roughly consists of the following: start with a zig-zag pattern (a non-random Hamiltonian path on the grid) and repeatedly apply a transformation (called "backbite") to the path. A backbite consists of adding an edge from one of the endpoints A to an adjacent vertex B other than the one A is connected to (thus creating a loop), and then remove the edge that starts in B that is not the one just added and that causes a loop (there will always be only one causing a loop other than the one just added).

The authors add some conditions to obtain rough uniformity (including an estimation on how many times to apply the backbite move). Details in the paper.

The authors also prove empirically that the probability of their method generating adjacent endpoints approximately matches the theoretical probability in uniform random Hamiltonian paths.

There is an implementation of the algorithm in JavaScript here: Hamiltonian Path Generator

Enough randomness is very general, You should have some benchmarks, most famous algorithm for eucleadian TSP has 3/2 approximation (Christofides algorithm), which uses MST (like algorithm you mentioned which is 2-approximate), and as you can see in wiki best PTAS found currently has running time depending to (n log n)^f(c,2) for c > 0 (in 2 dimentional space like your sample) with approximation of (1+1/c), and best approximation for TSP with constant factor is 3/2 - 1/500 algorithm (recently found), but all of them using logical ways, there are some random usages but it doesn't cause to leave all things to random selections. if you just want using random you can use Random Walk, It's more random but see Markove Chain for better performance and randomness.

You can start with the approach you mentioned to find a Hamiltonian path. To further randomize the solution you can start rotating edges as mentioned on the wiki. Doing this more often will make the solution more random. Rotating a random edge N*M times keeps the algorithm in the efficient realm, while making the found Hamiltonian path more random.

You Question is Wrong. You are searching for a Eulerian path. A Hamiltonian path is ALWAYS a complete cycle (-1 edge) by definition.

An Eulerian path is also not NP-hard like finding a cycle.