Какой самый быстрый способ найти самый глубокий путь в трехмерном массиве?

Ответ 1

Думаю, вы сможете сделать это в O (N). Когда вы анализируете свой ввод, назначьте каждый node a 'caveNumber' инициализирован равным 0. Установите его в действительное число всякий раз, когда вы посещаете пещеру:

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).

Вы будете посещать каждый node 7 раз в худшем случае: один раз из внешнего цикла и, возможно, один раз от каждого из своих шести соседей. Но вы будете работать только с каждым из них, так как после этого будет установлен caveNumber, и вы проигнорируете его.

Вы можете выполнить отслеживание глубины, добавив параметр глубины в рекурсивный вызов ProcessNode и увеличивая его только при посещении младшего соседа.

Ответ 2

Решение, показанное ниже (как программа python), запускается со временем O(n lg*(n)), где lg*(n) - это почти постоянная функция повторного логарифма, часто связанная с операциями объединения в лесах с непересекающимися множествами.

В первом проходе через все ячейки программа создает лес с непересекающимся множеством, используя подпрограммы, называемые makeset(), findset(), link(), и union(), как описано в разделе 22.3 (леса с разнесенными наборами) издания 1 Cormen/Leiserson/Ривест. В более поздних проходах через ячейки он подсчитывает количество членов каждого непересекающегося леса, проверяет глубину и т.д. Первый проход выполняется во времени 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 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

Ответ 3

Вы можете наблюдать это как график, где (недиагональные) смежные элементы связаны, если они оба пустые (часть пещеры). Обратите внимание, что вам не нужно преобразовывать его в график, вы можете использовать нормальное представление 3d-массива.

Поиск пещер - это та же задача, что и поиск подключенных компонентов на графике (O (N)), а размер пещеры - это количество узлов этого компонента.

Ответ 4

Похоже, вы решаете проблему с "связанными компонентами". Если ваш 3D-массив можно преобразовать в бит-массив (например, 0 = коренной корень, 1 = пещера или наоборот), вы можете применить технику, используемую при обработке изображений, чтобы найти число и размеры либо переднего плана, либо фона.

Обычно этот алгоритм применяется в 2D-изображениях, чтобы найти "подключенные компоненты" или "капли" одного цвета. Если возможно, найдите алгоритм "одного прохода":

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

Та же самая техника может быть применена к 3D-данным. Googling "подключенные компоненты 3D" приведут к ссылкам вроде этого:

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

Как только алгоритм завершит обработку вашего 3D-массива, вы получите список помеченных, связанных областей, и каждый регион будет списком вокселей (элементов тома, аналогичных пикселям изображения). Затем вы можете проанализировать каждую помеченную область, чтобы определить объем, близость к поверхности, высоту и т.д.

Реализация этих алгоритмов может быть немного сложной, и вы можете сначала попробовать выполнить 2D-реализацию. Думал, что это может быть не так эффективно, как вам нравится, вы можете создать алгоритм маркировки трехмерных подключаемых компонентов, применяя 2D-алгоритм итеративно к каждому слою, а затем перевязывая связанные области от верхнего слоя к нижнему слою:

• Для слоя 0 найдите все подключенные области, используя алгоритм 2D-подключенного компонента
• Для слоя 1 найдите все связанные области.
• Если какой-либо помеченный пиксель в слое 0 находится непосредственно над помеченным пикселем в слое 1, измените все метки в слое 1 на метку в слое 0.
• Примените эту технологию меток итеративно через стек, пока не достигнете слоя 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-соединение.

Для трехмерных данных вы можете рассматривать либо 6-соединение, либо 26-соединение: 6-подключение рассматривает только соседние пиксели, которые разделяют полную поверхность куба с центром воксела, а 26-подключение рассматривает каждый соседний пиксель вокруг центра вокселя. Вы отмечаете, что "по диагонали" не учитывается, поэтому достаточно 6-соединений.