Блог

У меня есть этот алгоритм, который я написал, но я действительно не знаю, можно ли преобразовать его в итеративный. Я пытаюсь получить узлы смежности для каждого узла в форме куба. Соседние узлы должны удовлетворять двум условиям:

1. Это серый узел.
2. Он находится в радиусе distance

 
def find_continumm(seed, node, row, gray, xyz, distance):
"""
seed: the nodes we want to find the adjacent nodes for. 
node: the candidate nodes to be in the adjacency.
row:  save the nodes that are adjacent. 
gray: boolean array that tells if a node is a gray or not. 
xyz: the 3 dim of the shape. 
distance: the radius
"""
    node_ravel = np.ravel_multi_index(node, xyz)
    if node_ravel in row or ~gray[node_ravel] or math.dist(node, seed) > distance:
        return
    row.add(node_ravel)
    if node[0] < xyz[0]:
        node[0] = node[0]   1
        find_continumm(seed, node, row, gray, xyz, distance)
        node[0] = node[0] - 1
    if node[0] > 0:
        node[0] = node[0] - 1
        find_continumm(seed, node, row, gray, xyz, distance)
        node[0] = node[0]   1
    if node[1] < xyz[1]:
        node[1] = node[1]   1
        find_continumm(seed, node, row, gray, xyz, distance)
        node[1] = node[1] - 1
    if node[1] > 0:
        node[1] = node[1] - 1
        find_continumm(seed, node, row, gray, xyz, distance)
        node[1] = node[1]   1
    if node[2] < xyz[2]:
        node[2] = node[2]   1
        find_continumm(seed, node, row, gray, xyz, distance)
        node[2] = node[2] - 1
    if node[2] > 0:
        node[2] = node[2] - 1
        find_continumm(seed, node, row, gray, xyz, distance)
        node[2] = node[2]   1

 

Да, всегда можно превратить рекурсивный алгоритм в итерационный алгоритм. Общая процедура для этого заключается в переключении на стиль передачи продолжения, применении отмены функций, а затем применении исключения завершающего вызова. Композиция этих трех преобразований превратит рекурсивную функцию в итеративную функцию, возможно, требующую стека.

Прежде чем я применю это к вашему коду, я кратко перепишу ваш код следующим образом:

 def find_continumm(seed, node, row, gray, xyz, distance):
    def helper():
        node_ravel = np.ravel_multi_index(node, xyz)
        if node_ravel in row or ~gray[node_ravel] or math.dist(node, seed) > distance:
            return
        row.add(node_ravel)
        for i in range(3):
            if node[i] < xyz[i]:
                node[i]  = 1
                helper()
                node[i] -= 1
            if node[i] > 0:
                node[i] -= 1
                helper()
                node[i]  = 1
    helper()
 

Вы можете сами убедиться, что это эквивалентно вашей версии кода. Я сделаю последнюю переписку, чтобы использовать a while -цикл вместо a for -цикла:

 def find_continumm(seed, node, row, gray, xyz, distance):
    def helper():
        node_ravel = np.ravel_multi_index(node, xyz)
        if node_ravel in row or ~gray[node_ravel] or math.dist(node, seed) > distance:
            return
        row.add(node_ravel)
        i = 0
        while i < 3:
            if node[i] < xyz[i]:
                node[i]  = 1
                helper()
                node[i] -= 1
            if node[i] > 0:
                node[i] -= 1
                helper()
                node[i]  = 1
            i  = 1
    helper()
 

Это значительно упрощает код и значительно упрощает его преобразование в итеративную версию.

Полученная итеративная версия является:

 beginning = 0
entering_loop = 1
finishing_first_call = 2
enter_second_if = 3
finishing_second_call = 4
increment_i = 5
# the actual values of the above variables don't matter
# so long as they're different

def find_continumm(seed, node, row, gray, xyz, distance):
    stack = []
    add_to_stack = lambda tag, data : stack.append((tag, data))
    back_to_beginning = lambda : add_to_stack(beginning, None)
    back_to_beginning()
    while stack:
        tag, i = stack.pop()
        
        if tag is beginning:
            node_ravel = np.ravel_multi_index(node, xyz)
            if node_ravel in row or ~gray[node_ravel] or math.dist(node, seed) > distance:
                pass
            else:
                row.add(node_ravel)
                add_to_stack(entering_loop, 0)
                
        elif tag is entering_loop:
            if i < 3:
                if node[i] < xyz[i]:
                    node[i]  = 1
                    add_to_stack(finishing_first_call, i)
                    back_to_beginning()
                else:
                    add_to_stack(enter_second_if, i)
                
        elif tag is finishing_first_call:
            node[i] -= 1
            add_to_stack(enter_second_if, i)
            
        elif tag is enter_second_if:
            if node[i] > 0:
                node[i]  = 1
                add_to_stack(finishing_second_call, i)
                back_to_beginning()
            else:
                add_to_stack(increment_i, i)
                
        elif tag is finishing_second_call:
            node[i] -= 1
            add_to_stack(increment_i, i)
            
        elif tag is increment_i:
            add_to_stack(entering_loop, i   1)  

 

Если вы посмотрите на итеративную версию, вы заметите, что она очень точно соответствует рекурсивной версии с while циклом -. Каждый тег соответствует определенной строке кода в этой рекурсивной версии, к которой мы «возвращаемся».