What is the best algorithm for finding routes that intersect all vertices in a graph?

Question

So, I have the following problem:

Given a grid of x by y measurements, calculate the number of routes through it that start in one corner (let them say at the top left) and end with another (bottom right) and go through each vertex.

Thus, my current method just rudely makes it just try all possible paths and count those that reach the finish line and cross each node. While it works, it is O (n ^ 2) and it incredibly slowly slows down very quickly. I’m not sure how to do this combinatorially due to the fact that the path goes through each vertex.

I was looking for more complex algorithms, and the Herholzer algorithm for calculating the Eulerian paths seems somewhat connected, but not perfect, because it is impossible to traverse the nodes more than once.

Be that as it may, my program works, but it is bad, and I would like to make it more efficient. Are there any better algorithms I could use?

Edit Thanks for the answers. To clarify, all nodes in a 2d grid are connected n / e / s / w

In addition, the grid should not be square

Answer 1

Not much can be done, because the Hamilton path problem , which is NP-complete.

However, you can find something else and add some limitations to the problem you are trying to solve ...

EDIT:

As @JanDvorak noted, your specific limitation is that you use a square grid. My data so far:

If x even, then there is no way to go through all the vertices, starting from the upper left corner and ending in the lower right corner. Evidence:

Allows you to calculate directional movements along the axes, for example. up -1 , down 1 , left - -1 , right -1 . So, having an xxx grid, your total movement will be 2*x . At each vertex (except the last one!) You choose only one direction. So, if there is an even number of vertices that you need to go through, your overall movement will be even and vice versa for the weird. If x even than the odd number of vertices, but the total motion is stil even =>, you cannot find any way.

Answer 2

This semester I worked with similar issues on the topic. I think you could take a look at metaheuristic algorithms such as:

• Tabu Search
• Evolutionary computing

You may want to stay with brute force if you really do not need improvement; because they are quite complicated.

Answer 3

First, if x is even, there is a simple parity argument that shows that the answer is always zero; check the grid and note that the squares of the upper and left and lower right colors have the same color, and this color cannot be visited both first and n ² since n ² even if 1 is odd.

If x is odd, I don’t know how to count the paths, but note that the total number grows at least exponentially fast: any n * n grid walk can be raised to two different walks (n + 2) * (n + 2). You get one, going straight along the top row, left along the second row, down the first column, up the second column, and then go around the n * n grid on the remaining squares; you get the other by closing the first two rows and columns in reverse order.

This should tell you that brute force solutions are unlikely to work very well.