`A *`노드를 프론티어에서 제거함

Question

이것은 내가 작성한 A* 알고리즘입니다. "제거 된 것이 아니라 후미가 프론티어에 추가되었을 때 목표 테스트를 수행합니다.이 절충안 최적 ". "제거되지 않을 때"라는 의미는 무엇입니까? 바로 견적 전에

def solve(problem, heuristic) : 
    """ 
    A* search algorithm finding the shortest path. 

    Returns: 
     A list of actions. 
    """ 
    s0 = problem.get_initial_state() 
    queue = PriorityQueue() 
    queue.push((0,s0,[]),0) # second 0 is priority 
    cost_so_far = dict() 
    cost_so_far[s0] = 0 

    while not queue.is_empty(): 
     current_cost, s, actions = queue.pop() 
     for successor, action, cost in problem.get_successors(s): 
      new_cost = current_cost + cost 
      if problem.goal_test(successor): 
       return actions + [action] 
      else: 
       h = heuristic(successor, problem) 
       if successor not in cost_so_far or cost_so_far[successor] > new_cost + h: 
        cost_so_far[successor] = new_cost + h 
        queue.push((new_cost, successor, actions + [action]), new_cost + h) 

수정 된 버전 (업데이트) 위키

def solve(problem, heuristic) : 
    """ 
    A* search algorithm finding the shortest path. 

    Returns: 
     A list of actions. 
    """ 
    s0 = problem.get_initial_state() 
    queue = PriorityQueue() 
    queue.push((s0,[]),0) # 0 is the priority 
    cost_so_far = {s0:0} 

    while not queue.is_empty(): 
     s, actions = queue.pop() 

     if problem.goal_test(s): 
       return actions 

     for successor, action, cost in problem.get_successors(s): 
      successor_cost = current_cost + cost 
      new_cost = successor_cost + heuristic(successor, problem) 

      if successor not in cost_so_far or cost_so_far[successor] > new_cost: 
        cost_so_far[successor] = new_cost 
        queue.push((successor, actions + [action]), new_cost) 

Answer 1

이 그래프는 다음과 같습니다 말 : 당신은 목표 노드 가능한 가장 저렴한 경로를 따라 G로 시작 노드 S에서 얻을 필요가

9 
S ----- G 
\ /
1\ /1 
    \/
    W 

. 가장자리가 비용을 한 각 웨이 포인트 W에 연결하는 동안 SG의 가장자리, 9의 비용이 2

귀하의 알고리즘은, 국경에 노드를 추가 G을 발견하고 비싼, 직접을 반환 S의 이웃을 보일 것이다

웨이 포인트 W을 통한 경로를 찾지 못한 채 즉시 SG 경로.

우선 순위 큐의 노드 pop이있을 때 노드에 대한 목표 테스트를 수행해야합니다. 이 시점에서 노드에 대한 경로가 이 아니고 노드에 대한 경로가 인 것을 확인할 수 있습니다.

Answer 2

:

여기 내 코드의 "위의 의사 코드가 발견 기능이 단순 있다고 가정합니다."

귀하의 코드는 다음 그래프와 발견에 대한 잘못된 대답을 줄 것이다 (문자 노드, 숫자 비용입니다입니다) :

Get from X to Z: 

    1 2 
X - Y - Z 
1 \ W/3 

h(X) = 2, h(Y) = 2, h(W) = 1, h(Z) = 0 

노드는 순서 X, W, Z, Y, Z 확대 될 것이다. 그러나 처음에는 Z을 찾은 후 프로그램이 종료되고 비용이 4 인 최적 경로가 아닌 경로 X>W>Z이보고됩니다.