A * 구현이 floodfill보다 느린 이유는 무엇입니까?

난 100, 100 타일의 빈 그리드 있습니다. 시작점은 (0,0), 목표는 (99,99)입니다. 타일은 4 방향 연결입니다.A * 구현이 floodfill보다 느린 이유는 무엇입니까?

내 floodfill 알고리즘은 30ms에서 최단 경로를 찾지 만 제 A * 구현은 약 10x 느립니다.

참고 : A *는 격자 또는 레이아웃의 크기에 상관없이 내 floodfill보다 일관되게 느립니다 (3 - 10x). floodfill이 간단하기 때문에 A *에서 일종의 최적화가 누락 된 것 같습니다.

다음은이 기능입니다. 파이썬의 heapq를 사용하여 f 정렬 목록을 유지합니다. '그래프'는 모든 노드, 목표, 이웃 및 g/f 값을 유지합니다.

import heapq 

def solve_astar(graph): 

    open_q = [] 

    heapq.heappush(open_q, (0, graph.start_point)) 

    while open_q: 

     current = heapq.heappop(open_q)[1] 

     current.seen = True # Equivalent of being in a closed queue 

     for n in current.neighbours: 
      if n is graph.end_point: 
       n.parent = current 
       open_q = [] # Clearing the queue stops the process 

      # Ignore if previously seen (ie, in the closed queue) 
      if n.seen: 
       continue 

      # Ignore If n already has a parent and the parent is closer 
      if n.parent and n.parent.g <= current.g: 
       continue 

      # Set the parent, or switch parents if it already has one 
      if not n.parent: 
       n.parent = current 
      elif n.parent.g > current.g: 
       remove_from_heap(n, n.f, open_q) 
       n.parent = current 

      # Set the F score (simple, uses Manhattan) 
      set_f(n, n.parent, graph.end_point) 

      # Push it to queue, prioritised by F score 
      heapq.heappush(open_q, (n.f, n)) 

def set_f(point, parent, goal): 
    point.g += parent.g 
    h = get_manhattan(point, goal) 
    point.f = point.g + h

출처

2014-01-20 cyrus

'remove_from_heap'을 보여줄 수 있습니까? 그것은 병목 일 수 있습니다. – templatetypedef

@templatetypedef 그것은'heap.remove ((f_value, tile))'입니다 -하지만 제거가 없을 때조차도 눈에 띄게 빨리 실행되지 않습니다. – cyrus

힙 제거 작업은 선형 시간으로 실행되므로 지능형 A * 검색에서 얻을 수있는 모든 효율성을 완전히 상실 할 수 있습니다. 이게 당신 문제가 아니라고 확신합니까? – templatetypedef

타이 브레이커 문제입니다. 빈 그리드에서 (0,0)에서 시작하여 (99,99)로가는 것은 동일한 f- 점수를 가진 많은 타일을 생성합니다.

휴리스틱에 미세한 찌름을 추가하면 대상에 약간 더 가까운 타일이 먼저 선택되므로 목표에 더 빨리 도달하고 검사 할 타일을 줄일 수 있습니다.

def set_f(point, parent, goal): 
    point.g += parent.g 
    h = get_manhattan(point, goal) * 1.001 
    point.f = point.g + h

이로 인해 floodfill보다 훨씬 빠르게 100 배 향상되었습니다.

출처

2014-01-20 07:52:29 cyrus

A * 구현이 floodfill보다 느린 이유는 무엇입니까?

답변

관련 문제