路由“路径”通过矩形阵列

Question

我正在尝试创建自己的益智游戏实现。

要创建我的游戏板，我需要遍历数组中的每个方块一次且仅一次。
遍历需要链接到相邻的邻居（水平、垂直或对角线）。

我正在使用以下形式的数组结构：

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

我当前构建随机路径的方法是：

 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

该算法在某些中等大小的网格上花费的时间太长，因为早期的选择删除了考虑范围。

我想要的是一个函数，它将索引放入每个可能的路径中，并返回填充该路径的数组。这将让我提供一个“种子”值以返回到这个特定的板。

欢迎其他建议..

Answer 1

我将从穿过网格的简单路径开始，然后随机选择板上的位置（使用输入种子为随机数生成器提供种子）并在可能的情况下在路径上执行“切换”。例如：

------  to:    --\/--
------         --/\--

有了足够的开关，你应该得到一条看起来随机的路径。

Answer 2

奇怪的是，我在数学学位上花了一个本科暑假来研究这个问题，并提出解决它的算法。首先我对其他答案进行评论。

Martin B：正确地将其识别为哈密顿路径问题。但是，如果图形是规则网格（正如你们两个在评论中讨论的那样），那么可以轻松找到哈密顿路径（例如，蛇行行主顺序。）

agnorest：正确地讨论了一类哈密顿路径问题困难的问题。 agnorest 还提到了可能利用图形结构，这很有趣，但在常规网格的情况下是微不足道的。

我现在将通过详细阐述我认为您想要实现的目标来继续讨论。正如您在评论中提到的，在规则的格子/网格上找到某些类别的“空间填充”非相交“行走”是微不足道的。然而，您似乎不仅仅满足于这些，并且希望找到一种算法来找到随机覆盖您的网格的“有趣”行走。但在探讨这种可能性之前，我想指出这些路径的“不相交”属性极其重要，也是导致枚举它们的困难的原因。

事实上，我在暑期实习中研究的东西叫做自我回避行走 。令人惊讶的是，SAW（自避行走）的研究对于物理建模的一些子领域非常重要（并且是 曼哈顿项目！）您在问题中给出的算法实际上是称为“增长”算法或 Rosenbluth 算法（以 罗森布鲁斯元帅）。有关该算法的通用版本（用于估计 SAW 统计数据）及其与物理关系的更多详细信息，可以在此类文献中轻松找到 论文。

众所周知，二维声表面波很难研究。关于二维声表面波的理论结果知之甚少。奇怪的是，在高于 3 维的情况下，您可以说 SAW 的大多数特性在理论上都是已知的，例如它们的生长常数。 可以说，二维 SAW 是非常有趣的事情！

在这个讨论中谈论您手头的问题，您可能会发现您的增长算法的实现被相当“切断”频繁且无法扩展以填满整个格子。在这种情况下，将您的问题视为哈密顿路径问题更合适。我寻找有趣的哈密顿路径的方法是将问题表述为整数线性规划，并添加要在 ILP 中使用的固定随机边。随机边缘的固定将为生成过程提供随机性，并且 ILP 部分将有效地计算某些配置是否可行，如果可行则返回解决方案。

代码

以下代码实现了任意初始条件的哈密顿路径或循环问题。它在具有 4 个连通性的常规 2D 晶格上实现。该公式遵循标准子巡回消除 ILP 拉格朗日。子游览被延迟消除，这意味着可能需要多次迭代。

您可以对此进行扩展以满足随机条件或您认为对您的问题“有趣”的初始条件。如果初始条件不可行，它会提前终止并打印此内容。

此代码取决于 NetworkX 和 纸浆。

"""
Hamiltonian path formulated as ILP, solved using PuLP, adapted from 

https://projects.coin-or.org/PuLP/browser/trunk/examples/Sudoku1.py

Authors: ldog
"""

# Import PuLP modeler functions
from pulp import *

# Solve for Hamiltonian path or cycle
solve_type = 'cycle'

# Define grid size
N = 10

# If solving for path a start and end must be specified
if solve_type == 'path':
    start_vertex = (0,0)
    end_vertex = (5,5)

