算法找到在网格中随机汉弥尔顿路径？ [英] Algorithm to find a random Hamiltonian path in a grid?

问题描述

我在寻找一个有效的算法，它能够找到一个尽可能的随机哈密尔顿路径的一个双向N * M网格。

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?

我已经找到了一个有效的方法（见下图）。这里的最终结果是一个汉密尔顿的周期。删除随机优势将使其成为哈密尔顿路径。这个算法是有效的，但没有提供足够的随机性。这种做法总会有路径的开始和结束点紧挨着对方，而我想有那些在随机位置。 图片摘自<一个href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type=pdf

I've already found an efficient approach (see image below). The end 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. Image taken from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type=pdf

推荐答案

您可以与您提及找到一个汉弥尔顿路径的方式开始。为了进一步随机化解决方案，您可以开始旋转边提到的<一个href="http://stackoverflow.com/questions/1987183/randomized-algorithm-for-finding-hamiltonian-path-in-a-directed-graph">wiki.这更经常这样做将会使解决方案更加随意。旋转的无规边缘N * M次保持的算法中的高效的领域，同时使发现汉弥尔顿路径更随机。

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.

这篇关于算法找到在网格中随机汉弥尔顿路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！