A * Алгоритм Pathfinding - поиск пути, но не оптимальный лучший путь

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, но вы направляете свой поиск до пункта назначения, совмещая функции расстояния с оценкой оставшегося расстояния.

В узле х, стоимость или "оценка" является (distance_so_far) для djikstra

в А *, то (distance_so_far + estimate_of_remaining_distance)

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

Это хорошая ссылка: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Он ссылается на эту ссылку, которая объясняет больше о эвристических функций: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html