PriorityQueue A* 算法上的 NullPointerException

Question

我尝试实现 A* 算法。我不知道为什么，但我收到此错误：

我的图表和启发式是这样的：

我在创建节点时写了启发式的值。以及 edged 的值，当一条边被创建时。

代码如下：

package com.astar.algorithm;

import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;

import java.util.List;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Collections;

public class AStar {



        public static void main(String[] args){


                Node s = new Node("S", 12);
                Node a = new Node("A", 5);
                Node b = new Node("B", 5);
                Node c = new Node("C", 5);
                Node d = new Node("D", 2);
                Node e = new Node("E", 2);
                Node f = new Node("F", 1);
                Node h = new Node("H", 1);
                Node g = new Node("G", 0);

                s.adjacencies = new Edge[]{
                        new Edge(b, 8),
                        new Edge(a, 10)
                };

                b.adjacencies = new Edge[]{
                        new Edge(d, 8),
                        new Edge(g, 16)
                };

                d.adjacencies = new Edge[]{
                        new Edge(g, 3),
                        new Edge(h, 1)
                };

                h.adjacencies = new Edge[]{
                        new Edge(f, 1)
                };

                a.adjacencies = new Edge[]{
                        new Edge(g, 10),
                        new Edge(c, 2)
                };

                c.adjacencies = new Edge[]{
                        new Edge(e, 3)
                };

                e.adjacencies = new Edge[]{
                        new Edge(g, 2)
                };

                AstarSearch(s, g);

                List<Node> path = printPath(g);

                        System.out.println("Path: " + path);


        }

        public static List<Node> printPath(Node target){
                List<Node> path = new ArrayList<Node>();

        for(Node node = target; node!=null; node = node.parent){
            path.add(node);
        }

        Collections.reverse(path);

        return path;
        }

        public static void AstarSearch(Node source, Node goal){

                Set<Node> explored = new HashSet<Node>();

                PriorityQueue<Node> queue = new PriorityQueue<Node>(8, new Comparator<Node>(){
                                 //override compare method
                 public int compare(Node i, Node j){
                    if(i.f_scores > j.f_scores){
                        return 1;
                    }

                    else if (i.f_scores < j.f_scores){
                        return -1;
                    }

                    else{
                        return 0;
                    }
                 }

                        }
                        );

                //cost from start
                source.g_scores = 0;

                queue.add(source);

                boolean found = false;

                while((!queue.isEmpty())&&(!found)){

                        //the node in having the lowest f_score value
                        Node current = queue.poll();

                        explored.add(current);

                        //goal found
                        if(current.value.equals(goal.value)){
                                found = true;
                        }

                        //check every child of current node
                        for(Edge o : current.adjacencies){
                                Node child = o.target;
                                double cost = o.cost;
                                double temp_g_scores = current.g_scores + cost;
                                double temp_f_scores = temp_g_scores + child.h_scores;


                                /*if child node has been evaluated and 
                                the newer f_score is higher, skip*/

                                if((explored.contains(child)) && (temp_f_scores >= child.f_scores)) {
                                        continue;
                                }

                                /*else if child node is not in queue or 
                                newer f_score is lower*/

                                else if((!queue.contains(child)) || (temp_f_scores < child.f_scores)){

                                        child.parent = current;
                                        child.g_scores = temp_g_scores;
                                        child.f_scores = temp_f_scores;

                                        if(queue.contains(child)){
                                                queue.remove(child);
                                        }

                                        queue.add(child);

                                }

                        }

                }

        }

}

class Node{

        public final String value;
        public double g_scores;
        public final double h_scores;
        public double f_scores = 0;
        public Edge[] adjacencies;
        public Node parent;

        public Node(String val, double hVal){
                value = val;
                h_scores = hVal;
        }

        public String toString(){
                return value;
        }

}

class Edge{
        public final double cost;
        public final Node target;

        public Edge(Node targetNode, double costVal){
                target = targetNode;
                cost = costVal;
        }
}

Answer 1

您没有为Node f和Node g初始化任何adjacencies，而是将它们设置为某些边中的目标节点。所以当你遍历 for(Edge o : current.adjacencies) 并设置你的 Node child = o.target 时，这个 child 实际上可以是 Node f 或 Node b 因为你没有初始化 adjacencies 对于那些你在 current.adjacencies 获得 NPE 的人，因为 f/g.adjacencies == null.

因此，为了防止 NPE，您还应该首先使用空 Edge 数组初始化 f 和 g 的邻接关系。

所以f/g.adjacencies = new Edge[0];至少应该解决NPE。

Answer 2

您的程序在将节点添加到队列但未将邻接设置为任何值时在节点 G 处失败。

以下代码尝试添加未分配邻接的子项：

queue.add(child);

快速解决方法是更改节点 class 并使用空数组初始化邻接关系，如下所示：

public Edge[] adjacencies = new Edge[]{};

所以节点 class 看起来像：

class Node{
        public final String value;
        public double g_scores;
        public final double h_scores;
        public double f_scores = 0;
        public Edge[] adjacencies = new Edge[]{};
        public Node parent;

        public Node(String val, double hVal){
                value = val;
                h_scores = hVal;
        }

        public String toString(){
                return value;
        }    
}

更好的解决方案是用 ArrayList 替换数组。

PriorityQueue A* 算法上的 NullPointerException

NullPointerException on PriorityQueue A* algorithm

java

algorithm

artificial-intelligence

graph-algorithm

a-star