Java a* 算法实现问题

Question

我正在尝试使用自行实现的 PQ 和 Vector 对 A* 算法进行编码。它的顶点是路口，边缘是道路。我能够正确编码 dijkstra 算法，但是我需要提高性能。

目前，我的算法中断并抛出代码中注释的空指针异常。在过去的 5 个多小时里，我一直在研究该算法，同时尝试实施它。我并不像我对 dijkstra 实现那样完全理解比较路径的方法。

这是我当前的代码：

    private Vertex dijkstra (int start, int end)
{


    Vertex current;
    while (!(pqOpen.IsEmpty()))
    {
        current = pqOpen.GetNextItem();


        else
        {               
            for (int i = 0; i < current.neighbors.GetNoOfItems(); i++)
            {                                   
                if (hold != null && hold.neighbors.GetItem(i).fromid != hold.city)
                {
                    int x = 1;                        



                if (hold2 == null || hold.getTentativeDistance() < hold2.getTentativeDistance())
                {
                    hold2.from = hold; //throws null pointer here
                    hold2.setTentativeDistance(hold.getTentativeDistance());
                    hold2.setF(hold2.getTentativeDistance() + heuristic(hold2, endLoc));  
                    System.out.println(hold2.from.city);
                }  
            }
        }   
    }
    return null;
}

  private double heuristic(Vertex goal, Vertex next)
  {        
      return Math.sqrt(Math.pow((goal.x - next.x), 2) + Math.pow((goal.y - next.y), 2));
  }

我有一种感觉，我完全误解了算法中大约一半的伪代码，但到目前为止，我还没有找到一种我可以理解的表示形式——所以有人可能会接受查看我的代码并指出我哪里做错了什么？

这是我用来参考的link网站：http://wiki.gamegardens.com/Path_Finding_Tutorial#Pseudo-code_A.2A

我也试过维基百科的，但是他们的方法更让我困惑：http://en.wikipedia.org/wiki/A*_search_algorithm

目前它确实循环了几次并存储了一些节点，但是它们是不正确的。

编辑：

我恢复了我的代码并尝试了不同的方式。我现在正在使用这些伪代码示例来理解算法。 http://web.mit.edu/eranki/www/tutorials/search/ and http://www.redblobgames.com/pathfinding/a-star/introduction.html

关于第一个，我认为我的代码在伪代码的第 13 行之前是正确的。从那时起，我对他使用的术语感到困惑 'position'.

我注释掉的 if 语句来自我的 dijkstra 算法。但是我认为我之前提到的伪代码中的 if 语句应该类似于 IF 语句。

谁能帮助我理解伪代码中与我的代码相关的第 13 行？

Answer 1

我没有看完所有的代码，但这部分明显不好:)

          if (hold2 == null)
            {
                hold2.from = hold; //throws null pointer here
            }

看到了吗？如果 hold2 为 null，则您试图将值分配给 hold2 的字段 from，在这种情况下为 null，因此它会引发异常。

Java a* 算法实现问题

Java a* algorithm implementation issue

java

algorithm

a-star

dijkstra

编辑：