java 如何让算法更高效?

nmpmafwu  于 2022-12-10  发布在  Java
关注(0)|答案(1)|浏览(147)

免责声明此问题是已完成竞赛的一部分,不会重复使用

我希望有人可以创建并解释一个解决方案,足够有效地运行文件大小最多为15 x 15瓷砖。
瓷砖地面(40分)Sam最近雇佣了一名瓷砖安装工来铺厨房的地板。地板应该是色彩丰富的,没有两块相邻的瓷砖具有相同的颜色。不幸的是,安装工未能确保相邻的瓷砖具有不同的颜色。砂浆仍然是湿的,但很难一次只抬起一块瓷砖。因此安装人员仅限于交换相邻的瓷砖。问题是如何在尽可能少的移动中交换相邻的瓷砖,以使地板满足没有两个相邻瓷砖具有相同颜色的标准。示例输入为RGR RPC GRB YPG表示3 × 4楼层上的瓷砖,其中R是红色瓷砖,G是绿色,B是蓝色,C是青色,P是紫色,Y是黄色。通常,输入将是一系列线R、G、B、C、P和Y。每行将具有相同的长度,并且最多将有15行,每行中有15个字符。输出将是表示相邻瓷砖的交换次数的整数。对于该问题,“相邻”意味着接触并且在同一行或列中;例如,只有两个瓷砖与上面楼层左下角的黄色瓷砖相邻:第三行开始处的绿色区块和第四行中间处的紫色区块。由于第二行开始处的红色区块可以与第三行开始处的绿色区块交换,然后行3中间的红色区块可以与末尾的蓝色区块交换。这给出了RGR GPC RBR YPG的排列方式。也可以进行其他修复,例如交换第2行的前两个瓷砖以获得PRC,然后交换第3行和第4行的中间瓷砖。您的程序不会打印生成的地板排列方式,**有时无法修复地板:**GGYGP CGGRG无法平铺,因为有6个G,而这种大小的地板在没有两个相邻的情况下只能容纳5个G。在没有解决方案的情况下,将无法输出
我已经创建了一个解决方案,但它只适用于大约16个瓷砖(4 x 4),再多就需要大量的时间。这是因为这个函数的递归和天真的本质,对于每一个调用,它调用自己至少4次。
下面是我尝试的解决方案,请记住,前面的尝试中有额外的方法,并且minimumSwaps()是主要的递归方法:

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");
    }
  }
}
2uluyalo

2uluyalo1#

改进算法

广度优先搜索会首先得到最优解,但在解较深的较大问题上,它仍然会很慢;或者在最坏的情况下,根本没有解决方案。
你目前的算法看起来像是深度优先的回溯算法,因此你需要在确定找到最短的解之前查看所有可能的解,这是非常浪费的。

改进数据表示

在一个15 x15的网格中有6种颜色。您当前存储了15 x15 =225个字符串,并且不断地复制String[][]。使用单个byte[]会更有效(长度为dim x dim),可以更快地复制。使用整数(1,2,...)而不是颜色字符(“R”,“Y”,...)。对于一维,你必须做一些数学来检查相邻性,但这并不是什么太花哨的事情;这样就赢得了大量的内存局部性。

相关问题