# Assuming 4-connectivity (up, down, left, right)
Edges = ["up", "down", "left", "right"]
Sequence = [ i for i in range(N) ]

# The Rows and Cols sequences follow this form, Vals will be which edge is used
Vals = Edges
Rows = Sequence
Cols = Sequence

# The prob variable is created to contain the problem data        
prob = LpProblem("Hamiltonian Path Problem",LpMinimize)

# The problem variables are created
choices = LpVariable.dicts("Choice",(Vals,Rows,Cols),0,1,LpInteger)

# The arbitrary objective function is added
prob += 0, "Arbitrary Objective Function"

# A constraint ensuring that exactly two edges per node are used 
# (a requirement for the solution to be a walk or path.)
for r in Rows:
    for c in Cols:
        if solve_type == 'cycle':
            prob += lpSum([choices[v][r][c] for v in Vals ]) == 2, ""
        elif solve_type == 'path':
            if (r,c) == end_vertex or (r,c) == start_vertex:
                prob += lpSum([choices[v][r][c] for v in Vals]) == 1, ""
            else:
                prob += lpSum([choices[v][r][c] for v in Vals]) == 2, ""

# A constraint ensuring that edges between adjacent nodes agree
for r in Rows:
    for c in Cols:
        #The up direction
        if r > 0:
            prob += choices["up"][r][c] == choices["down"][r-1][c],""
        #The down direction
        if r < N-1:
            prob += choices["down"][r][c] == choices["up"][r+1][c],""
        #The left direction
        if c > 0:
            prob += choices["left"][r][c] == choices["right"][r][c-1],""
        #The right direction
        if c < N-1:
            prob += choices["right"][r][c] == choices["left"][r][c+1],""

# Ensure boundaries are not used
for c in Cols:
    prob += choices["up"][0][c] == 0,""
    prob += choices["down"][N-1][c] == 0,""
for r in Rows:
    prob += choices["left"][r][0] == 0,""
    prob += choices["right"][r][N-1] == 0,""

# Random conditions can be specified to give "interesting" paths or cycles 
# that have this condition.
# In the simplest case, just specify one node with fixed edges used.
prob += choices["down"][2][2] == 1,""
prob += choices["up"][2][2] == 1,""

# Keep solving while the smallest cycle is not the whole thing
while True:
    # The problem is solved using PuLP's choice of Solver
    prob.solve()

    # The status of the solution is printed to the screen
    status = LpStatus[prob.status]
    print "Status:", status
    if status == 'Infeasible':
        print 'The set of conditions imposed are impossible to solve for. Change the conditions.'
        break

    import networkx as nx
    g = nx.Graph()
    g.add_nodes_from([i for i in range(N*N)])

    for r in Rows:
        for c in Cols:
            if value(choices['up'][r][c])  == 1:
                nr = r - 1
                nc = c
                g.add_edge(r*N+c,nr*N+nc)
            if value(choices['down'][r][c])  == 1:
                nr = r + 1
                nc = c
                g.add_edge(r*N+c,nr*N+nc)
            if value(choices['left'][r][c])  == 1:
                nr = r
                nc = c - 1
                g.add_edge(r*N+c,nr*N+nc)
            if value(choices['right'][r][c])  == 1:
                nr = r
                nc = c + 1
                g.add_edge(r*N+c,nr*N+nc)

    # Get connected components sorted by length
    cc = sorted(nx.connected_components(g), key = len)

    # For the shortest, add the remove cycle condition
    def ngb(idx,v):
        r = idx/N
        c = idx%N
        if v == 'up':
            nr = r - 1
            nc = c
        if v == 'down':
            nr = r + 1
            nc = c
        if v == 'left':
            nr = r 
            nc = c - 1
        if v == 'right':
            nr = r 
            nc = c + 1
        return nr*N+c

    prob += lpSum([choices[v][idx/N][idx%N] for v in Vals for idx in cc[0] if ngb(idx,v) in cc[0] ]) \
            <= 2*(len(cc[0]))-1,  ""

    # Pretty print the solution
    if len(cc[0]) == N*N:
        print ''
        print '***************************'
        print ' This is the final solution'
        print '***************************'
    for r in Rows:
        s = ""
        for c in Cols:
            if value(choices['up'][r][c])  == 1:
                s += " | "
            else:
                s += "   "
        print s
        s = ""
        for c in Cols:
            if value(choices['left'][r][c])  == 1:
                s += "-"
            else:
                s += " "
            s += "X"
            if value(choices['right'][r][c])  == 1:
                s += "-"
            else:
                s += " "
        print s
        s = ""
        for c in Cols:
            if value(choices['down'][r][c])  == 1:
                s += " | "
            else:
                s += "   "
        print s

    if len(cc[0]) != N*N:
        print 'Press key to continue to next iteration (which eliminates a suboptimal subtour) ...'
    elif len(cc[0]) == N*N:
        print 'Press key to terminate'
    raw_input()

    if len(cc[0]) == N*N:
        break

