Java八皇后问题爬山算法死循环求助：nextState未更新

问题概述 #

实现的Java八皇后爬山算法陷入死循环，排查发现getNextState函数能更新bestHeuristic，但返回的nextState并未真正更新到更优状态，导致算法无法向启发值为0的目标推进。

错误根源分析 #

核心问题出在getNextState的状态更新逻辑上：

• 代码在尝试移动皇后时，直接在nextState数组上修改，当遇到启发值不更优的情况，会把nextState[i]改回当前状态的值，但没有保存之前找到的更优状态。
• 比如当找到某个列i的行j能让启发值降低时，仅更新了bestHeuristic，但后续循环其他行时，若启发值变差，会把nextState[i]还原，导致之前找到的更优移动被覆盖，最终返回的nextState还是初始复制的当前状态。

修复方案 #

1. 新增变量记录最优移动的列和行，而不是直接在nextState上反复修改后又还原。
2. 每次尝试移动时，基于当前状态临时生成测试状态，避免干扰后续的状态判断。
3. 循环结束后，根据记录的最优位置修改nextState，确保返回的是真正的更优状态。

修正后的完整代码 #

import java.util.Random;

public class HillClimbing {
    private static final int N = 8;
    private static final Random RANDOM = new Random();

    public static void main(String[] args) {
        int[] state = generateRandomState();
        int heuristic = getHeuristic(state);
        System.out.println("This is initial state:");
        printState(state);

        while (heuristic != 0) {
            state = getNextState(state);
            heuristic = getHeuristic(state);
        }

        printState(state);
    }

    private static int[] generateRandomState() {
        int[] state = new int[N];
        for (int i = 0; i < N; i++) {
            state[i] = RANDOM.nextInt(N);
        }
        return state;
    }

    private static int getHeuristic(int[] state) {
        int heuristic = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (state[i] == state[j] || Math.abs(state[i] - state[j]) == Math.abs(i - j)) {
                    heuristic++;
                }
            }
        }
        return heuristic;
    }

    private static int[] getNextState(int[] currentState) {
        int[] nextState = new int[N];
        // 初始化nextState为当前状态
        System.arraycopy(currentState, 0, nextState, 0, N);
        
        int currentHeuristic = getHeuristic(currentState);
        int bestHeuristic = currentHeuristic;
        // 记录最优移动的列和行
        int bestCol = -1;
        int bestRow = -1;
        boolean found = false;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (currentState[i] == j) continue;

                // 临时生成测试状态，避免修改nextState影响后续判断
                int[] testState = new int[N];
                System.arraycopy(currentState, 0, testState, 0, N);
                testState[i] = j;
                
                int nextHeuristic = getHeuristic(testState);

                if (nextHeuristic < bestHeuristic) {
                    System.out.println("heuristic after movement: "+ nextHeuristic);
                    bestHeuristic = nextHeuristic;
                    bestCol = i;
                    bestRow = j;
                    found = true;
                }
            }
        }

        if (!found) {
            // 陷入局部最优，随机重启
            System.out.println("Hit local optimum, restarting...");
            return getNextState(generateRandomState());
        }
        
        // 应用最优移动到nextState
        nextState[bestCol] = bestRow;
        
        System.out.println("The next state:");
        printState(nextState);
        return nextState;
    }

    private static void printState(int[] state) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (state[j] == i) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
    }
}

修复说明 #

• 使用System.arraycopy复制数组，避免引用传递带来的意外修改。
• 每次尝试移动时生成独立的testState，保证每次判断都是基于原始当前状态，不会互相干扰。
• 用bestCol和bestRow记录最优移动的位置，循环结束后统一修改nextState，确保返回的是真正的更优状态。
• 当陷入局部最优时，增加了提示信息，方便调试。

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