启发式搜索算法a*搜索求解8数码问题 生成Java代码 简单实现不需要窗体

以下是一个简单的Java实现a*搜索算法求解8数码问题，不需要窗体：

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

class Node {
    int[] puzzle;   // 用一维数组表示8数码问题的状态
    int cost;       // 当前的代价函数值（启发式函数值 + 已经扩展的步数）
    int steps;      // 已经扩展的步数
    Node parent;    // 父节点，用于在搜索结束后回溯得到解路径

    Node(int[] puzzle, int cost, int steps, Node parent) {
        this.puzzle = puzzle;
        this.cost = cost;
        this.steps = steps;
        this.parent = parent;
    }

    // 定义计算曼哈顿距离的方法
    int manhattan() {
        int distance = 0;
        for (int i = 0; i < 9; i++) {
            if (puzzle[i] != 0) {
                int row = Math.abs((puzzle[i] - 1) / 3 - i / 3);
                int col = Math.abs((puzzle[i] - 1) % 3 - i % 3);
                distance += (row + col);
            }
        }
        return distance;
    }

    // 判断当前状态是否为目标状态
    boolean isGoal() {
        for (int i = 0; i < 9; i++) {
            if (puzzle[i] != i) {
                return false;
            }
        }
        return true;
    }

    // 扩展当前状态，并返回扩展出的所有子节点
    Node[] expand() {
        Node[] children = new Node[4];
        int zeroIndex = 0;
        while (puzzle[zeroIndex] != 0) {
            zeroIndex++;
        }
        int row = zeroIndex / 3, col = zeroIndex % 3;
        int[][] moves = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
        };
        for (int i = 0; i < moves.length; i++) {
            int r = row + moves[i][0], c = col + moves[i][1];
            if (r >= 0 && r < 3 && c >= 0 && c < 3) {
                int newIndex = r * 3 + c;
                int[] newPuzzle = Arrays.copyOf(puzzle, 9);
                newPuzzle[zeroIndex] = newPuzzle[newIndex];
                newPuzzle[newIndex] = 0;
                Node child = new Node(newPuzzle, cost + 1 + manhattan(newPuzzle), steps + 1, this);
                children[i] = child;
            }
        }
        return children;
    }

    // 重写equals方法，用于将节点添加到HashSet中
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return Arrays.equals(puzzle, node.puzzle);
    }

    // 重写hashCode方法，用于将节点添加到HashSet中
    @Override
    public int hashCode() {
        return Arrays.hashCode(puzzle);
    }
}

public class AStarAlgorithm {
    public static void main(String[] args) {
        int[] puzzle = {2, 8, 3, 1, 6, 4, 7, 0, 5};   // 起始状态
        PriorityQueue<Node> openList = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
        HashSet<Node> closedList = new HashSet<>();
        Node start = new Node(puzzle, 0 + start.manhattan(puzzle), 0, null);   // 初始节点
        openList.add(start);
        while (!openList.isEmpty()) {
            Node current = openList.poll();
            if (current.isGoal()) {
                printPath(current);
                break;
            }
            closedList.add(current);
            Node[] children = current.expand();
            for (Node child : children) {
                if (child != null && !closedList.contains(child)) {
                    if (openList.contains(child)) {
                        Node existing = null;
                        for (Node n : openList) {
                            if (n.equals(child)) {
                                existing = n;
                                break;
                            }
                        }
                        if (existing.cost > child.cost) {
                            openList.remove(existing);
                            openList.offer(child);
                        }
                    } else {
                        openList.offer(child);
                    }
                }
            }
        }
    }

    // 回溯搜索路径
    static void printPath(Node node) {
        int steps = 0;
        while (node != null) {
            System.out.println("Step " + steps++ + ":");
            printPuzzle(node.puzzle);
            node = node.parent;
        }
    }

    // 打印8数码问题的状态
    static void printPuzzle(int[] puzzle) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(puzzle[i * 3 + j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

该实现使用了启发式搜索算法a*搜索来求解8数码问题。具体而言，它使用了曼哈顿距离作为启发函数，即每个数字与它在目标状态中位置之间的水平距离与垂直距离之和。由于每个数字移动的距离至少为1，因此该启发函数是一致的，并且可以保证找到的解路径是最短的。该算法使用了一个优先队列来维护已经生成但未扩展的节点，并按照每个节点的代价函数值进行排序。在扩展节点时，算法根据当前状态生成四个子节点，分别对应于移动空格到上下左右四个方向上的位置。算法将生成的每个子节点加入到优先队列中，并进行如下处理：如果该子节点已经在关闭列表中，直接忽略；如果该子节点已经在打开列表中，比较它的新代价函数值与已有代价函数值的大小，如果更小，则更新已有的节点；否则忽略。

这里提供的实现未包含图形用户界面或用户交互，而是直接输入初始状态，并输出找到的解路径。你可以改写该实现以添加图形用户界面或其他交互方式，以更好地展示该算法的功能。