所以，我有以下问题：

定x由y尺寸的网格，计算路由的数量   通过它启动的一个角落里（比方说左上）和结束   另一个（右下图），并通过每一个顶点。

Given a grid of x by y dimensions, calculate the number of routes through it that start in one corner (let's say top left) and end in another (bottom right) and pass through every vertex.

所以，我目前的方法只是蛮力迫使它通过只是想每一个可能的路径，并计算那些到达终点并遍历每个节点。虽然它的工作原理，它是为O（n ^ 2），并得到令人难以置信的慢速度非常快。我不知道怎么组合地做，因为路径遍历每个顶点的要求吧。

So my current method just brute forces it by just trying every possible path and counting the ones that reach the finish and traverse every node. While it works, it's O(n^2) and gets unbelievably slow extremely quickly. I'm not sure how to do it combinatorially because of the requirement that the path traverse every vertex.

我抬头一看更复杂的算法，并Hierholzer的算法计算欧拉路径似乎有点关系，但不是完美的，因为节点不能移动超过一次的这一点。

I've looked up more complex algorithms, and Hierholzer's algorithm for calculating Eulerian paths seems somewhat related but not perfect because nodes cannot be traversed more than once for this.

正因为如此，我的程序工作，但得厉害，我想使它更有效率。有没有更好的算法，我可以用？

As it is, my program works, but badly, and I would like to make it more efficient. Are there better algorithms I could be using?

修改谢谢你的答案为止。只是为了澄清，在2D网格的所有节点由N / E / S /的W相连接。

Edit Thanks for the answers so far. Just to clarify, all nodes in the 2d grid are connected by n/e/s/w

此外，网格不必是方

推荐答案

没有什么可以做，因为它的汉弥尔顿路径问题，这是一个NP完全问题。

There is not much you can do, because it's Hamiltonian path problem, which is NP-complete.

不过，您的可以的实际寻找别的东西，并添加一些限制的问题，你要解决...

However, you may actually search for something else and add some restrictions to the problem you are trying to solve...

由于@JanDvorak指出，您的具体限制的是，你使用的是方形网格。我的发现至今：

As @JanDvorak noted, your specific restriction is that your are using square grid. My findings so far:

如果 X 甚至，比没有办法去通过从左上角和结束的右下角开始的所有顶点。证明：

If x is even, than there is no way to go through all vertices starting from top left corner and end in bottom right. Proof:

允许计数的针对的运动沿轴，如最多是 1 ，下来就是 1 ，左边是 1 ，对 1 。因此，通过X电网的x，你的总运动是 2 * X 。在每个顶点（除了最后一个！）你正在选择仅一个方向。所以，如果有，即使你需要经过顶点的数量，你的总运动将更加反之为奇。如果 X 甚至，比有顶奇数，但总的运动甚至还是老样子=>你是不是能找到什么办法。

Lets count directed movements along axes, e.g. up is -1, down is 1, left is -1, right -1. So, having x by x grid, your total movement would be 2*x. At each vertex (except the last one!) your are selecting only one direction. So, if there is even number of vertices you need to go through, your total movement would be even and vice versa for odd. If x is even, than there is odd number of vertices, but total movement is stil even => you are not able to find any way.