近期某手游出了個活動，經(jīng)確認(rèn)發(fā)現(xiàn)本質(zhì)為十滴水游戲。
簡單說一下規(guī)則，棋盤大小通常為6x6，在游戲開始時，棋盤隨機(jī)有若干水珠，其大小范圍為1-4。點擊棋盤內(nèi)的一格，會消耗玩家持有的1個小水滴，同時使得該單元格的水珠大小+1。如果水珠大小超過4，則水珠發(fā)生爆炸并消失，同時向四個方向各發(fā)射1個小水滴。小水滴勻速前進(jìn)，前進(jìn)時遇到第一個水珠則消失，同時該水珠大小+1，或者小水滴遇到棋盤邊界而消失。當(dāng)棋盤被清空時這一關(guān)通過，或者玩家持有的水滴耗盡而游戲結(jié)束。如果一次操作引發(fā)多個水珠爆炸，則每爆炸3個水珠，獎勵1個水滴。如果只觸發(fā)爆炸一次水珠通過這一關(guān)，則視為完美通關(guān)，額外獎勵1個小水滴。對于該游戲，每次通關(guān)獎勵2個小水滴。
查閱了相關(guān)資料后，得到了幾條關(guān)鍵思路，即：
1、根據(jù)一個確定的盤面和一個坐標(biāo)，通過計算，可以得到一個確定的執(zhí)行結(jié)果，這樣的操作稱為一步。
2、一般不會在空白的單元格上設(shè)置小水滴，所以隨機(jī)不停地在有水珠的單元格上添加小水滴，必然在有限的步驟后清空棋盤。
3、暴力遍歷的話，由于狀態(tài)空間太大，只要步數(shù)稍多（7步或更長），就不能在合理的時間內(nèi)找到最優(yōu)解。
所以，我們可以得到進(jìn)一步的推論，我們可以使用一個有限且有序的點列表，解決一個盤面，并計算出該解法的小水滴的收益，期間最大投入小水滴的數(shù)量等結(jié)果。我們最終的目的是使得小水滴的收益最大化。
?因此，我決定使用遺傳算法，解決本問題。
?
首先定義游戲關(guān)鍵對象：
1 package bean; 2 3 import main.Game; 4 5 import java.util.HashMap; 6 import java.util.Map; 7 8 /** 9 * 位置點 10 */ 11 public class Point { 12 13 private static final Map<Integer, Map<Integer, Point>> POINT_MAP = new HashMap<>(); 14 15 /** 16 * X坐標(biāo) 17 */ 18 private final int x; 19 20 /** 21 * Y坐標(biāo) 22 */ 23 private final int y; 24 25 private Point(int x, int y) { 26 this.x = x; 27 this.y = y; 28 } 29 30 /** 31 * 獲取一個點對象 32 * 33 * @param x X坐標(biāo) 34 * @param y Y坐標(biāo) 35 * @return 生成的點對象 36 */ 37 public static Point get(int x, int y) { 38 Map<Integer, Point> subPointMap = POINT_MAP.computeIfAbsent(x, i -> new HashMap<>()); 39 return subPointMap.computeIfAbsent(y, i -> new Point(x, y)); 40 } 41 42 public int getX() { 43 return x; 44 } 45 46 public int getY() { 47 return y; 48 } 49 50 public boolean isValidPosition() { 51 return x >= 0 && y >= 0 && x < Game.X && y < Game.Y; 52 } 53 54 @Override 55 public String toString() { 56 return String.format("(%s,%s)", x, y); 57 } 58 }
1 package bean; 2 3 /** 4 * 子彈對象，即爆裂發(fā)生時需要計算隨時間變化的結(jié)果 5 */ 6 public class Bullet { 7 8 /** 9 * X坐標(biāo) 10 */ 11 private int x; 12 13 /** 14 * Y坐標(biāo) 15 */ 16 private int y; 17 18 /** 19 * X變化率 20 */ 21 private int dx; 22 23 /** 24 * Y變化率 25 */ 26 private int dy; 27 28 public Bullet() { 29 } 30 31 public Bullet(int x, int y, int dx, int dy) { 32 this.x = x; 33 this.y = y; 34 this.dx = dx; 35 this.dy = dy; 36 } 37 38 public Bullet(Point point, int dx, int dy) { 39 this(point.getX(), point.getY(), dx, dy); 40 } 41 42 public int getX() { 43 return x; 44 } 45 46 public void setX(int x) { 47 this.x = x; 48 } 49 50 public int getY() { 51 return y; 52 } 53 54 public void setY(int y) { 55 this.y = y; 56 } 57 58 public int getDx() { 59 return dx; 60 } 61 62 public void setDx(int dx) { 63 this.dx = dx; 64 } 65 66 public int getDy() { 67 return dy; 68 } 69 70 public void setDy(int dy) { 71 this.dy = dy; 72 } 73 74 /** 75 * 子彈移動一個回合 76 * 77 * @return 移動后的位置 78 */ 79 public Point move() { 80 x += dx; 81 y += dy; 82 return Point.get(x, y); 83 } 84 }
1 package bean; 2 3 /** 4 * 游戲的行動結(jié)果對象，會進(jìn)行緩存 5 */ 6 public class MoveResult { 7 8 /** 9 * 行動后的盤面 10 */ 11 private int[][] arr; 12 13 /** 14 * 行動后獲得的收益(可以由combo計算出) 15 */ 16 private int reward; 17 18 /** 19 * 行動連擊數(shù)量，即本次行動導(dǎo)致多少爆炸 20 */ 21 private int combo; 22 23 public MoveResult() { 24 25 } 26 27 public MoveResult(int[][] arr, int reward, int combo) { 28 this.arr = arr; 29 this.reward = reward; 30 this.combo = combo; 31 } 32 33 public int[][] getArr() { 34 return arr; 35 } 36 37 public void setArr(int[][] arr) { 38 this.arr = arr; 39 } 40 41 public int getReward() { 42 return reward; 43 } 44 45 public void setReward(int reward) { 46 this.reward = reward; 47 } 48 49 public int getCombo() { 50 return combo; 51 } 52 53 public void setCombo(int combo) { 54 this.combo = combo; 55 } 56 }
1 package bean; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 /** 7 * 遺傳算法使用的解答 8 */ 9 public class Answer { 10 11 /** 12 * 操作鏈，存儲依次的執(zhí)行操作 13 */ 14 private final List<Point> pointList = new ArrayList<>(); 15 16 /** 17 * 爆炸次數(shù) 18 */ 19 private int burstCount; 20 21 /** 22 * 累計的收益 23 */ 24 private int totalReward; 25 26 /** 27 * 區(qū)間最低收益 28 */ 29 private int minReward; 30 31 public Answer() { 32 } 33 34 public Answer(List<Point> pointList) { 35 this.pointList.addAll(pointList); 36 } 37 38 public List<Point> getPointList() { 39 return pointList; 40 } 41 42 public int getBurstCount() { 43 return burstCount; 44 } 45 46 public void setBurstCount(int burstCount) { 47 this.burstCount = burstCount; 48 } 49 50 public int getTotalReward() { 51 return totalReward; 52 } 53 54 public void setTotalReward(int totalReward) { 55 this.totalReward = totalReward; 56 } 57 58 public int getMinReward() { 59 return minReward; 60 } 61 62 public void setMinReward(int minReward) { 63 this.minReward = minReward; 64 } 65 66 /** 67 * 獲取解的長度 68 * 69 * @return 解的長度 70 */ 71 public int length() { 72 return pointList.size(); 73 } 74 75 @Override 76 public String toString() { 77 return String.format("%s, %s, %s, %s, %s", totalReward, burstCount, length(), minReward, pointList); 78 } 79 }
以及工具類
1 package util; 2 3 import bean.Answer; 4 import bean.MoveResult; 5 import bean.Point; 6 import main.Game; 7 8 import java.util.ArrayList; 9 import java.util.List; 10 11 public class Utils { 12 13 /** 14 * 可視化一個Array（用于打?。? 15 * 16 * @param game 游戲 17 * @param answer 解答 18 * @return 復(fù)制后的Array 19 */ 20 public static String answerString(Game game, Answer answer) { 21 StringBuilder builder = new StringBuilder(); 22 23 int[][] arr = game.getInitArr(); 24 int[][] moveArr = new int[Game.X][Game.Y]; 25 int moved = 0; 26 int totalReward = 0; 27 int minReward = 0; 28 int burstCount = 0; 29 StringBuilder moveBuilder = new StringBuilder(); 30 for (int i = 0; i < answer.length(); i++) { 31 Point point = answer.getPointList().get(i); 32 if (arr[point.getX()][point.getY()] <= 0) { 33 continue; 34 } 35 36 // 記錄本次操作的結(jié)果，并更新棋盤狀態(tài) 37 MoveResult move = Game.move(arr, point); 38 totalReward += move.getReward(); 39 if (minReward > totalReward) { 40 minReward = totalReward; 41 } 42 if (move.getCombo() > 0) { 43 burstCount++; 44 // 發(fā)生爆炸，則打印之前的行 45 if (moved > 0) { 46 answerStringArrLine(builder, moveBuilder, arr, moveArr); 47 builder.append("\r\n"); 48 moveArr = new int[Game.X][Game.Y]; 49 moved = 0; 50 } 51 } 52 arr = move.getArr(); 53 moveArr[point.getX()][point.getY()] += 1; 54 moved++; 55 56 builder.append(i).append(", Reward: ").append(move.getReward()).append(", TotalReward: ").append(totalReward).append(", Combo: ").append(move.getCombo()).append(", ").append(point); 57 builder.append("\r\n"); 58 if (move.getCombo() > 0) { 59 answerStringArrLine(builder, moveBuilder, arr, moveArr); 60 builder.append("\r\n"); 61 moveArr = new int[Game.X][Game.Y]; 62 moved = 0; 63 } 64 } 65 66 if (burstCount <= 1) { 67 builder.append("Full Combo!").append("\r\n"); 68 } else { 69 builder.append("BurstCount: ").append(burstCount).append("\r\n"); 70 } 71 72 builder.append(answer.getTotalReward()).append(", ").append(answer.getBurstCount()).append(", ").append(answer.length()).append(", ").append(answer.getMinReward()).append(": ").append(moveBuilder).append("\r\n"); 73 74 return builder.toString(); 75 } 76 77 private static void answerStringArrLine(StringBuilder builder, StringBuilder moveBuilder, int[][] arr, int[][] moveArr) { 78 List<String> moveList = new ArrayList<>(); 79 for (int x = 0; x < arr.length; x++) { 80 for (int y = 0; y < arr.length; y++) { 81 builder.append(arr[x][y]).append(", "); 82 } 83 builder.append(" "); 84 for (int y = 0; y < arr.length; y++) { 85 builder.append(moveArr[x][y]).append(", "); 86 if (moveArr[x][y] > 0) { 87 moveList.add(String.format("(%s, %s, %s)", x, y, moveArr[x][y])); 88 } 89 } 90 builder.append("\r\n"); 91 } 92 moveBuilder.append(moveList.toString()).append(" "); 93 } 94 95 /** 96 * 將一個數(shù)組轉(zhuǎn)化為String（配合Map使用） 97 * 98 * @param arr 待處理數(shù)組 99 * @return 處理結(jié)果 100 */ 101 public static String arrKey(int[][] arr) { 102 StringBuilder builder = new StringBuilder(); 103 for (int i = 0; i < arr.length; i++) { 104 for (int j = 0; j < arr[i].length; j++) { 105 builder.append(arr[i][j]); 106 } 107 } 108 return builder.toString(); 109 } 110 111 /** 112 * 可視化一個Array（用于打?。?113 * 114 * @param arr 待復(fù)制數(shù)組 115 * @return 復(fù)制后的Array 116 */ 117 public static String arrString(int[][] arr) { 118 StringBuilder builder = new StringBuilder(); 119 for (int i = 0; i < arr.length; i++) { 120 for (int j = 0; j < arr[i].length; j++) { 121 builder.append(arr[i][j]); 122 builder.append(", "); 123 } 124 if (i < arr.length - 1) { 125 builder.append("\r\n"); 126 } 127 } 128 return builder.toString(); 129 } 130 131 /** 132 * 復(fù)制一個Array 133 * 134 * @param arr 待復(fù)制數(shù)組 135 * @return 復(fù)制后的Array 136 */ 137 public static int[][] arrCopy(int[][] arr) { 138 int[][] result = new int[arr.length][]; 139 for (int i = 0; i < arr.length; i++) { 140 result[i] = new int[arr[i].length]; 141 for (int j = 0; j < arr[i].length; j++) { 142 result[i][j] = arr[i][j]; 143 } 144 } 145 return result; 146 } 147 148 /** 149 * 返回一個在0到num之間的隨機(jī)數(shù)，包含0，不包含num 150 * 151 * @param num 數(shù)字 152 * @return 返回隨機(jī)數(shù) 153 */ 154 public static int randInt(int num) { 155 if (num >= 0) { 156 return randInt(0, num); 157 } else { 158 return randInt(num, 0); 159 } 160 } 161 162 /** 163 * 返回一個在min到max之間的隨機(jī)數(shù)，包含min，不包含max 164 * 165 * @param min 隨機(jī)數(shù)下限 166 * @param max 隨機(jī)數(shù)上限 167 * @return 返回隨機(jī)數(shù) 168 */ 169 public static int randInt(int min, int max) { 170 int diff = max - min; 171 int rand = (int) (Math.random() * diff); 172 return min + rand; 173 } 174 175 /** 176 * 求一組數(shù)字的最大值 177 * 178 * @param nums 輸入數(shù)列 179 * @return 最大值 180 */ 181 public static int max(int... nums) { 182 int result = nums[0]; 183 for (int i = 1; i < nums.length; i++) { 184 if (nums[i] > result) { 185 result = nums[i]; 186 } 187 } 188 return result; 189 } 190 191 /** 192 * 求一組數(shù)字的最小值 193 * 194 * @param nums 輸入數(shù)列 195 * @return 最小值 196 */ 197 public static int min(int... nums) { 198 int result = nums[0]; 199 for (int i = 1; i < nums.length; i++) { 200 if (nums[i] < result) { 201 result = nums[i]; 202 } 203 } 204 return result; 205 } 206 }
?
接下來需要模擬游戲過程了：
這部分的重點是，需要不停地掃描當(dāng)前是否有水滴在活動，以及是否有水珠發(fā)生爆炸。兩者要分開并依次進(jìn)行，以防止多個水滴同時命中水珠后爆炸，導(dǎo)致結(jié)果誤判。
計算完畢一個狀態(tài)以后，可以把它緩存，之后無需重復(fù)計算。
1 package main; 2 3 import bean.Bullet; 4 import bean.MoveResult; 5 import bean.Point; 6 import util.Utils; 7 8 import java.util.ArrayList; 9 import java.util.HashMap; 10 import java.util.List; 11 import java.util.Map; 12 13 /** 14 * 游戲的基本參數(shù)與功能 15 * 如果需要分析別的盤面，在這里修改參數(shù) 16 */ 17 public class Game { 18 19 /** 20 * 棋盤X大小 21 */ 22 public static int X = 6; 23 24 /** 25 * 棋盤Y大小 26 */ 27 public static int Y = 6; 28 29 /** 30 * 爆裂門檻 31 */ 32 public static int BURST = 4; 33 34 /** 35 * 獎勵倒數(shù)，COMBO除以這個數(shù)后得到獎勵 36 */ 37 public static int REWARD_INV = 3; 38 39 /** 40 * 完美通關(guān)的額外獎勵 41 */ 42 public static int REWARD_PFT = 1; 43 44 /** 45 * 緩存發(fā)生爆炸后的計算結(jié)果 46 */ 47 public static Map<String, MoveResult> MOVE_MAP = new HashMap<>(524288); 48 49 /** 50 * 待求解初始狀態(tài) 51 */ 52 private int[][] initArr = { 53 {0, 2, 2, 1, 4, 4}, 54 {2, 1, 1, 1, 3, 0}, 55 {2, 3, 1, 2, 2, 4}, 56 {0, 3, 2, 0, 0, 4}, 57 {1, 0, 3, 2, 1, 0}, 58 {3, 3, 0, 2, 0, 0}, 59 60 }; 61 62 // public static void main(String[] args) { 63 // Game game = new Game(); 64 // MoveResult move = move(game.initArr, 5, 3); 65 // System.out.println(Utils.arrString(move.getArr())); 66 // System.out.println(move.getCombo()); 67 // } 68 69 /** 70 * @param arr 棋盤 71 * @param point 坐標(biāo)點 72 * @return v1: 執(zhí)行后的棋盤, v2: 本次操作的收益, v3: 是否發(fā)生了爆炸 73 */ 74 public static MoveResult move(int[][] arr, Point point) { 75 return move(arr, point.getX(), point.getY()); 76 } 77 78 /** 79 * 執(zhí)行一次加水操作，返回執(zhí)行后的棋盤，本次操作收益，是否發(fā)生爆炸 80 * 如果發(fā)生爆炸，需要緩存對應(yīng)結(jié)果 81 * 82 * @param arr 棋盤 83 * @param x X坐標(biāo) 84 * @param y Y坐標(biāo) 85 * @return v1: 執(zhí)行后的棋盤, v2: 本次操作的收益, v3: 是否發(fā)生了爆炸 86 */ 87 public static MoveResult move(int[][] arr, int x, int y) { 88 int[][] resArr = Utils.arrCopy(arr); 89 resArr[x][y]++; 90 if (resArr[x][y] <= BURST) { 91 // 本次操作不會導(dǎo)致爆炸，直接返回 92 return new MoveResult(resArr, -1, 0); 93 } 94 String arrKey = Utils.arrKey(arr) + x + y; 95 MoveResult result = MOVE_MAP.get(arrKey); 96 if (result != null) { 97 // 本次操作命中緩存，直接返回 98 return result; 99 } 100 101 // 循環(huán)計算爆炸結(jié)果 102 int combo = 0; 103 List<Bullet> bulletList = new ArrayList<>(); 104 do { 105 // 1. 所有水滴移動1回合 106 List<Bullet> newBulletList = new ArrayList<>(); 107 for (Bullet bullet : bulletList) { 108 Point point = bullet.move(); 109 if (!point.isValidPosition()) { 110 // 水滴出界，則移除掉它 111 continue; 112 } 113 if (resArr[point.getX()][point.getY()] > 0) { 114 // 水滴遇到了已存在的水球，則水球大小+1，移除水滴 115 resArr[point.getX()][point.getY()]++; 116 continue; 117 } 118 // 水滴通過校驗，存活進(jìn)入下一個回合 119 newBulletList.add(bullet); 120 } 121 122 // 2. 檢查是否有水珠爆炸，是的話在該位置生成4個方向的新水滴，并將所在位置的格子置空 123 List<Point> burstPointList = availablePoints(resArr, 1); 124 for (Point point : burstPointList) { 125 newBulletList.add(new Bullet(point, 1, 0)); 126 newBulletList.add(new Bullet(point, 0, 1)); 127 newBulletList.add(new Bullet(point, -1, 0)); 128 newBulletList.add(new Bullet(point, 0, -1)); 129 resArr[point.getX()][point.getY()] = 0; 130 combo++; 131 } 132 133 bulletList = newBulletList; 134 } while (!bulletList.isEmpty()); 135 136 int reward = combo / REWARD_INV - 1; 137 result = new MoveResult(resArr, reward, combo); 138 MOVE_MAP.put(arrKey, result); 139 return result; 140 } 141 142 /** 143 * 獲取可選的點 144 * 145 * @param arr 棋盤 146 * @param burst 點的狀態(tài)，0為任意有水滴點，1為僅滿，-1為僅不滿 147 * @return 返回的可選點列表 148 */ 149 public static List<Point> availablePoints(int[][] arr, int burst) { 150 List<Point> pointList = new ArrayList<>(); 151 for (int i = 0; i < arr.length; i++) { 152 for (int j = 0; j < arr[i].length; j++) { 153 if (arr[i][j] > 0) { 154 int isBurst = arr[i][j] > BURST ? 1 : -1; 155 int result = burst * isBurst; 156 if (result >= 0) { 157 pointList.add(Point.get(i, j)); 158 } 159 } 160 } 161 } 162 return pointList; 163 } 164 165 public int[][] getInitArr() { 166 return initArr; 167 } 168 169 public void setInitArr(int[][] initArr) { 170 this.initArr = initArr; 171 } 172 }
?
接下來，就是使用遺傳算法，計算出最優(yōu)解了。
這里我想了想，找到了一個盡可能適合本問題的生成子代方法，大致是這樣的：
1、分?jǐn)?shù)最高的<精英個數(shù)>名后代，直接移入下一回合
2、分?jǐn)?shù)最高的<精英個數(shù)>名后代，隨機(jī)兩兩配對，獨立地產(chǎn)生2個后代，可能變異
3、分?jǐn)?shù)最高的<普通個數(shù)>名后代，隨機(jī)兩兩配對，對立地產(chǎn)生2個后代，可能變異
4、分?jǐn)?shù)最高的<隨機(jī)個數(shù)>名后代，從隨機(jī)位置截斷，截斷后的部分全部隨機(jī)生成
配對時，以50%幾率設(shè)置1個切斷位點，25%幾率設(shè)置2個切斷位點，25%幾率設(shè)置3個切斷位點。重組位點在兩個解長度較小值之內(nèi)。
變異發(fā)生時，以50%幾率修改一步，25%幾率增加一步，25%幾率刪除一步。
生成子代后，計算它們的最終收益，爆炸次數(shù)、解的長度，以及期間最大投入成本，并排序。
如果計算出的解的最終收益、爆炸次數(shù)、解的長度發(fā)生更新，則回合數(shù)置零。當(dāng)回合數(shù)超過<最大回合數(shù)>時，終止并輸出結(jié)果。
經(jīng)過參數(shù)調(diào)優(yōu)，精英個數(shù)設(shè)置為128，普通個數(shù)為4096，隨機(jī)個數(shù)為512，最大回合數(shù)為128，變異幾率為0.125。
?
本算法和一般的遺傳算法不同的地方：
1、不限制答案長度。（但理論最大是6x6x3步）
2、生成后代的方式比較豐富，但只允許適應(yīng)度最高的一些解產(chǎn)生后代。但是，不在這范圍內(nèi)的解直接淘汰，而不是以幾率被選擇。
3、允許了最多3個重組位點，而不是固定1個。
4、允許突變發(fā)生增加和刪除操作，而不是只有修改操作。
1 package main; 2 3 import bean.Answer; 4 import bean.MoveResult; 5 import bean.Point; 6 import util.Utils; 7 8 import java.util.ArrayList; 9 import java.util.Collections; 10 import java.util.Comparator; 11 import java.util.List; 12 13 /** 14 * 遺傳算法，尋找一個盡可能收益最高的解 15 */ 16 public class Resolve { 17 18 /** 19 * 種群容量 20 * 初始生成數(shù)量、生成普通后代時的配對數(shù)量 21 */ 22 private int capacity = 4096; 23 24 /** 25 * 精英種群容量 26 * 精英種群直接移入下一回合，同時兩兩配對產(chǎn)生2個后代 27 */ 28 private int eliteCapacity = 128; 29 30 /** 31 * 隨機(jī)種群容量 32 * 每回合對該數(shù)量的成員，在某位置截斷，之后部分重新生成 33 * 它負(fù)責(zé)同時引入大量突變 34 */ 35 private int randomCutCapacity = 512; 36 37 /** 38 * 經(jīng)過該回合數(shù)，最優(yōu)解的適應(yīng)度不發(fā)生變化，則終止并退出遺傳算法，輸出結(jié)果 39 */ 40 private int stableExitTurn = 128; 41 42 /** 43 * 重組時發(fā)生變異的幾率 44 * 一旦發(fā)生，隨機(jī)位置以25%幾率新增1個操作，25%刪除1個操作，50%修改1個操作（修改后可能與原操作相同） 45 */ 46 private double variationRate = 0.125D; 47 48 public int getCapacity() { 49 return capacity; 50 } 51 52 public void setCapacity(int capacity) { 53 this.capacity = capacity; 54 } 55 56 public int getEliteCapacity() { 57 return eliteCapacity; 58 } 59 60 public void setEliteCapacity(int eliteCapacity) { 61 this.eliteCapacity = eliteCapacity; 62 } 63 64 public int getRandomCutCapacity() { 65 return randomCutCapacity; 66 } 67 68 public void setRandomCutCapacity(int randomCutCapacity) { 69 this.randomCutCapacity = randomCutCapacity; 70 } 71 72 public int getStableExitTurn() { 73 return stableExitTurn; 74 } 75 76 public void setStableExitTurn(int stableExitTurn) { 77 this.stableExitTurn = stableExitTurn; 78 } 79 80 public double getVariationRate() { 81 return variationRate; 82 } 83 84 public void setVariationRate(double variationRate) { 85 this.variationRate = variationRate; 86 } 87 88 public static void main(String[] args) { 89 Resolve resolve = new Resolve(); 90 Game game = new Game(); 91 92 // for (int i = 0; i < game.getInitArr().length; i++) { 93 // for (int j = 0; j < game.getInitArr()[i].length; j++) { 94 // game.getInitArr()[i][j] = Utils.randInt(5); 95 // } 96 // } 97 // System.out.println(Utils.arrString(game.getInitArr())); 98 // System.out.println(); 99 100 Answer answer = resolve.select(game); 101 System.out.println(answer); 102 } 103 104 /** 105 * 遺傳算法執(zhí)行入口 106 * 107 * @param game 游戲 108 * @return 找到的最優(yōu)解 109 */ 110 public Answer select(Game game) { 111 int turn = 0; 112 int stableTurn = 0; 113 int lastTotalReward = 0; 114 int lastBurstCount = 0; 115 int lastLength = 0; 116 List<Answer> answerList = new ArrayList<>(capacity); 117 118 // 初始化，產(chǎn)生最初的答案 119 for (int i = 0; i < capacity; i++) { 120 Answer answer = new Answer(); 121 calcTotalReward(game, answer); 122 answerList.add(answer); 123 } 124 sortAnswerList(answerList); 125 126 // 執(zhí)行遺傳算法 127 while (stableTurn < stableExitTurn) { 128 // 1. 生成下一代，同時計算總獎勵 129 List<Answer> newAnswerList = new ArrayList<>(capacity + eliteCapacity * 2 + randomCutCapacity); 130 131 // A. 分?jǐn)?shù)最高的<精英個數(shù)>名后代，直接移入下一回合 132 for (int i = 0; i < eliteCapacity; i++) { 133 newAnswerList.add(answerList.get(i)); 134 } 135 136 // B. 分?jǐn)?shù)最高的<精英個數(shù)>名后代，隨機(jī)兩兩配對，獨立地產(chǎn)生2個后代，可能變異 137 List<Answer> eliteMateAnswerList = mate(game, answerList, eliteCapacity, 0); 138 newAnswerList.addAll(eliteMateAnswerList); 139 140 // C. 分?jǐn)?shù)最高的<普通個數(shù)>名后代，隨機(jī)兩兩配對，對立地產(chǎn)生2個后代，可能變異 141 List<Answer> mateAnswerList = mate(game, answerList, capacity, 2); 142 newAnswerList.addAll(mateAnswerList); 143 144 // D. 分?jǐn)?shù)最高的<隨機(jī)個數(shù)>名后代，從隨機(jī)位置截斷，截斷后的部分全部隨機(jī)生成 145 for (int i = 0; i < randomCutCapacity; i++) { 146 newAnswerList.add(randomCut(game, answerList.get(i))); 147 } 148 149 // 2. 更新循環(huán)狀態(tài) 150 Collections.shuffle(newAnswerList); 151 sortAnswerList(newAnswerList); 152 Answer bestAnswer = newAnswerList.get(0); 153 turn++; 154 if (bestAnswer.getTotalReward() == lastTotalReward && bestAnswer.getBurstCount() == lastBurstCount && bestAnswer.length() == lastLength) { 155 stableTurn++; 156 } else { 157 stableTurn = 0; 158 } 159 lastTotalReward = bestAnswer.getTotalReward(); 160 lastBurstCount = bestAnswer.getBurstCount(); 161 lastLength = bestAnswer.length(); 162 answerList = newAnswerList; 163 System.out.println(turn + ", " + stableTurn + ": " + bestAnswer); 164 } 165 166 // 打印最終找到的最優(yōu)解（16個） 167 System.out.println(); 168 System.out.println("最優(yōu)Top16："); 169 for (int i = 0; i < 16; i++) { 170 Answer answer = answerList.get(i); 171 System.out.println(answer); 172 } 173 174 // 打印最優(yōu)解 175 System.out.println(); 176 System.out.println("最優(yōu)解關(guān)鍵盤面："); 177 Answer bestAnswer = answerList.get(0); 178 System.out.println(Utils.answerString(game, bestAnswer)); 179 return bestAnswer; 180 } 181 182 /** 183 * 兩兩配對，每一對產(chǎn)生2個后代 184 * 重組斷點50%為1個，25%為2個，25%為3個。 185 * 186 * @param game 游戲 187 * @param answerList 排序后的解答列表 188 * @param limit 數(shù)量限制，只有最前面的解答有資格產(chǎn)生后代 189 * @param policy 0: 對立產(chǎn)生后代，生成2個子代，分別隨機(jī)地獨占親代的基因，親代基因不會丟失，1或以上：獨立產(chǎn)生policy個后代，子代基因從親代完全隨機(jī)獲得，互不影響 190 * @return 生成的子代列表 191 */ 192 public List<Answer> mate(Game game, List<Answer> answerList, int limit, int policy) { 193 int pairNum = limit >> 1; 194 ArrayList<Answer> parentAnswerList = new ArrayList<>(answerList.subList(0, limit)); 195 Collections.shuffle(parentAnswerList); 196 List<Answer> childAnswerList = new ArrayList<>(); 197 for (int pairNo = 0; pairNo < pairNum; pairNo++) { 198 Answer parentAnswer0 = parentAnswerList.get(2 * pairNo); 199 Answer parentAnswer1 = parentAnswerList.get(2 * pairNo + 1); 200 List<Point> parentPointList0 = parentAnswer0.getPointList(); 201 List<Point> parentPointList1 = parentAnswer1.getPointList(); 202 int minLength = Utils.min(parentAnswer0.length(), parentAnswer1.length()); 203 204 if (policy > 0) { 205 // 獨立產(chǎn)生后代，子代基因從親代完全隨機(jī)獲得，互不影響 206 for (int childNo = 0; childNo < policy; childNo++) { 207 int breakPointNum = Utils.max(Utils.randInt(4), 1); 208 List<Integer> matePositionList = new ArrayList<>(); 209 for (int i = 0; i < breakPointNum; i++) { 210 matePositionList.add(Utils.randInt(minLength)); 211 } 212 matePositionList.sort(Integer::compareTo); 213 214 List<Point> childPointList = new ArrayList<>(); 215 int starts = Utils.randInt(2); 216 int lastMatePosition = 0; 217 for (int i = 0; i < breakPointNum + 1; i++) { 218 List<Point> fragmentPointList; 219 List<Point> parentPointList = (i + starts) % 2 == 0 ? parentPointList0 : parentPointList1; 220 if (i < breakPointNum) { 221 int matePosition = matePositionList.get(i); 222 fragmentPointList = parentPointList.subList(lastMatePosition, matePosition); 223 lastMatePosition = matePosition; 224 } else { 225 fragmentPointList = parentPointList.subList(lastMatePosition, parentPointList.size()); 226 } 227 childPointList.addAll(fragmentPointList); 228 } 229 childAnswerList.add(new Answer(childPointList)); 230 } 231 } else { 232 // 對立產(chǎn)生后代，生成2個子代，分別隨機(jī)地獨占親代的基因，親代基因不會丟失 233 int breakPointNum = Utils.max(Utils.randInt(4), 1); 234 List<Integer> matePositionList = new ArrayList<>(); 235 for (int i = 0; i < breakPointNum; i++) { 236 matePositionList.add(Utils.randInt(minLength)); 237 } 238 matePositionList.sort(Integer::compareTo); 239 240 List<Point> childPointList0 = new ArrayList<>(); 241 List<Point> childPointList1 = new ArrayList<>(); 242 int lastMatePosition = 0; 243 for (int i = 0; i < breakPointNum + 1; i++) { 244 // 按照斷點指定的位置，獲得親代基因的碎片 245 List<Point> fragmentPointList0; 246 List<Point> fragmentPointList1; 247 if (i < breakPointNum) { 248 int matePosition = matePositionList.get(i); 249 fragmentPointList0 = parentPointList0.subList(lastMatePosition, matePosition); 250 fragmentPointList1 = parentPointList1.subList(lastMatePosition, matePosition); 251 lastMatePosition = matePosition; 252 } else { 253 fragmentPointList0 = parentPointList0.subList(lastMatePosition, parentPointList0.size()); 254 fragmentPointList1 = parentPointList1.subList(lastMatePosition, parentPointList1.size()); 255 } 256 257 // 拼接親代基因碎片，得到子代基因 258 if (i % 2 == 0) { 259 childPointList0.addAll(fragmentPointList0); 260 childPointList1.addAll(fragmentPointList1); 261 } else { 262 childPointList0.addAll(fragmentPointList1); 263 childPointList1.addAll(fragmentPointList0); 264 } 265 } 266 childAnswerList.add(new Answer(childPointList0)); 267 childAnswerList.add(new Answer(childPointList1)); 268 } 269 } 270 271 // 引入變異 272 for (Answer answer : childAnswerList) { 273 if (Math.random() < variationRate && answer.length() > 0) { 274 int variationType = Utils.max(Utils.randInt(4), 1); 275 int position = Utils.randInt(answer.length()); 276 switch (variationType) { 277 case 1: 278 // 修改一個步驟 279 answer.getPointList().remove(position); 280 // BREAK-THROUGH 281 case 2: 282 // 插入一個步驟，需要遍歷到當(dāng)前為止的棋盤狀態(tài)，然后隨機(jī)插入一個合法的位置 283 int[][] arr = game.getInitArr(); 284 for (int i = 0; i < position; i++) { 285 Point point = answer.getPointList().get(i); 286 if (arr[point.getX()][point.getY()] <= 0) { 287 continue; 288 } 289 // 記錄本次操作的結(jié)果，并更新棋盤狀態(tài) 290 MoveResult move = Game.move(arr, point); 291 arr = move.getArr(); 292 } 293 List<Point> remainPointList = Game.availablePoints(arr, 0); 294 if (!remainPointList.isEmpty()) { 295 Point point = remainPointList.get(Utils.randInt(remainPointList.size())); 296 answer.getPointList().add(position, point); 297 } 298 break; 299 case 3: 300 // 刪除一個步驟 301 answer.getPointList().remove(position); 302 break; 303 } 304 } 305 calcTotalReward(game, answer); 306 } 307 return childAnswerList; 308 } 309 310 /** 311 * 從隨機(jī)位置斬斷一個解，之后部分隨機(jī)生成 312 * 313 * @param game 游戲 314 * @param answer 解答 315 * @return 生成的新解答 316 */ 317 public Answer randomCut(Game game, Answer answer) { 318 int saveLength = Utils.randInt(answer.length()); 319 List<Point> savePointList = answer.getPointList().subList(0, saveLength); 320 Answer newAnswer = new Answer(savePointList); 321 calcTotalReward(game, newAnswer); 322 return newAnswer; 323 } 324 325 /** 326 * 驗證解答，并計算總獎勵 327 * 如果解答序列不完整，則隨機(jī)生成之后序列，使其補(bǔ)充完整。 328 * 329 * @param game 游戲 330 * @param answer 答案 331 * @return 總獎勵 332 */ 333 public static int calcTotalReward(Game game, Answer answer) { 334 int totalReward = 0; 335 int minReward = 0; 336 int burstCount = 0; 337 int[][] arr = game.getInitArr(); 338 339 // 遍歷已有點的列表，驗證并計算結(jié)果 340 List<Point> pointList = new ArrayList<>(answer.getPointList()); 341 for (Point point : answer.getPointList()) { 342 if (arr[point.getX()][point.getY()] <= 0) { 343 // 這個點已經(jīng)被清空了，因此跳過它，將其從列表中刪除 344 pointList.remove(point); 345 continue; 346 } 347 348 // 記錄本次操作的結(jié)果，并更新棋盤狀態(tài) 349 MoveResult move = Game.move(arr, point); 350 arr = move.getArr(); 351 totalReward += move.getReward(); 352 if (minReward > totalReward) { 353 minReward = totalReward; 354 } 355 if (move.getCombo() > 0) { 356 burstCount++; 357 } 358 } 359 360 // 檢查是否棋盤未被清空，是的話則隨機(jī)生成之后的解答 361 List<Point> remainPointList = Game.availablePoints(arr, 0); 362 while (!remainPointList.isEmpty()) { 363 Point point = remainPointList.get(Utils.randInt(remainPointList.size())); 364 pointList.add(point); 365 366 // 記錄本次操作的結(jié)果，并更新棋盤狀態(tài) 367 MoveResult move = Game.move(arr, point); 368 arr = move.getArr(); 369 totalReward += move.getReward(); 370 if (minReward > totalReward) { 371 minReward = totalReward; 372 } 373 if (move.getCombo() > 0) { 374 burstCount++; 375 } 376 377 remainPointList = Game.availablePoints(arr, 0); 378 } 379 380 // 追加完美通關(guān)獎勵 381 if (burstCount <= 1) { 382 totalReward += Game.REWARD_PFT; 383 } 384 385 answer.getPointList().clear(); 386 answer.getPointList().addAll(pointList); 387 answer.setBurstCount(burstCount); 388 answer.setTotalReward(totalReward); 389 answer.setMinReward(minReward); 390 return totalReward; 391 } 392 393 public static void sortAnswerList(List<Answer> answerList) { 394 answerList.sort(Comparator.comparing(Answer::getTotalReward).reversed().thenComparing(Answer::getBurstCount).thenComparing(Answer::length)); 395 } 396 }
計算出的結(jié)果最終打印到控制臺中。
?
實際用于解決該游戲后，發(fā)現(xiàn)了以下現(xiàn)象與問題：
1、最優(yōu)解幾乎總是先在棋盤上設(shè)置大量小水滴，之后一把將其全部引爆。
2、最優(yōu)解如果直接打印，很多在同一個單元格的操作不放在一起，增加操作難度，比如一不小心點錯單元格。
3、不是每次都能找到最優(yōu)解，有的最優(yōu)解出現(xiàn)概率很低，需要多次執(zhí)行確認(rèn)。
4、直接照著盤面改Array太麻煩了。
最終，我采取了以下措施：
1、輸出解時。將一組不引爆水珠的一系列操作合并，增加一個次數(shù)參數(shù)。
2、將執(zhí)行入口設(shè)置為了允許并發(fā)運行。一般同時執(zhí)行3個實例，若找到的解的收益不同，則再執(zhí)行幾個看看。
3、我寫了個程序，輔助將盤面錄入為Array，以便粘貼。
1 package main; 2 3 import java.util.Scanner; 4 5 public class FormatArray { 6 public static void main(String[] args) { 7 System.out.println("粘貼純數(shù)字格式，獲得格式化的Array對象。注意最后需要多加一個空行。"); 8 Scanner scanner = new Scanner(System.in); 9 while (scanner.hasNext()) { 10 String line = scanner.next(); 11 char[] chars = line.toCharArray(); 12 StringBuilder builder = new StringBuilder(); 13 builder.append("{"); 14 for (int i = 0; i < chars.length; i++) { 15 builder.append(chars[i]); 16 if (i < chars.length - 1) { 17 builder.append(", "); 18 } 19 } 20 builder.append("},"); 21 System.out.println(builder.toString()); 22 } 23 } 24 }
?
如有興趣，可以下載源文件：https://pan.baidu.com/s/1iWNIkNLUXDDadNLlaerIHg?pwd=bili
?
參考資料：文章來源：http://www.zghlxwxcb.cn/news/detail-828254.html
《也談十滴水-啟發(fā)式搜索》https://www.cnblogs.com/ComputingLife/archive/2010/09/19/1830873.html文章來源地址http://www.zghlxwxcb.cn/news/detail-828254.html
到了這里，關(guān)于Java使用遺傳算法，尋找十滴水問題的最優(yōu)解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
