Java实现A*算法未展开节点即终止问题求助（英国路网作业）

Hey Pete, let's break down why your A* implementation is stopping before finding any expandable nodes—there are a few critical issues in the code you shared that are almost certainly causing this problem.

Key Issues in Your Current Code #

1. Starting Node Never Added to Open List #

Looking at your plan method, after verifying the origin and destination aren't null, you don't add the starting origin node to your openList. A* can't run at all if the open list starts empty—this is the most likely reason it terminates immediately with no nodes to expand.

2. Broken empty() Method #

Your empty() method has a fatal bug:

public boolean empty() {
    int lengthOfItem = 0;
    return (lengthOfItem == 0);
}

This method always returns true, no matter if your openList has nodes or not. If your algorithm uses this to check if there's work to do, it'll incorrectly think the open list is empty right out the gate.

3. Incomplete Node Existence Check #

Your code only checks if origin and destination aren't null, but it doesn't confirm these nodes actually exist in the provided RoadGraph. If the nodes aren't part of the graph, there's no path to find, and your algorithm will fail silently.

4. Missing Core A* Loop Logic #

The code snippet cuts off, but I don't see the core A* loop that drives the algorithm:

• While the open list isn't empty
• Extracting the node with the lowest f-cost (f = g + h)
• Checking if it's the destination
• Expanding its neighbors and updating open/closed lists

Without this loop, your algorithm can't traverse the graph at all.

Fixes to Get Your A* Working #

Let's walk through the critical fixes step by step:

1. Fix the empty() Method #

Update it to actually check the state of your openList (assuming OpenList has a size() method):

public boolean empty() {
    return openList.size() == 0;
}

2. Add the Starting Node to Open List #

Right after validating the origin and destination, initialize the starting node and add it to the open list to kick off the algorithm:

if (originExistence && destinationExistence && !destination.equals(origin)) {
    // Initialize starting node: g-cost = 0, h-cost = heuristic to destination
    double startHeuristic = calculateHaversineHeuristic(origin, destination); // Use a valid heuristic for UK roads
    SearchThroughNodes startNode = new SearchThroughNodes(origin, 0, startHeuristic, null);
    openList.add(startNode);
    
    // Core A* loop
    while (!empty()) {
        currentNode = openList.extractMin(); // Get node with lowest f-cost
        
        // Check if we've reached the destination
        if (currentNode.getNode().equals(destination)) {
            return reconstructPath(currentNode); // Build and return the final path
        }
        
        closedList.add(currentNode);
        
        // Expand all neighbors of the current node
        for (GraphEdge edge : graph.getEdgesFrom(currentNode.getNode())) {
            GraphNode neighbor = edge.getDestination();
            double tentativeGCost = currentNode.getGCost() + edge.getWeight();
            
            // Skip if neighbor is already in closed list with a better cost
            boolean skipNeighbor = false;
            for (SearchThroughNodes closedNode : closedList) {
                if (closedNode.getNode().equals(neighbor) && closedNode.getGCost() <= tentativeGCost) {
                    skipNeighbor = true;
                    break;
                }
            }
            if (skipNeighbor) continue;
            
            // Calculate heuristic and f-cost for the neighbor
            double neighborHeuristic = calculateHaversineHeuristic(neighbor, destination);
            double neighborFCost = tentativeGCost + neighborHeuristic;
            
            // Add to open list if not present or if this path is better
            boolean alreadyInOpen = false;
            for (SearchThroughNodes openNode : openList) {
                if (openNode.getNode().equals(neighbor) && openNode.getFCost() <= neighborFCost) {
                    alreadyInOpen = true;
                    break;
                }
            }
            if (!alreadyInOpen) {
                openList.add(new SearchThroughNodes(neighbor, tentativeGCost, neighborHeuristic, currentNode));
            }
        }
    }
}

3. Properly Validate Node Existence #

Update your existence check to confirm nodes are part of the graph (replace with your graph's actual node-check method):

originExistence = graph.contains(origin);
destinationExistence = graph.contains(destination);

4. Add Helper Methods #

You'll need two key helper functions:

• calculateHaversineHeuristic: For UK road networks, use the Haversine formula to calculate straight-line distance between nodes (this is an admissible heuristic, which ensures A* finds the shortest path).
• reconstructPath: Traverse back from the destination node using the parent references in SearchThroughNodes to build the final list of GraphEdges.

Final Note #

Make sure your OpenList is a priority queue that always returns the node with the lowest f-cost—this is non-negotiable for A* to work correctly. If your OpenList doesn't handle priority ordering, that's another potential failure point to fix.

内容的提问来源于stack exchange，提问作者Pete