如何优化最小相邻交换算法？适配15×15网格性能需求

问题背景 #

我们需要解决6种颜色瓷砖组成的二维矩形网格问题：通过最少的**相邻（仅水平/垂直，非对角线）**交换操作，让网格中所有瓷砖都无同色相邻情况，要求支持最大15×15的网格规模，无解时返回no solution。

当前实现的瓶颈 #

现有基于广度优先搜索（BFS）的实现仅能处理16-20块瓷砖的小网格，大网格场景下会出现内存耗尽或运行超时，核心问题包括：

1. 状态存储开销大：用ArrayList<Integer>存储网格状态，克隆和存储的内存、时间成本高
2. 无效状态过多：遍历所有存在同色相邻的瓷砖并尝试四向交换，生成大量重复或无意义的状态
3. 缺乏剪枝策略：未过滤无效交换（如交换同色瓷砖、交换后冲突增加），也未用启发式引导搜索
4. 无无解判断逻辑：无法确定何时终止搜索并返回无解

当前核心交换方法代码：

public static boolean minSwaps(ArrayList<Integer> tiles, int moves) {
    boolean solved = true;
    for (int i = 0; i < tiles.size(); i++) {
      if (hasAdjacent(tiles, i)) {
        solved = false;
        try {
          ArrayList<Integer> tilesNew = (ArrayList<Integer>)tiles.clone();
          Collections.swap(tilesNew, i, i - length);
          queue.add(tilesNew);
          Main.moves.add(moves + 1);
        }
        catch(Exception e) {}
        try {
          ArrayList<Integer> tilesNew = (ArrayList<Integer>)tiles.clone();
          Collections.swap(tilesNew, i, i + length);
          queue.add(tilesNew);
          Main.moves.add(moves + 1);
        }
        catch(Exception e) {}
        try {
          if (i + 1 % length != 0) {
            ArrayList<Integer> tilesNew = (ArrayList<Integer>)tiles.clone();
            Collections.swap(tilesNew, i, i + 1);
            queue.add(tilesNew);
            Main.moves.add(moves + 1);
          }
        }
        catch(Exception e) {}
        try {
          if (i % length != 0) {
            ArrayList<Integer> tilesNew = (ArrayList<Integer>)tiles.clone();
            Collections.swap(tilesNew, i, i - 1);
            queue.add(tilesNew);
            Main.moves.add(moves + 1);
          }
        }
        catch(Exception e) {}
      }
    }
    return solved;
}

针对性优化方案 #

1. 状态表示与存储优化 #

• 替换ArrayList<Integer>为int[]：数组的克隆、访问效率远高于ArrayList，且内存占用更小
• 状态编码压缩：将网格状态编码为紧凑的哈希可表示形式，比如把int[]转为固定格式的字符串（用逗号分隔每个颜色值），或计算自定义哈希值，存入HashSet避免重复处理
• 封装状态与步数：将网格状态和当前步数封装为一个类（如GridState，包含int[] tiles和int steps），统一存入队列，避免单独维护moves列表

2. 剪枝与无效操作过滤 #

• 移除try-catch，用边界判断替代：比如向上交换时先判断i >= length，而非依赖异常捕获，减少异常处理开销
• 过滤无效交换：
  • 交换前检查目标位置颜色，若与当前瓷砖颜色相同直接跳过
  • 预计算交换后的冲突数，若冲突数比当前状态多，不加入队列
• 聚焦冲突点：只针对产生冲突的相邻瓷砖对进行交换，而非遍历所有有冲突的瓷砖，减少不必要的状态生成

3. 搜索算法升级：从BFS到A*启发式搜索 #

纯BFS在大状态空间下效率极低，改用A*算法可大幅提升搜索速度：

• 启发函数设计：以当前网格的同色相邻对数作为启发值h(n)，冲突数越少的状态优先级越高
• 优先队列：用PriorityQueue代替普通队列，每次优先处理启发值+步数最小的状态，更快逼近最优解

4. 无解判断逻辑实现 #

• 可行性预检查：对于m×n网格，任意颜色的瓷砖数量不能超过ceil((m*n + 1)/2)（棋盘格模式下的最大允许数量），超过则直接返回no solution
• 搜索终止条件：当队列为空时，说明所有可能状态已遍历完毕，未找到解，返回no solution

5. 代码细节优化 #

• 复用临时对象：预先创建临时数组，交换后生成新状态，避免频繁创建新对象
• 批量处理冲突：一次遍历找出所有冲突位置并统一处理，减少重复遍历网格的次数
• 缓存相邻位置：预先计算每个位置的上下左右相邻坐标，避免每次判断冲突时重复计算

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