Answer 3

本质上，您想要构建一个 哈密尔顿路径：精确访问图的每个节点的路径一次。

一般来说，即使您只想测试图是否包含哈密顿路径，那也已经是 NP 完全的了。在这种情况下，很明显该图至少包含一条哈密顿路径，并且该图具有很好的规则结构——但是枚举所有哈密顿路径似乎仍然是一个难题。

关于哈密顿路径问题的维基百科条目有一个随机算法，用于查找声称的哈密顿路径“在大多数图表上都很快”。它与您的算法不同，因为它会交换路径的整个分支，而不是仅回溯一个节点。这种更“激进”的策略可能会更快——尝试一下看看。

您可以让用户输入随机数生成器的种子来重建特定路径。您仍然不会枚举所有可能的路径，但我想这对于您的应用程序来说可能不是必需的。

Answer 4

这最初是对 Martin B 的帖子的评论，但它增长了一点，所以我将其发布为“答案”。

首先，枚举所有可能的哈密顿路径的问题与#P复杂度类——NP的可怕哥哥非常相似。 维基百科一如既往地可以解释。正是出于这个原因，我希望您不需要真正了解每一条路径，而只是了解大多数路径。如果没有，那么，如果您可以利用图表的结构，那么仍然有希望。

（这里有一个有趣的方式来解释为什么枚举所有路径真的很困难：假设你的图表有 10 条路径，你认为你已经完成了。邪恶的老我走过来说“好吧，向我证明有不是第 11 条路径”。有一个既能说服我又不需要花时间来证明的答案 --- 这将是相当令人印象深刻的！证明不存在任何路径是 co -NP，这也很难证明只存在某个数字，这听起来很困难，所以我有点糊涂，但到目前为止我认为我所说的一切都是正确的。 ）

无论如何，我的谷歌-fu在这个问题上似乎特别弱，这令人惊讶，所以我没有一个冷酷的答案给你，但我有一些提示？

• 首先，如果每个节点最多有 2 个传出边，那么边的数量与顶点的数量成线性关系，我很确定这意味着它是一个“稀疏”图，通常更容易处理。但哈密顿路径的边数呈指数增长，因此没有真正简单的解决方法。 :)
• 其次，如果你的图的结构适合这一点，那么就有可能将问题分解成更小的块。 Min-cut 和 强连接组件浮现在脑海中。理想情况下，基本思想是发现您的大图实际上是 4 个较小的图，较小的图之间只有一些连接边。在这些较小的块上运行 HamPath 算法会快得多，并且希望能够轻松地将子图路径拼凑成整个图路径。巧合的是，这些都是很棒的绕口令。缺点是这些算法有点难以实现，并且需要大量的思考和小心才能正确使用（在 HamPath 的组合中）。此外，如果你的图表实际上是相当彻底地连接的，那么这整段都是毫无意义的！ :)

所以这些只是一些想法。如果您的图表还有任何其他方面（需要特定的起点，或特定的终点，或关于哪个节点可以连接到哪个节点的附加规则），它可能会非常有帮助！ NP 完全问题和 P（快速）算法之间的界限通常很窄。

希望这有帮助，-Agor。