如何优化瓷砖地板算法以高效求解15×15规模问题？

本问题属于已结束的竞赛题目，不会被重复使用

我需要一个能处理最大15×15规模瓷砖地板问题的高效方案，并希望得到详细讲解。问题详情如下：

问题描述（40分） #

山姆雇人铺厨房地板，要求相邻瓷砖颜色不同，但完工后未达标。现在仅允许交换相邻瓷砖（同一行或同一列中相邻的瓷砖），需要找到最少交换次数让地板符合要求；如果无法修复则输出not possible。

示例输入 #

RGR
RPC
GRB
YPG

这代表一个3×4的地板，其中R=红色、G=绿色、B=蓝色、C=青色、P=紫色、Y=黄色。输入由R、G、B、C、P、Y组成的多行字符串，每行长度相同，最大规模为15行15列。

示例输出 #

2
原因：将第2行开头的红色瓷砖与第3行开头的绿色瓷砖交换，再将第3行中间的红色瓷砖与末尾的蓝色瓷砖交换，即可得到合规地板。

我的现有实现及问题 #

我写了一个递归解决方案，但只能处理约16块瓷砖（4×4）的规模，更大规模耗时极长。问题出在朴素递归的特性，每次调用至少会递归自身4次。以下是我的代码：

import java.util.*;
import java.io.*;
class Main {
  private static ArrayList<String[][]> solutions = new ArrayList<String[][]>();
  private static ArrayList<Integer> moves = new ArrayList<Integer>();
  private static int min = Integer.MAX_VALUE;
  
  
  public static void main(String[] args) throws Exception {
    File file = new File("Tiles.txt");
    Scanner scan = new Scanner(file);
    Scanner scan1 = new Scanner(file);
    int length = 0;
    while (scan1.hasNextLine()) {
      scan1.nextLine();
      length++;
    } 
    String[][] tiles = new String[length][];
    for (int i = 0; i < length; i++) {
      String line = scan.nextLine();
      tiles[i] = new String[line.length()];
      for (int l = 0; l < tiles[i].length; l++) {
        tiles[i][l] = line.substring(l, l + 1);
      }
    }

    System.out.println("Start");

    minimumSwaps(tiles, 0, new ArrayList<String>());
    

    //System.out.println(Arrays.toString(findCount(tiles)));
    //findSolutions(new String[tiles.length][tiles[0].length], findCount(tiles), 0, 0);
    //System.out.println(solutions.size());
    System.out.println(min);
    //display();

    
  }

  //tilesIDs: more efficient way to check if computer has seen previous situation

  //how to know if there are moves that do not involve problem areas that reduces total number of moves?

