路由＆QUOT;路径＆QUOT;通过矩形阵列 [英] Routing "paths" through a rectangular array

问题描述

我试图创建我自己的实现的益智游戏。

I'm trying to create my own implementation of a puzzle game.

要创建我的游戏板，我需要遍历每平方米在我的阵列一次，只有一次。
遍历需要被链接到相邻的邻居（水平，垂直或对角线）。

To create my game board, I need to traverse each square in my array once and only once.
The traversal needs to be linked to an adjacent neighbor (horizontal, vertical or diagonal).

我使用的是一种形式的数组结构：

I'm using an array structure of the form:

board[n,m] = byte
Each bit of the byte represents a direction 0..7 and exactly 2 bits are always set
Directions are numbered clockwise
0 1 2 
7 . 3
6 5 4 
Board[0,0] must have some combination of bits 3,4,5 set

我目前的做法构建一个随机的路径是：

My current approach for constructing a random path is:

 Start at a random position
 While (Squares remain)
    if no directions from this square are valid, step backwards
    Pick random direction from those remaining in bitfield for this square       
    Erase the direction to this square from those not picked
    Move to the next square

这个算法需要的时间太长了一些中等规模的网格，因为早期的选择在考虑删除的区域。

This algorithm takes far too long on some medium sized grids, because earlier choices remove areas from consideration.

我想有一个函数，它接受一个索引到每一个可能的路径，并返回已填充该路径的数组。这将让我提供了一个种子值返回到这个特殊的电路板。

What I'd like to have is a function that takes an index into every possible path, and returns with the array filled in for that path. This would let me provide a 'seed' value to return to this particular board.

其他的建议，欢迎..

Other suggestions are welcome..

推荐答案

从本质上讲，你要构造一个的哈密尔顿路径的：即访问一个图形的每个节点恰好一次的路径

Essentially, you want to construct a Hamiltonian path: A path that visits each node of a graph exactly once.

在一般情况下，即使你只是想测试图是否包含哈密尔顿路径，这已经NP完全问题。在这种情况下，很显然，图中至少包含一个哈密顿路径，图形有一个很好的规则的结构 - 但枚举所有汉弥尔顿路径似乎仍然是一个棘手的问题。

In general, even if you only want to test whether a graph contains a Hamiltonian path, that's already NP-complete. In this case, it's obvious that the graph contains at least one Hamiltonian path, and the graph has a nice regular structure -- but enumerating all Hamiltonian paths still seems to be a difficult problem.

借助维基百科条目上的汉弥尔顿路径问题有一个随机算法寻找据称，一个哈密尔顿路径是快上的大多数图。它是从你的算法不同，它交换围绕路径，而不是只由一个节点回溯的整个分支。这更激进策略可能会更快 - 尝试一下，看看

The Wikipedia entry on the Hamiltonian path problem has a randomized algorithm for finding a Hamiltonian path that is claimed to be "fast on most graphs". It's different from your algorithm in that it swaps around a whole branch of the path instead of backtracking by just one node. This more "aggressive" strategy might be faster -- try it and see.

您可以让您的用户进入种子随机数发生器来重建某个路径。你仍然不会枚举所有可能的路径，但我想这是可能没有必要为您的应用。

You could let your users enter the seed for the random number generator to reconstruct a certain path. You still wouldn't be enumerating all possible paths, but I guess that's probably not necessary for your application.

这篇关于路由＆QUOT;路径＆QUOT;通过矩形阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！