10

一个多星期以来，我一直在努力寻找解决问题的方法，但我找不到比一百万次迭代 prog 更好的方法，所以我认为是时候请人帮助我了。

我有一个 3D 数组。比方说，我们谈论的是地面，第一层是表面。另一层是地下的地板。我必须找到最深的路径长度、地下孤立洞穴的数量以及最大洞穴的大小。

这是我的问题的可视化。

Input:
5 5 5 // x, y, z
xxxxx
oxxxx
xxxxx
xoxxo
ooxxx

xxxxx
xxoxx

and so...


Output:
5 // deepest path - starting from the surface
22 // size of the biggest cave
3 // number of izolated caves (red ones) (izolated - cave that doesn't reach the surface)

请注意，即使 2 楼的红色单元格位于绿​​色单元格旁边，它也不是同一个洞穴，因为它是对角放置的，这不算数。有人告诉我，最好的方法是使用递归算法“分而治之”，但我真的不知道它会是什么样子。

4

4 回答 4

4

我认为你应该能够在 O(N) 中做到这一点。解析输入时，为每个节点分配一个初始化为 0 的“caveNumber”。每当您访问洞穴时，将其设置为有效数字：

CaveCount = 0, IsolatedCaveCount=0
AllSizes = new Vector.
For each node, 
   ProcessNode(size:0,depth:0);

ProcessNode(size,depth):
   If node.isCave and !node.caveNumber 
       if (size==0) ++CaveCount
       if (size==0 and depth!=0) IsolatedCaveCount++
       node.caveNumber = CaveCount
       AllSizes[CaveCount]++
       For each neighbor of node, 
            if (goingDeeper) depth++
            ProcessNode(size+1, depth).

在最坏的情况下，您将访问每个节点 7 次：一次来自外部循环，并且可能来自其六个邻居中的每一个。但是你只会对每一个工作一次，因为在那之后就设置了caveNumber，然后你就忽略了它。

您可以通过在递归 ProcessNode 调用中添加深度参数来进行深度跟踪，并且仅在访问较低的邻居时才增加它。

于 2012-10-19T16:27:46.103 回答
2

下面显示的解决方案（作为 python 程序）在 time 中运行O(n lg*(n))，其中lg*(n)几乎恒定的迭代日志函数通常与不相交集森林中的联合操作相关联。

在第一次遍历所有单元格时，程序使用名为makeset(), findset(), link(),and的例程创建一个不相交集森林，union()正如 Cormen/Leiserson/Rivest 第一版第 22.3 节（不相交集森林）中所解释的那样。在以后通过单元格时，它会计算每个不相交森林的成员数量，检查深度等。第一次通过及时运行O(n lg*(n))，随后通过及时运行，O(n)但通过简单的程序更改，一些通过可以运行O(c)或O(b)运行c 个洞穴，总共有 b 个细胞。

请注意，下面显示的代码不受上一个答案中包含的错误的影响，其中上一个答案的伪代码包含该行
if (size==0 and depth!=0) IsolatedCaveCount++
该行中的错误是与地表相连的洞穴可能有地下上升分支，这另一个答案会错误地添加到其孤立洞穴的总数中。

下面显示的代码产生以下输出：（
Deepest: 5 Largest: 22 Isolated: 3
请注意，图中显示的 24 的计数应该是 22，从 4+9+9。）

v=[0b0000010000000000100111000,   # Cave map
   0b0000000100000110001100000,
   0b0000000000000001100111000,
   0b0000000000111001110111100,
   0b0000100000111001110111101]
nx, ny, nz = 5, 5, 5
inlay, ncells = (nx+1) * ny,  (nx+1) * ny * nz
masks = []
for r in range(ny):
    masks += [2**j for j in range(nx*ny)][nx*r:nx*r+nx] + [0]
p = [-1 for i in range(ncells)]  # parent links
r = [ 0 for i in range(ncells)]  # rank
c = [ 0 for i in range(ncells)]  # forest-size counts
d = [-1 for i in range(ncells)]  # depths

def makeset(x): # Ref: CLR 22.3, Disjoint-set forests
    p[x] = x
    r[x] = 0
def findset(x):
    if x != p[x]:
        p[x] = findset(p[x])
    return p[x]
