* 길 찾기 알고리즘 - 경로를 찾지 만 최적의 최적 경로가 아님

Question

나는 A * 알고리즘을 연구 중이다. 이것은 길 찾기 메소드의 코드입니다. 참고로,이 보드는 내가 작업하고있는 보드입니다. http://i.imgur.com/xaAzNSw.png?1 각 색상 타일은 다른 휴리스틱 값을 나타냅니다. 알려지지 않은 일부 이유 때문에 매번 경로를 찾지 만 항상 정확한 경로는 아닙니다. 다음은 길 찾기 메소드의 코드입니다. 누구든지 명확한 설명이 필요한 경우이를 제공하게되어 기쁩니다.

public List<Point> findPath(Point start, Point end) { 

    //declarations and instantiations 
    List<PathState> closedList = new ArrayList<PathState>(); //the nodes already considered 
    List<PathState> openList = new ArrayList<PathState>();  //nodes to be considered 
    openList.add(new PathState(start, end, tm));    //add starting point 
    PathState current = openList.get(0); 

    while(!current.isGoal()){ 
     //sort open list to find the pathstate with the best hscore(sorts by hscore) 
     Collections.sort(openList); 
     current = openList.get(openList.size() - 1); 
     closedList.add(current); 
     openList.remove(current); 

     //get the valid children of current node 
     List<PathState> children = current.getChildren();; 

     if(!current.isGoal()){    
      for(int i = 0; i < children.size(); i++){ 
       if(!closedList.contains(children.get(i))){ 
        if(openList.contains(children.get(i))){ 
         if(openList.get(openList.indexOf(children.get(i))).getgScore() > children.get(i).getgScore()){ 
          //child is already on the open list, but this node has lower g value 
          //change g value and parent of node on open list 
          openList.get(openList.indexOf(children.get(i))).setG(children.get(i).getgScore()); 
          openList.get(openList.indexOf(children.get(i))).changeParent(current); 
        } 
        }else{ 
         //child not in closed list 
         openList.add(children.get(i)); 

         //repaint the terrain panel with shades 
         tp.addAstarState(children.get(i)); 
         tp.repaint(); 
         try { 
          Thread.sleep(25); 
         } catch(Exception e) { 
          e.printStackTrace(); 
         } 
        } 
       } 
      } 
     } 
    } 
    //returns the path from winning node to start for output 
    return current.getPath(); 
} 

Answer 1

A *는 기본적으로 Djikstra의 알고리즘이지만 거리 함수와 남은 거리를 결합하여 검색을 목적지로 지정합니다. 노드 X에서

는, 비용 또는 "점수"(distance_so_far) A *에서 djikstra

을 위해, 그것은이다 (distance_so_far + estimate_of_remaining_distance)

A * 발견 있는지 확인하려면 이 가장 짧습니다. 경로 인 경우 estimate_of_remaining_distance은 실제 하한값이어야합니다. 즉, 항상은 실제 남은 거리보다 작아야합니다. 즉,이 거리를 과대 평가하지 않아야합니다. 그렇지 않으면 정확하지 않은 경험적 방법이되어 최단 경로를 찾지 못할 수도 있습니다.

이 좋은 참조가 : http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

그것은 발견 적 기능에 대한 자세한 설명이 참조에 대한 링크 : http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html