  public static void minimumSwaps (String[][] tiles, int moves, ArrayList<String> tilesIDs) {
    if (moves < min) {
      String newID = computeID(tiles);
      if (linearSearch(tilesIDs, newID)) return;
      tilesIDs.add(newID);
      if (solved(tiles)) {
        //Main.moves.add(moves);
        if (moves < min) min = moves;
        //solutions.add(cloneTiles(tiles));
      }
      else if (moves < min - 1) {
        for (int i = 0; i < tiles.length; i++) {
          for (int l = 0; l < tiles[i].length; l++) {
            if (adjacentPresent(tiles, tiles[i][l], i, l)) {
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i][l - 1];
                newTiles[i][l - 1] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }  
              catch (Exception e) {}
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i][l + 1];
                newTiles[i][l + 1] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }
              catch (Exception e) {}
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i - 1][l];
                newTiles[i - 1][l] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }
              catch (Exception e) {}
              try {
                String[][] newTiles = cloneTiles(tiles);
                String current = newTiles[i][l];
                newTiles[i][l] = newTiles[i + 1][l];
                newTiles[i + 1][l] = current;
                minimumSwaps(newTiles, moves + 1, (ArrayList<String>)(tilesIDs.clone()));
              }
              catch (Exception e) {}
            }
          }  
        }
      }
    }
  }

  public static boolean linearSearch(ArrayList<String> IDs, String newID) {
    for (String ID : IDs) if (ID.equals(newID)) return true;
    return false;
  }

  public static String computeID(String[][] tiles) {
    String ID = "";
    for (String[] letters : tiles) {
      for (String letter : letters) {
        ID += letter;
      }
    }
    return ID;
  }

  public static String[][] cloneTiles(String[][] tiles) {
    String[][] newTiles = new String[tiles.length][tiles[0].length];
    for (int i = 0; i < tiles.length; i++) {
      newTiles[i] = tiles[i].clone();
    }
    return newTiles;
  }

  public static boolean solved(String[][] tiles) {
    for (int i = 0; i < tiles.length; i++) {
      for (int l = 0; l < tiles[i].length; l++) {
        if (adjacentPresent(tiles, tiles[i][l], i, l)) return false;
      }
    }
    return true;
  }

  public static int minMoves() {
    int min = Integer.MAX_VALUE;
    for (int num : moves) if (num < min) min = num;
    return min;
  }

  public static void findSolutions(String[][] tiles, int[] count, int i, int l) {

    String[] colors = {"R", "G", "B", "C", "P", "Y"};
    for (int z = 0; z < 6; z++) {
      //System.out.println("testing");
      if (!adjacentPresent(tiles, colors[z], i, l) && count[z] > 0) {
        String[][] newTiles = new String[tiles.length][tiles[0].length];
        for (int a = 0; a < newTiles.length; a++) {
          for (int b = 0; b < newTiles[0].length; b++) {
            newTiles[a][b] = tiles[a][b]; // clone does not work properly?
          }
        }
        newTiles[i][l] = colors[z];
        //System.out.println(Arrays.deepToString(newTiles));
        int[] newCount = count.clone();
        newCount[z]--;
        if (l == tiles[0].length - 1 && i != tiles.length - 1) {
          findSolutions(newTiles, newCount, i + 1, 0);
        }
        else if (l < tiles[0].length - 1) {
          findSolutions(newTiles, newCount, i, l + 1);
        }
        else if (l == tiles[0].length - 1 && i == tiles.length - 1) {
          solutions.add(newTiles);
        }
      }
    }
  }

  public static boolean adjacentPresent(String[][] tiles, String color, int i, int l) {
    try {
      if (tiles[i][l + 1].equals(color)) return true;
    }
    catch (Exception e) {}
    try {
      if (tiles[i][l - 1].equals(color)) return true;
    }
    catch (Exception e) {}
    try {
      if (tiles[i + 1][l].equals(color)) return true;
    }
    catch (Exception e) {}
    try {
      if (tiles[i - 1][l].equals(color)) return true;
    }
    catch (Exception e) {}

    return false;
  }

  public static int[] findCount(String[][] tiles) {
    int[] count = new int[6];
    for (String[] line : tiles) {
      for (String letter : line) {
        switch (letter) {
          case "R": count[0]++;
          break;
          case "G": count[1]++;
          break;
          case "B": count[2]++;
          break;
          case "C": count[3]++;
          break;
          case "P": count[4]++;
          break;
          case "Y": count[5]++;
          break;
        }
      }
    }
    return count;
  } 

  public static void display() {
    for (String[][] lines : solutions) {
      for (String[] line : lines) {
        for (String letter : line) {
          System.out.print(letter);
        }
        System.out.println();
      }
      System.out.println("\n\n");
    }
  }
}

核心思路：A*算法 + 状态优化 #

朴素递归的问题在于状态空间爆炸，且无优先级引导搜索。用A*算法优先搜索最有希望的状态，配合状态压缩、哈希去重等优化，可处理15×15规模。

1. 状态表示 #

• 将地板状态压缩为字符串（和现有computeID逻辑一致），但用HashSet存储已访问状态，将查重时间复杂度降至O(1)。
• 每个搜索节点包含：当前地板状态、已交换次数、预估剩余交换次数（启发式函数）。

2. 启发式函数设计（关键） #

启发式函数h(n)需满足可采纳性（不高估剩余步数），才能保证A*找到最优解，可选两种方案：

• 冲突瓷砖计数：统计当前地板中相邻同色的瓷砖对数，每对冲突至少需1次交换解决，h(n)取冲突对数。
• 瓷砖位移代价：先预生成所有合法目标地板（回溯生成符合相邻不同色且颜色数量匹配的布局），计算当前状态到每个目标状态的最小交换代价（每个瓷砖曼哈顿距离之和除以2，因每次交换解决两个瓷砖位移），取最小值作为h(n)。

3. A*算法实现步骤 #

1. 初始化优先队列：节点按f(n) = g(n) + h(n)排序（g(n)为已交换次数，f(n)越小优先级越高）。初始节点为输入状态，g(n)=0，计算h(n)。
2. 状态去重：用HashSet存储已处理状态，避免重复搜索。
3. 循环处理节点：
   • 取出队列中f(n)最小的节点。
   • 若当前状态合规，返回g(n)作为答案。
   • 生成所有相邻交换后的新状态：对每个瓷砖尝试上下左右交换（做边界判断避免异常）。
   • 对未访问过的新状态，计算g(n)+1和新h(n)，加入队列并标记为已访问。
4. 终止条件：队列空且未找到合规状态，返回not possible。

4. 额外优化手段 #

• 预筛选目标状态：先通过回溯生成所有符合颜色数量要求的合规布局，若无此类布局直接返回not possible，避免无效搜索。
• 状态压缩优化：15×15地板中，每个瓷砖用3位二进制表示（6种颜色足够），将状态压缩为long数组或自定义整数类型，节省内存并提升查重效率。
• 剪枝策略：若当前节点f(n)大于已知最小解，直接跳过该节点的搜索。

复杂度分析 #

• 状态空间：15×15状态总数极大，但A*的启发式函数会大幅减少搜索节点数，配合去重，实际可处理目标规模。
• 时间复杂度：主要取决于启发式函数质量，优秀的启发式可将搜索节点数控制在可接受范围内。

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