def link(x,y):
    if r[x] > r[y]:
        p[y] = x
    else:
        p[x] = y
        if r[x] == r[y]:
            r[y] += 1
def union(x,y):
    link(findset(x), findset(y))

fa = 0                          # fa = floor above
bc = 0                          # bc = floor's base cell #
for f in v:                     # f = current-floor map
    cn = bc-1                   # cn = cell#
    ml = 0
    for m in masks:
        cn += 1
        if m & f:
            makeset(cn)
            if ml & f:
                union(cn, cn-1)
            mr = m>>nx
            if mr and mr & f:
                union(cn, cn-nx-1)
            if m & fa:
                union(cn, cn-inlay)
        ml = m
    bc += inlay
    fa = f

for i in range(inlay):
    findset(i)
    if p[i] > -1:
        d[p[i]] = 0
for i in range(ncells):
    if p[i] > -1:
        c[findset(i)] += 1
        if d[p[i]] > -1:
            d[p[i]] = max(d[p[i]], i//inlay)
isola = len([i for i in range(ncells) if c[i] > 0 and d[p[i]] < 0])
print "Deepest:", 1+max(d), "  Largest:", max(c), "  Isolated:", isola
于 2012-10-19T20:45:50.597 回答
2

听起来您正在解决“连接组件”问题。如果您的 3D 数组可以转换为位数组（例如 0 = 基岩，1 = 洞穴，反之亦然），那么您可以应用图像处理中使用的技术来查找前景或背景的数量和尺寸。

通常，此算法应用于 2D 图像以查找相同颜色的“连接组件”或“斑点”。如果可能，找一个“单程”算法：

http://en.wikipedia.org/wiki/Connected-component_labeling

相同的技术可以应用于 3D 数据。谷歌搜索“连接的组件 3D”将产生如下链接：

http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/pmwiki.php/Research/ConnectedComponents

一旦算法处理完您的 3D 阵列，您将拥有一个标记的、连接区域的列表，并且每个区域将是一个体素列表（类似于图像像素的体积元素）。然后，您可以分析每个标记区域以确定体积、与表面的接近程度、高度等。

实现这些算法可能有点棘手，您可能想先尝试 2D 实现。认为它可能没有您喜欢的那么高效，您可以通过对每一层迭代地应用 2D 算法然后将连接区域从顶层重新标记到底层来创建 3D 连接组件标记算法：

  1. 对于第 0 层，使用 2D 连通分量算法查找所有连通区域
  2. 对于第 1 层，找到所有连接区域。
  3. 如果第 0 层中的任何标记像素直接位于第 1 层中的标记像素之上，则将第 1 层中的所有标签更改为第 0 层中的标签。
  4. 在堆栈中迭代地应用这种标记技术，直到到达第 N 层。

连接组件标记的一个重要考虑因素是如何考虑要连接的区域。在位的 2D 图像（或 2D 数组）中，我们可以考虑相邻元素的“4 连通”区域

X 1 X
1 C 1
X 1 X

其中“C”是中心元素，“1”表示将被视为连接的邻居，“X”是我们认为不连接的相邻邻居。另一种选择是考虑“8 连接邻居”：

1 1 1
1 C 1
1 1 1

也就是说，与中心像素相邻的每个元素都被认为是连接的。起初，这听起来像是更好的选择。在现实世界的 2D 图像数据中，噪声棋盘图案或单个噪声像素的对角线串将被检测为连通区域，因此我们通常测试 4 连通性。

对于 3D 数据，您可以考虑 6 连接或 26 连接：6 连接仅考虑与中心体素共享完整立方体面的相邻像素，而 26 连接考虑中心体素周围的每个相邻像素。您提到“对角线放置”不算数，因此 6 连接就足够了。

于 2012-10-21T15:22:06.383 回答
1

您可以将其观察为一个图形，其中（非对角线）相邻元素如果都为空（洞穴的一部分）则它们是连接的。请注意，您不必将其转换为图形，您可以使用普通的 3d 数组表示。

寻找洞穴与在图中寻找连接的组件(O(N))的任务相同，洞穴的大小是该组件的节点数。

于 2012-10-19T16:27:22.540 回答