引言
华容道是中国传统益智游戏，玩家需要在有限的空间中移动方块，将目标棋子（曹操）移至出口。其状态空间极其庞大，传统BFS或A*搜索在复杂局面下容易因状态爆炸而效率低下。本文将遗传算法（Genetic Algorithm）引入华容道求解，通过染色体编码、交叉变异与适应度选择，让种群在进化中自动发现最优解路径。
算法核心思想
遗传算法模拟生物进化过程：
- 染色体编码：将华容道的每一步移动编码为基因序列
- 初始种群：随机生成多组可行移动序列
- 适应度评估：根据曹操到出口的距离、移动步数、死锁惩罚综合评分
- 选择：优胜劣汰，保留高适应度个体
- 交叉：两条染色体交换片段，组合优良移动模式
- 变异：随机改变某些基因（移动方向），维持种群多样性
- 精英保留：每代最优个体直接进入下一代，防止优秀基因丢失
核心数据结构
import java.util.*;
/**
* 华容道遗传算法求解器
* 采用经典布局：4×5网格，曹操为2×2，五虎将各1×2或2×1，四个1×1小兵
*/
public class GeneticAlgorithmKlondike {
// 棋盘尺寸
private static final int ROWS = 5;
private static final int COLS = 4;
// 棋子类型
private static final int EMPTY = 0;
private static final int CAOCAO = 1; // 曹操 2×2
private static final int GENERAL = 2; // 将领 1×2 或 2×1
private static final int SOLDIER = 3; // 小兵 1×1
// 移动方向编码：0=上,1=下,2=左,3=右
private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
private static final String[] DIR_NAMES = {"上","下","左","右"};
private final Random random;
// 遗传算法参数
private final int populationSize; // 种群大小
private final int maxGenerations; // 最大迭代代数
private final double crossoverRate; // 交叉概率
private final double mutationRate; // 变异概率
private final int chromosomeLength; // 染色体长度（最大移动步数）
public GeneticAlgorithmKlondike() {
this.random = new Random();
this.populationSize = 200;
this.maxGenerations = 5000;
this.crossoverRate = 0.8;
this.mutationRate = 0.15;
this.chromosomeLength = 150; // 预估足够长的移动序列
}
/**
* 华容道局面状态
*/
static class BoardState {
// board[r][c] 存储该位置 occupiedBy 的棋子ID，0表示空
int[][] board;
// 每个棋子的位置和尺寸: [id] -> {row, col, height, width}
Map<Integer, int[]> pieces;
BoardState() {
board = new int[ROWS][COLS];
pieces = new HashMap<>();
}
BoardState deepCopy() {
BoardState copy = new BoardState();
for (int r = 0; r < ROWS; r++) {
copy.board[r] = board[r].clone();
}
for (Map.Entry<Integer, int[]> e : pieces.entrySet()) {
copy.pieces.put(e.getKey(), e.getValue().clone());
}
return copy;
}
}
/**
* 染色体：编码一条移动序列
* genes[i] = {pieceId, direction}
*/
static class Chromosome {
int[][] genes; // [步数][0=棋子ID, 1=方向]
double fitness;
int validSteps; // 实际有效步数（遇到死锁前的步数）
Chromosome(int length) {
genes = new int[length][2];
fitness = 0;
validSteps = 0;
}
}
初始化经典华容道布局
/**
* 创建经典"横刀立马"初始布局
*/
private BoardState createInitialBoard() {
BoardState state = new BoardState();
// 曹操 2×2 位于 (0,1)
placePiece(state, 1, CAOCAO, 0, 1, 2, 2);
// 关羽 1×2 横刀 位于 (2,1)
placePiece(state, 2, GENERAL, 2, 1, 1, 2);
// 张飞 2×1 位于 (0,0)
placePiece(state, 3, GENERAL, 0, 0, 2, 1);
// 赵云 2×1 位于 (0,3)
placePiece(state, 4, GENERAL, 0, 3, 2, 1);
// 马超 2×1 位于 (2,0)
placePiece(state, 5, GENERAL, 2, 0, 2, 1);
// 黄忠 2×1 位于 (2,2)
placePiece(state, 6, GENERAL, 2, 2, 2, 1);
// 四个小兵
placePiece(state, 7, SOLDIER, 2, 1, 1, 1); // 注意与关羽位置协调
placePiece(state, 8, SOLDIER, 4, 0, 1, 1);
placePiece(state, 9, SOLDIER, 4, 1, 1, 1);
placePiece(state, 10, SOLDIER, 4, 2, 1, 1);
// 重新调整小兵以匹配经典布局
// 经典布局：
// 张 曹 曹 赵
// 张 曹 曹 赵
// 马 关 关 黄
// 马 兵 兵 黄
// 兵 兵
state = new BoardState();
placePiece(state, 1, CAOCAO, 0, 1, 2, 2);
placePiece(state, 2, GENERAL, 2, 1, 1, 2); // 关羽横
placePiece(state, 3, GENERAL, 0, 0, 2, 1); // 张飞竖
placePiece(state, 4, GENERAL, 0, 3, 2, 1); // 赵云竖
placePiece(state, 5, GENERAL, 2, 0, 2, 1); // 马超竖
placePiece(state, 6, GENERAL, 2, 3, 2, 1); // 黄忠竖
placePiece(state, 7, SOLDIER, 3, 1, 1, 1);
placePiece(state, 8, SOLDIER, 3, 2, 1, 1);
placePiece(state, 9, SOLDIER, 4, 0, 1, 1);
placePiece(state, 10, SOLDIER, 4, 3, 1, 1);
return state;
}
private void placePiece(BoardState state, int id, int type, int r, int c, int h, int w) {
state.pieces.put(id, new int[]{r, c, h, w});
for (int i = r; i < r + h; i++) {
for (int j = c; j < c + w; j++) {
state.board[i][j] = id;
}
}
}
移动操作与合法性判断
/**
* 尝试移动指定棋子到指定方向
* @return 移动后的新状态，若非法则返回null
*/
private BoardState tryMove(BoardState state, int pieceId, int dir) {
int[] piece = state.pieces.get(pieceId);
if (piece == null) return null;
int nr = piece[0] + DIRS[dir][0];
int nc = piece[1] + DIRS[dir][1];
int h = piece[2];
int w = piece[3];
// 边界检查
if (nr < 0 || nr + h > ROWS || nc < 0 || nc + w > COLS) return null;
// 目标位置必须全部为空或为自己
for (int i = nr; i < nr + h; i++) {
for (int j = nc; j < nc + w; j++) {
if (state.board[i][j] != 0 && state.board[i][j] != pieceId) {
return null; // 与其他棋子冲突
}
}
}
// 执行移动
BoardState newState = state.deepCopy();
// 清空原位置
for (int i = piece[0]; i < piece[0] + h; i++) {
for (int j = piece[1]; j < piece[1] + w; j++) {
newState.board[i][j] = 0;
}
}
// 填充新位置
for (int i = nr; i < nr + h; i++) {
for (int j = nc; j < nc + w; j++) {
newState.board[i][j] = pieceId;
}
}
newState.pieces.put(pieceId, new int[]{nr, nc, h, w});
return newState;
}
/**
* 检查曹操是否到达出口
* 出口在底部中央 (3,1) 到 (3,2) 下方
*/
private boolean isGoal(BoardState state) {
int[] caocao = state.pieces.get(1);
return caocao[0] == 3 && caocao[1] == 1; // 曹操底部到达第4行
}
适应度函数设计
/**
* 评估染色体适应度
* 综合考虑：曹操到出口距离、移动步数、死锁惩罚、通路顺畅度
*/
private void evaluateFitness(Chromosome chrom, BoardState initial) {
BoardState current = initial.deepCopy();
int steps = 0;
Set<String> visited = new HashSet<>();
visited.add(boardToString(current));
for (int i = 0; i < chrom.genes.length; i++) {
int pieceId = chrom.genes[i][0];
int dir = chrom.genes[i][1];
BoardState next = tryMove(current, pieceId, dir);
if (next == null) {
// 非法移动，停止模拟
chrom.validSteps = steps;
break;
}
String stateStr = boardToString(next);
if (visited.contains(stateStr)) {
// 循环状态，轻微惩罚但继续
chrom.fitness -= 0.5;
}
visited.add(stateStr);
current = next;
steps++;
chrom.validSteps = steps;
if (isGoal(current)) {
// 到达目标！极大奖励
chrom.fitness = 1000.0 - steps * 0.5;
return;
}
}
// 未到达目标，基于曹操位置评分
int[] caocao = current.pieces.get(1);
// 曹操到出口的距离（出口在底部中央）
double distToGoal = Math.abs(caocao[0] - 3) + Math.abs(caocao[1] - 1);
// 下方通路评估：曹操正下方是否有足够空间
double pathClearance = evaluatePathClearance(current);
// 综合适应度：距离越近、通路越顺畅，分数越高
chrom.fitness = 50.0 - distToGoal * 5.0 + pathClearance * 10.0 - steps * 0.1;
}
/**
* 评估曹操到出口的通路顺畅度
*/
private double evaluatePathClearance(BoardState state) {
int[] caocao = state.pieces.get(1);
// 检查曹操正下方两行两列是否畅通
int clearCount = 0;
for (int r = caocao[0] + caocao[2]; r < ROWS; r++) {
for (int c = caocao[1]; c < caocao[1] + caocao[3]; c++) {
if (r < ROWS && c < COLS && state.board[r][c] == 0) {
clearCount++;
}
}
}
return clearCount / 4.0; // 最大为1.0
}
private String boardToString(BoardState state) {
StringBuilder sb = new StringBuilder();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
sb.append(state.board[r][c]).append(',');
}
}
return sb.toString();
}
遗传操作：选择、交叉与变异
/**
* 初始化随机种群
*/
private List<Chromosome> initPopulation() {
List<Chromosome> pop = new ArrayList<>();
List<Integer> pieceIds = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));
for (int i = 0; i < populationSize; i++) {
Chromosome chrom = new Chromosome(chromosomeLength);
for (int j = 0; j < chromosomeLength; j++) {
chrom.genes[j][0] = pieceIds.get(random.nextInt(pieceIds.size()));
chrom.genes[j][1] = random.nextInt(4);
}
pop.add(chrom);
}
return pop;
}
/**
* 轮盘赌选择：适应度越高，被选中的概率越大
*/
private Chromosome selectParent(List<Chromosome> population) {
double totalFitness = population.stream().mapToDouble(c -> Math.max(c.fitness, 0.1)).sum();
double threshold = random.nextDouble() * totalFitness;
double sum = 0;
for (Chromosome c : population) {
sum += Math.max(c.fitness, 0.1);
if (sum >= threshold) return c;
}
return population.get(population.size() - 1);
}
/**
* 单点交叉：交换两条染色体从某点开始的基因序列
*/
private Chromosome[] crossover(Chromosome p1, Chromosome p2) {
if (random.nextDouble() > crossoverRate) {
return new Chromosome[]{p1, p2};
}
int point = random.nextInt(chromosomeLength);
Chromosome c1 = new Chromosome(chromosomeLength);
Chromosome c2 = new Chromosome(chromosomeLength);
for (int i = 0; i < chromosomeLength; i++) {
if (i < point) {
c1.genes[i] = p1.genes[i].clone();
c2.genes[i] = p2.genes[i].clone();
} else {
c1.genes[i] = p2.genes[i].clone();
c2.genes[i] = p1.genes[i].clone();
}
}
return new Chromosome[]{c1, c2};
}
/**
* 变异：以一定概率随机改变某些基因
*/
private void mutate(Chromosome chrom) {
List<Integer> pieceIds = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));
for (int i = 0; i < chromosomeLength; i++) {
if (random.nextDouble() < mutationRate) {
chrom.genes[i][0] = pieceIds.get(random.nextInt(pieceIds.size()));
}
if (random.nextDouble() < mutationRate) {
chrom.genes[i][1] = random.nextInt(4);
}
}
}
主进化循环
/**
* 执行遗传算法求解华容道
* @return 最优解的移动序列
*/
public List<String> solve() {
BoardState initial = createInitialBoard();
List<Chromosome> population = initPopulation();
Chromosome bestEver = null;
for (int gen = 0; gen < maxGenerations; gen++) {
// 评估适应度
for (Chromosome chrom : population) {
evaluateFitness(chrom, initial);
if (bestEver == null || chrom.fitness > bestEver.fitness) {
bestEver = chrom;
if (chrom.fitness >= 1000.0) {
System.out.println("找到解！代数: " + gen);
return extractSolution(bestEver, initial);
}
}
}
// 排序
population.sort((a, b) -> Double.compare(b.fitness, a.fitness));
if (gen % 500 == 0) {
System.out.println("Generation " + gen + ", Best Fitness: " +
String.format("%.2f", population.get(0).fitness) +
", Valid Steps: " + population.get(0).validSteps);
}
// 生成新一代
List<Chromosome> newPopulation = new ArrayList<>();
// 精英保留
int eliteCount = 10;
for (int i = 0; i < eliteCount; i++) {
newPopulation.add(population.get(i));
}
while (newPopulation.size() < populationSize) {
Chromosome p1 = selectParent(population);
Chromosome p2 = selectParent(population);
Chromosome[] children = crossover(p1, p2);
mutate(children[0]);
mutate(children[1]);
newPopulation.add(children[0]);
if (newPopulation.size() < populationSize) {
newPopulation.add(children[1]);
}
}
population = newPopulation;
}
System.out.println("达到最大代数，最优适应度: " + bestEver.fitness);
return extractSolution(bestEver, initial);
}
/**
* 从最优染色体提取可执行的移动序列
*/
private List<String> extractSolution(Chromosome chrom, BoardState initial) {
List<String> moves = new ArrayList<>();
BoardState current = initial.deepCopy();
List<Integer> pieceNames = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
String[] nameMap = {"","曹操","关羽","张飞","赵云","马超","黄忠","兵","兵","兵","兵"};
for (int i = 0; i < chrom.validSteps; i++) {
int pieceId = chrom.genes[i][0];
int dir = chrom.genes[i][1];
BoardState next = tryMove(current, pieceId, dir);
if (next != null) {
moves.add(nameMap[pieceId] + DIR_NAMES[dir]);
current = next;
if (isGoal(current)) {
moves.add("【曹操到达出口，胜利！】");
break;
}
}
}
return moves;
}
public static void main(String[] args) {
GeneticAlgorithmKlondike solver = new GeneticAlgorithmKlondike();
List<String> solution = solver.solve();
System.out.println("\n=== 最优移动序列 ===");
for (int i = 0; i < solution.size(); i++) {
System.out.println((i + 1) + ". " + solution.get(i));
}
}
}
算法复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化种群 | O(P×L) | O(P×L) |
| 适应度评估 | O(P×L×R×C) | O(R×C) |
| 选择 | O(P) | O(1) |
| 交叉 | O(P×L) | O(P×L) |
| 变异 | O(P×L) | O(1) |
| 单代进化 | O(P×L×R×C) | O(P×L) |
| 完整求解 | O(G×P×L×R×C) | O(P×L) |
其中 P=种群大小, L=染色体长度, G=代数, R×C=棋盘大小。
优化与改进
- 自适应变异率：种群多样性降低时自动提高变异率
- 启发式初始化：利用已知开局走法生成部分初始个体
- 多步模拟评估：评估染色体时不只模拟单步，而是预测多步后的局面
- 并行评估：利用多线程同时评估种群中多个个体
总结
遗传算法为华容道这类组合爆炸问题提供了一种启发式求解路径。通过合理的染色体编码和适应度设计，算法能够在较短时间内找到可行解，且随着迭代不断逼近最优。相比传统搜索算法，遗传算法在超大状态空间中展现出更好的可扩展性。
