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));
  }

我有一种感觉，我完全误解了算法中途的伪代码，但到目前为止我还没有找到一个可以让我理解的表示 - 所以有人可以看一下吗在我的代码中指出我做错的地方和内容？

这是我引用的网站链接:http://wiki.gamegardens.com/Path_Finding_Tutorial#Pseudo-code_A.2A

我也尝试过维基百科，但他们的方法让我更加困惑:http://en.wikipedia.org/wiki/A *_搜索_算法

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

编辑:

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

对于第一个，我认为我的代码直到伪代码的第 13 行都是正确的。从那时起，我对他使用的“位置”一词感到困惑。

我注释掉的 if 语句来 self 的 dijkstra 算法。不过我认为我之前提到的伪代码中的 if 语句应该与 IF 语句类似。

有人可以帮助我理解伪代码中与我的代码相关的第 13 行吗？

Answer 1

我没有阅读所有代码，但这部分显然很糟糕:)

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

看到了吗？如果hold2为空，则您试图将值分配给hold2的字段from，在本例中为null，因此会引发异常。