A *算法不能正常工作

Question

我需要一些帮助来实现我的A *算法。 当我运行该算法时，它确实找到了目标，但路径绝对不是最短路径:-P

这是我的代码，请帮助我发现错误！ 我认为这可能是重建路径，这是我的问题，但我不确定。

public class Pathfinder { 

public List<Node> aStar(Node start, Node goal, WeightedGraph graph) { 
    Node x, y; 
    int tentative_g_score; 
    boolean tentative_is_better; 

    FScoreComparator comparator = new FScoreComparator(); 
    List<Node> closedset = new ArrayList<Node>(); 
    Queue<Node> openset = new PriorityQueue<Node>(10, comparator); 
    openset.add(start); 

    start.g_score = 0; 
    start.h_score = heuristic_cost_estimate(start, goal); 
    start.f_score = start.h_score; 

    while (!openset.isEmpty()) { 
     x = openset.peek(); 

     if (x == goal) { 
      return reconstruct_path(goal); 
     } 

     x = openset.remove(); 
     closedset.add(x); 

     for (Edge e : graph.adj(x)) { 

      if (e.v == x) { 
       y = e.w; 
      } else { 
       y = e.v; 
      } 

      if (closedset.contains(y) || y.illegal) { 
       continue; 
      } 

      tentative_g_score = x.g_score + e.weight; 

      if (!openset.contains(y)) { 
       openset.add(y); 
       tentative_is_better = true; 
      } else if (tentative_g_score < y.g_score) { 
       tentative_is_better = true; 
      } else { 
       tentative_is_better = false; 
      } 

      if (tentative_is_better) { 
       y.g_score = tentative_g_score; 
       y.h_score = heuristic_cost_estimate(y, goal); 
       y.f_score = y.g_score + y.h_score; 
       y.parent = x; 
      } 

     } 

    } 

    return null; 

} 

private int heuristic_cost_estimate(Node start, Node goal) { 
    return Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y); 
} 

private List<Node> reconstruct_path(Node current_node) { 
    List<Node> result = new ArrayList<Node>(); 

    while (current_node != null) { 
     result.add(current_node); 
     current_node = current_node.parent; 
    } 

    return result; 
} 

private class FScoreComparator implements Comparator<Node> { 

    public int compare(Node n1, Node n2) { 
     if (n1.f_score < n2.f_score) { 
      return 1; 
     } else if (n1.f_score > n2.f_score) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

}

感谢大家为所有伟大的答案！ 感谢你们，我的A *算法现在可以完美工作！ :-)

这是我的第一篇文章，这个论坛真的很棒！

Answer 1

您正在改变的元素的优先级在PriorityQueue。这不受支持，因为优先级队列不知道对象已更改。你可以做的是删除并重新添加对象，当它改变。

该行的优先级更改为：y.f_score = y.g_score + y.h_score;。该行在将y添加到优先级队列后发生。请注意，仅仅在计算成本后将openset.add(y);行移动到仅仅是因为y可能已经在先前的迭代中添加了。

从代码中也不清楚您使用的启发式是admissible。如果不是，它也会导致你获得次优路径。

最后，性能注意事项：ArrayList和PriorityQueue上的contains方法需要线性运行时间，这将使您的实施的运行时间不是最优的。您可以通过向节点添加布尔属性来指示它们是处于关闭/打开集合中还是通过使用集合数据结构来改善这一点。

Answer 2

当您更改其优先级时，优先队列不更新项目的位置。 因此堆属性不成立。 更改的优先级会影响其他项目的添加/删除，但不会修复堆属性。

因此，您没有从打开中获得最佳物品 - >您找不到最短路径。

您可以： 1）写自己的堆和维护索引，它 2）添加另一个对象为PQ和标记旧为无效（必须的，而不是节点把一些物体有效标志和引用节点进入队列）。 2）性能较差，我建议不要这样做，但一些导航软件使用这种方法（或者至少几年前使用它）。

编辑：最好的做法是，插入不可变的（或至少与该装置优先imutable份）具有插入之后对象插入的PriorityQueue