1
我在实施爱仕达还是有些问题的做法A *算法，它看起来像代码是所有好的只是当我尝试做一些测试，它崩溃上节点不能转换为java.util.Map。 A启动实施
Exception in thread "main" java.lang.ClassCastException: AStar.Node cannot be cast to java.util.Map
at AStar.GraphAStar.addNode(GraphAStar.java:51)
at AStar.AStar.main(AStar.java:283)
它看起来像铸造并没有像它在GraphAStar类中特别说明的那样工作。
nodeIdNode.put(nodeId, (Map<T, Double>) new Node<T>(nodeId, heuristicMap.get(nodeId)));
任何想法？
我在这里添加我的代码。
Node类
public class Node <T> {
T nodeId;
Map<T, Double> heuristic;
double g; //distance to new node
double h; //distante to goal
double f; // f = g + h;
public Node(T nodeId,Map<T,Double> heuristic){
this.nodeId = nodeId;
this.g = Double.MAX_VALUE;
this.heuristic = heuristic;
}
public T getNode(){
return nodeId;
}
public double getGPath(){
return g;
}
public void setGPath(double g){
this.g = g;
}
public void CalculateF(T destination){
this.h = heuristic.get(destination);
this.f = g + h;
}
public double getH(){
return g;
}
public double getF(){
return f;
}
}
GraphAStar类
public class GraphAStar<T> implements Iterable<T> {
/***
* A map from the Node id to outgoing edge.
* An outgoing edge is represented as a Node and the length
*/
Map<T, Map<Node<T>, Double>> graph;
/***
* A map of heuristic from a node to each other node in the graph
*/
Map<T, Map<T,Double>> heuristicMap;
/***
* A map between the Node id and its data.
*/
Map<T, Map<T,Double>> nodeIdNode;
public GraphAStar(Map<T, Map<T,Double>> heuristicMap){
if(heuristicMap == null){
throw new NullPointerException("The heuristic map should not be null");
}
graph = new HashMap<T, Map<Node<T>, Double>>();
nodeIdNode = new HashMap<>();
this.heuristicMap = heuristicMap;
}
/***
* Adds a new node to the graph
* Internally it creates the Node and populate the heuristic map with node input to node data
* @param nodeId the node to be added
*/
public void addNode(T nodeId){
if(nodeId == null){
throw new NullPointerException("The node cannot be null");
}
if(!heuristicMap.containsKey(nodeId)){
throw new NoSuchElementException("This node is not part of the heuristic Map");
}
graph.put(nodeId, new HashMap<Node<T>,Double>());
nodeIdNode.put(nodeId, (Map<T, Double>) new Node<T>(nodeId, heuristicMap.get(nodeId)));
}
/***
* Adds an edge from source node to destination node
* there can only be a single edge from source to node.
* Adding additional edge would be overwrite the value.
* @param From the first node to be in the edge
* @param To the second node to be in the edge
* @param length the length of node From and To
*/
public void addEdge(T From, T To, double length){
if(From == null || To == null){
throw new NullPointerException("Either of the nodes cannot be null");
}
if(!heuristicMap.containsKey(To) || !heuristicMap.containsKey(From)){
throw new NoSuchElementException("Either of the nodes should be listed in the heuristic map");
}
if(!graph.containsKey(To) || !graph.containsKey(From)){
throw new NoSuchElementException("Either of the nodes should be part of the graph");
}
graph.get(From).put((Node<T>) nodeIdNode.get(To), length);
graph.get(To).put((Node<T>) nodeIdNode.get(From), length);
}
/***
* Returns immutable view of edges
* @param nodeId the node whose outgoing needs to be returned.
* @return An immutable view of the edges leaving that node.
*/
public Map<Node<T>,Double> edgesFrom(T nodeId){
if(nodeId == null){
throw new NullPointerException("The input node should not be null");
}
if(!heuristicMap.containsKey(nodeId)){
throw new NoSuchElementException("This node should be part of the heuristic map");
}
if(!graph.containsKey(nodeId)){
throw new NoSuchElementException("Thsi node should be null");
}
return Collections.unmodifiableMap(graph.get(nodeId));
}
/***
* the node data corresponding to the current nodeId
* @param nodeId the nodeId to be returned
* @return the node data from the node
*/
public Node<T> getNodeData(T nodeId){
if(nodeId == null){
throw new NullPointerException("The node should not be empty");
}
if(!nodeIdNode.containsKey(nodeId)){
throw new NoSuchElementException("The node does not exist");
}
return (Node<T>) nodeIdNode.get(nodeId);
}
/***
* Returns an iterator that can traverse the nodes of the graph
* @return an iterator
*/
@Override
public Iterator<T> iterator() {
return graph.keySet().iterator();
}
}
爱仕达类
public class AStar<T> {
GraphAStar<T> graph;
public AStar(GraphAStar<T> graphA){
this.graph = graphA;
}
//extends comparator
public class NodeComparator implements Comparator<Node<T>>{
public int compare(Node<T> first,Node<T> second){
if(first.getF() > second.getF()){
return 1;
}
if(second.getF() > first.getF()){
return -1;
}
return 0;
}
}
public List<T> Astar(T source, T destination){
Queue<Node<T>> openQueue = new PriorityQueue<Node<T>>(11,new NodeComparator());
Node<T> sourceNode = graph.getNodeData(source);
sourceNode.setGPath(0);
sourceNode.CalculateF(destination);
openQueue.add(sourceNode);
Map<T, T> path = new HashMap<T, T>();
Set<Node<T>> closedList = new HashSet<Node<T>>();
while(!openQueue.isEmpty()){
Node<T> node = openQueue.poll();
if(node.getNode().equals(destination)){
return path(path,destination);
}
closedList.add(node);
for(Entry<Node<T>, Double> neighborEntry : graph.edgesFrom(node.getNode()).entrySet()){
Node<T> neighbor = neighborEntry.getKey();
if(closedList.contains(neighbor)){
continue;
}
double distanceBetweenTwoNodes = neighborEntry.getValue();
double tentativeG = distanceBetweenTwoNodes + node.getGPath();
if(tentativeG < neighbor.getGPath()){
neighbor.setGPath(tentativeG);
neighbor.CalculateF(destination);
path.put(neighbor.getNode(), node.getNode());
if(!openQueue.contains(neighbor)){
openQueue.add(neighbor);
}
}
}
}
return null;
}
private List<T> path(Map<T,T> path, T destination){
assert path != null;
assert destination != null;
List<T> pathList = new ArrayList<T>();
pathList.add(destination);
while(path.containsKey(destination)){
destination = path.get(destination);
pathList.add(destination);
}
Collections.reverse(pathList);
return pathList;
}
public static void main(String[] args){
Map<String, Map<String,Double>> heuristic = new HashMap<String, Map<String,Double>>();
//distance from Node N to all
Map<String, Double> MapA = new HashMap<String,Double>();
MapA.put("A", 0.0);
MapA.put("B", 2.0);
MapA.put("C", 3.0);
MapA.put("D", 5.0);
MapA.put("E", 7.0);
MapA.put("F", 4.0);
MapA.put("G", 10.0);
MapA.put("H", 13.0);
MapA.put("I", 15.0);
Map<String, Double> MapB = new HashMap<String,Double>();
MapB.put("A", 2.0);
MapB.put("B", 0.0);
MapB.put("C", 5.0);
MapB.put("D", 3.0);
MapB.put("E", 4.0);
MapB.put("F", 6.0);
MapB.put("G", 6.0);
MapB.put("H", 10.0);
MapB.put("I", 14.0);
Map<String, Double> MapC = new HashMap<String,Double>();
MapC.put("A", 3.0);
MapC.put("B", 5.0);
MapC.put("C", 0.0);
MapC.put("D", 4.0);
MapC.put("E", 7.0);
MapC.put("F", 2.0);
MapC.put("G", 10.0);
MapC.put("H", 7.0);
MapC.put("I", 15.0);
Map<String, Double> MapD = new HashMap<String,Double>();
MapD.put("A", 5.0);
MapD.put("B", 5.0);
MapD.put("C", 4.0);
MapD.put("D", 0.0);
MapD.put("E", 3.0);
MapD.put("F", 3.0);
MapD.put("G", 7.0);
MapD.put("H", 9.0);
MapD.put("I", 11.0);
Map<String, Double> MapE = new HashMap<String,Double>();
MapE.put("A", 7.0);
MapE.put("B", 4.0);
MapE.put("C", 7.0);
MapE.put("D", 3.0);
MapE.put("E", 0.0);
MapE.put("F", 9.0);
MapE.put("G", 2.0);
MapE.put("H", 11.0);
MapE.put("I", 9.0);
Map<String, Double> MapF = new HashMap<String,Double>();
MapF.put("A", 4.0);
MapF.put("B", 6.0);
MapF.put("C", 2.0);
MapF.put("D", 3.0);
MapF.put("E", 9.0);
MapF.put("F", 0.0);
MapF.put("G", 7.0);
MapF.put("H", 3.0);
MapF.put("I", 7.0);
Map<String, Double> MapG = new HashMap<String,Double>();
MapG.put("A", 10.0);
MapG.put("B", 6.0);
MapG.put("C", 10.0);
MapG.put("D", 7.0);
MapG.put("E", 2.0);
MapG.put("F", 7.0);
MapG.put("G", 0.0);
MapG.put("H", 5.0);
MapG.put("I", 2.0);
Map<String, Double> MapH = new HashMap<String,Double>();
MapH.put("A", 13.0);
MapH.put("B", 10.0);
MapH.put("C", 7.0);
MapH.put("D", 9.0);
MapH.put("E", 11.0);
MapH.put("F", 3.0);
MapH.put("G", 5.0);
MapH.put("H", 0.0);
MapH.put("I", 4.0);
Map<String, Double> MapI = new HashMap<String,Double>();
MapI.put("A", 15.0);
MapI.put("B", 14.0);
MapI.put("C", 15.0);
MapI.put("D", 11.0);
MapI.put("E", 9.0);
MapI.put("F", 7.0);
MapI.put("G", 2.0);
MapI.put("H", 4.0);
MapI.put("I", 0.0);
heuristic.put("A", MapA);
heuristic.put("B", MapB);
heuristic.put("C", MapC);
heuristic.put("D", MapD);
heuristic.put("E", MapE);
heuristic.put("F", MapF);
heuristic.put("G", MapG);
heuristic.put("H", MapH);
heuristic.put("I", MapI);
GraphAStar<String> graph = new GraphAStar<String>(heuristic);
graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");
graph.addNode("F");
graph.addNode("G");
graph.addNode("H");
graph.addNode("I");
graph.addEdge("A", "B", 2);
graph.addEdge("A", "C", 3);
graph.addEdge("A", "D", 5);
graph.addEdge("B", "E", 4);
graph.addEdge("C", "F", 2);
graph.addEdge("D", "E", 3);
graph.addEdge("D", "F", 3);
graph.addEdge("E", "G", 2);
graph.addEdge("F", "H", 3);
graph.addEdge("G", "H", 5);
graph.addEdge("G", "I", 2);
AStar<String> aStar = new AStar<String>(graph);
for(String path : aStar.Astar("A", "I")){
System.out.println(path);
}
}
}
'Node'类没有实现'Map'接口，所以没有理由期望铸造'Node'到'Map'会工作。 – Eran