谷歌面试题: 迷宫随机生成算法

JustYY.com 小赖子的英国生活和资讯

1 year ago

据说这个是谷歌 Google 的第一轮面试题. 一般这种题目就是: 设计一个迷宫算法 (Design a Maze). 面试中应该先问清楚需求 (Ask Clarifying Questions): 迷宫需要有几条出路? (假定至少1条), 多大的迷宫? 多复杂的迷宫等等.

最容易想到的就是随机生成1和0的地图, 其中1是墙, 0是空路, 不过这种方法生成随机的效率实在是太低, 你可以跑了半天也无法生成一个有效的迷宫, 我们假定有效的迷宫是至少含一条路径.

def maze(width, height):
    m = None
    while not check(m):
        m = generate_random_matrix(width, height)
    return m

def maze(width, height):
    m = None
    while not check(m):
        m = generate_random_matrix(width, height)
    return m

当迷宫无效的时候我们还可以随机的把一些墙变成空格, 这样在进行若干次后肯定有路径, 不过这样的迷宫不可控, 因为很有可能生成的迷宫很稀疏 (Sparse), 一点也不像迷宫.

def maze(width, height):
    m = generate_random_matrix(width, height)
    while not check(m):
       m = remove_a_random_wall(m)
    return m

def maze(width, height):
    m = generate_random_matrix(width, height)
    while not check(m):
       m = remove_a_random_wall(m)
    return m

效率比较高的一种算法是: 先随机生成一条或者几条有效路径, 然后生成若干条干扰路径, 然后再把剩下的填成墙.

在生成路径的时候我们可以从顶部(然后可以旋转或者水平垂直镜像生成其它可能)随机往下左或者右三个方向走, 并且我们需要记录走过的格子(哈希集合), 这样就不会重复走. 随机走然后直到走出界. 生成干扰路径只需要最后面随机在路么中间加堵墙(或者多个).

当然需要避免在生成干扰路径的时候加的墙也同时把我们需要的有效路径给堵死了, 只需要避免在岔口填墙就可以了.

以下是 OpenAI/ChatGPT 给出的解决方案.

Random Maze Generate Algorithm

微信公众号: 小赖子的英国生活和资讯 JustYYUK