基于java的猎人问题代码

以下是基于Java实现猎人问题的示例代码，使用A*算法求解：

import java.util.*;

public class HunterProblem {
    // 定义节点类
    static class Node {
        int x, y; // 坐标
        double g, h; // g表示从起点到当前节点的距离，h表示从当前节点到终点的估计距离
        Node parent; // 父节点

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // 定义边类
    static class Edge {
        Node start, end;
        double weight;

        public Edge(Node start, Node end, double weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    // 定义估价函数，计算从当前节点到终点的估计距离
    static double heuristic(Node current, Node end) {
        return Math.sqrt(Math.pow(current.x - end.x, 2) + Math.pow(current.y - end.y, 2));
    }

    // 定义A*算法求解最短路径
    static List<Node> aStar(Node start, Node end, List<Node> nodes, List<Edge> edges) {
        Set<Node> visited = new HashSet<>(); // 已访问节点集合
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingDouble(node -> node.g + node.h)); // 优先队列，按f = g + h排序
        Map<Node, Double> gMap = new HashMap<>(); // 从起点到每个节点的距离
        Map<Node, Node> parentMap = new HashMap<>(); // 每个节点的父节点
        queue.offer(start);
        gMap.put(start, 0.0);

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current == end) {
                // 找到终点，返回路径
                List<Node> path = new ArrayList<>();
                while (current != start) {
                    path.add(current);
                    current = current.parent;
                }
                path.add(start);
                Collections.reverse(path);
                return path;
            }
            visited.add(current);
            for (Edge edge : edges) {
                if (edge.start == current && !visited.contains(edge.end)) {
                    double newG = gMap.get(current) + edge.weight;
                    if (!gMap.containsKey(edge.end) || newG < gMap.get(edge.end)) {
                        gMap.put(edge.end, newG);
                        parentMap.put(edge.end, current);
                        edge.end.g = newG;
                        edge.end.h = heuristic(edge.end, end);
                        queue.offer(edge.end);
                    }
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        // 定义起点、终点和障碍物
        Node start = new Node(0, 0);
        Node end = new Node(9, 9);
        Node obstacle1 = new Node(3, 3);
        Node obstacle2 = new Node(4, 3);
        Node obstacle3 = new Node(5, 3);
        Node obstacle4 = new Node(6, 3);
        Node obstacle5 = new Node(3, 4);
        Node obstacle6 = new Node(4, 4);
        Node obstacle7 = new Node(5, 4);
        Node obstacle8 = new Node(6, 4);
        Node obstacle9 = new Node(3, 5);
        Node obstacle10 = new Node(4, 5);
        Node obstacle11 = new Node(5, 5);
        Node obstacle12 = new Node(6, 5);
        List<Node> nodes = Arrays.asList(start, end, obstacle1, obstacle2, obstacle3, obstacle4, obstacle5, obstacle6, obstacle7, obstacle8, obstacle9, obstacle10, obstacle11, obstacle12);
        List<Edge> edges = new ArrayList<>();
        for (Node node1 : nodes) {
            for (Node node2 : nodes) {
                if (node1 != node2) {
                    double weight = Math.sqrt(Math.pow(node1.x - node2.x, 2) + Math.pow(node1.y - node2.y, 2));
                    if (weight != 1.0) { // 距离为1的节点相邻，不需要连边
                        edges.add(new Edge(node1, node2, weight));
                    }
                }
            }
        }
        // 求解最短路径
        List<Node> path = aStar(start, end, nodes, edges);
        // 输出结果
        if (path != null) {
            for (Node node : path) {
                System.out.println("(" + node.x + ", " + node.y + ")");
            }
        } else {
            System.out.println("未找到路径！");
        }
    }
}