경로 찾기에서 무한 루프

Question

을 Python에서 OpenGL을 사용하여 시뮬레이션하고 싶습니다. 나는 next_nodes을 얻기위한 코드를 작성했다. 노드가 경계를 만족시키고 다음 노드가 재귀 적으로 그렇지 않으면 돌아올 때 인쇄한다.

그러나 코드에는 무한한 실행 문제가 있습니다. 누구든지이 문제를 해결할 수 있습니까? 아래의 관련 코드를 게시하십시오 (모든 OpenGL 호출이 제거됨).

def get_node(x,y,z,side): 
    return [x+side,y,z],[x,y+side,z],[x,y,z+side],[x-side,y,z],[x,y-side,z],[x,y,z-side] 

def goto_next_nodes(x,y,z,cube_side,next_nodes,boundary_x,boundary_y,boundary_z): 
    for node in next_nodes: 
     if 0<=node[0]<=boundary_x and 0<=node[1]<=boundary_y and 0<=node[2]<=boundary_z: 
      print node 
      x,y,z=node[0],node[1],node[2] 
      next_nodes=get_node(x,y,z,cube_side) 
      goto_next_nodes(x,y,z,cube_side,next_nodes,boundary_x,boundary_y,boundary_z) 
     else: 
      return 

def display_fcc(cube_side,boundary_x,boundary_y,boundary_z): 
    x=y=z=0 
    next_nodes=get_node(x,y,z,cube_side) 
    goto_next_nodes(x,y,z,cube_side,next_nodes,boundary_x,boundary_y,boundary_z) 

display_fcc(5,10,10,10) 

재귀 goto_next_node는 재귀 함수이며, display_fcc 함수에서 시작한다.

Answer 1

본 코드와 같이 두 번째 노드는 기억하지 않아도됩니다. 하지만 하나만 더 고쳐야한다고 생각합니다.

else: 
    return 

이 올바르지 않다고 생각합니다. 더 이상 반복하지 않기 때문입니다.

def get_node(x, y, z, side): 
    return [(x+side,y,z), (x,y+side,z), (x,y,z+side), 
      (x-side,y,z), (x,y-side,z), (x,y,z-side)] 

seen_nodes = set() 

def goto_next_nodes(x, y, z, cube_side, next_nodes, boundary_x, boundary_y, boundary_z): 
    for node in next_nodes: 
     if node not in seen_nodes: 
      seen_nodes.add(node) 
      if 0<=node[0]<=boundary_x and 0<=node[1]<=boundary_y and 0<=node[2]<=boundary_z: 
       print node 
       x,y,z=node[0],node[1],node[2] 
       next_nodes=get_node(x,y,z,cube_side) 
       goto_next_nodes(x,y,z,cube_side,next_nodes,boundary_x,boundary_y,boundary_z) 
    return 

def display_fcc(cube_side,boundary_x,boundary_y,boundary_z): 
    x=y=z=0 
    next_nodes=get_node(x,y,z,cube_side) 
    goto_next_nodes(x,y,z,cube_side,next_nodes,boundary_x,boundary_y,boundary_z) 

display_fcc(5,10,10,10) 

Answer 2

next_node 함수는 (x,y,z)에서 한 걸음 떨어진 모든 노드를 반환하고 goto_next_node에서 경계 내에있는 모든 노드를 방문합니다. 그러나 노드 을 방문하면 전에 해당 노드를 방문했는지 확인하지 않습니다. 그래서 당신의 알고리즘은 구석에 달라 붙어서 반복적으로 노드 루프를 방문합니다. 출력을 보면 다음과 같이 명확하게 볼 수 있습니다.

>>> display_fcc(5,10,10,10) 
[5, 0, 0] 
[10, 0, 0] 
[5, 5, 0] 
[10, 5, 0] 
[5, 10, 0] 
[10, 10, 0] 
[5, 5, 5] 
[10, 5, 5] 
[5, 10, 5] 
[10, 10, 5] 
[5, 5, 10] 
[10, 5, 10] 
[5, 10, 10] 
[10, 10, 10] 
[0, 5, 5] 
[5, 5, 5]  # Oops: we've been here before! 
[10, 5, 5] 
[5, 10, 5] 
[10, 10, 5] 
[5, 5, 10] 
[10, 5, 10] 
[5, 10, 10] 
[10, 10, 10] 
[0, 5, 5] 
[5, 5, 5]  # And around we go again. 
... 

따라서 어디 있었는지를 추적하고 다시는 가지 않도록해야합니다.