回溯
回溯法的基本思想：回溯法在包含問題的所有可能解的解空間樹中，從根結(jié)點(diǎn)出發(fā)虱黄，按照深度優(yōu)先的策略進(jìn)行搜索橱乱，對于解空間樹的某個結(jié)點(diǎn)泳叠，如果該結(jié)點(diǎn)滿足問題的約束條件，則進(jìn)入該子樹繼續(xù)進(jìn)行搜索宗挥，否則將以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹進(jìn)行剪枝契耿。
回溯法的算法框架按照問題的解空間一般分為子集樹算法框架與排列樹算法框架螃征。
當(dāng)給定的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時盯滚，相應(yīng)的解空間樹稱為子集樹魄藕。
當(dāng)給定的問題是確定 n 個元素滿足某種性質(zhì)的排列時背率，對應(yīng)的解空間樹稱為排列樹嫩与；排列樹通常有n!個葉子結(jié)點(diǎn)蕴纳。
回溯法解題的關(guān)鍵要素：
- 針對給定的問題个粱，定義問題的解空間
- 確定易于搜索的解空間結(jié)構(gòu)
- 以深度優(yōu)先方式搜索解空間古毛，并且在搜索過程中用剪枝函數(shù)避免無效搜索
1. 迷宮回溯問題
import java.util.Random;
// 迷宮回溯問題
public class MazeBack {
public static void main(String[] args) {
// 先創(chuàng)建一個二維數(shù)組都许，模擬迷宮地圖
int[][] map = new int[9][9];
layoutMaze(map, 9); // 給迷宮布局
// 使用遞歸回溯找通路
boolean success = setWay(map, 1, 1);
if (success)
System.out.println("找到通路：");
else
System.out.println("沒有通路：");
display(map); // 顯示地圖
}
/**
* 從左上角開始出發(fā)稻薇，右下角為終點(diǎn)
* 0表示沒走過；1表示墻胶征；2表示通路睛低；3表示已經(jīng)走過但走不通
* 尋路策略：下-->右-->上-->左钱雷，如果走不通拉庵，再回溯
*
* @param map 表示地圖
* @param i 表示起始位置
* @param j 表示從起始位置
* @return 如果找到通路钞支，則返回true烁挟，否則返回false
*/
public static boolean setWay(int[][] map, int i, int j) {
if (map[map.length - 2][map[0].length - 2] == 2) {
// 遞歸終止條件撼嗓，通路已經(jīng)找到
return true;
} else if (map[i][j] == 0) { // 如果當(dāng)前這個點(diǎn)還沒走過
map[i][j] = 2; // 假定該點(diǎn)可以走通
if (setWay(map, i + 1, j)) { // 向下走
return true;
} else if (setWay(map, i, j + 1)) { // 向右走
return true;
} else if (setWay(map, i - 1, j)) { // 向上走
return true;
} else if (setWay(map, i, j - 1)) { // 向左走
return true;
} else { // 該點(diǎn)走不通警没，是死路
map[i][j] = 3;
return false;
}
} else {
// 1：走不通
// 2：走過了，不用再走
// 3：走過了走不通
// 因此如果map[i][j] != 0亡脸，說明該點(diǎn)不用走大州，直接返回false
return false;
}
}
// 初始化地圖
public static void initMap(int[][] map) {
for (int r = 0; r < map.length; r++) {
for (int c = 0; c < map[0].length; c++) {
// 將地圖四周設(shè)為1
if (r == 0 || r == map.length - 1 || c == 0 || c == map[0].length - 1)
map[r][c] = 1;
else
map[r][c] = 0;
}
}
}
// 給迷宮布局
public static void layoutMaze(int[][] map, int total) {
initMap(map); // 先初始化地圖
for (int i = 0; i < total; i++) {
Random random = new Random();
int r = random.nextInt(map.length - 2) + 1;
int c = random.nextInt(map[0].length - 2) + 1;
map[r][c] = 1;
}
}
// 顯示地圖
public static void display(int[][] map) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
}
2. 八皇后問題
八皇后問題遞歸思路：
- 第一個皇后先放第一列第一行
- 第二個皇后放第二行第一列滥朱，然后判斷是否OK徙邻，如果不OK缰犁，繼續(xù)放第二列帅容、第三列...依次把所有列放完夯到，找到一個合適的耍贾。
- 繼續(xù)放第三個皇后荐开，還是第一列晃听、第二列...直到第8個皇后也放在一個不沖突的位置，算找到了一個正確解初斑。
- 當(dāng)?shù)玫揭粋€正確解時见秤，在椇醭危回退到上一個棧時置济，就開始回溯舟肉，即得到第一個皇后放在第一列的所有正確解路媚。
- 然后回頭繼續(xù)第一個皇后放第二列，后面繼續(xù)循環(huán)執(zhí)行1裤园，2拧揽，3，4步驟铡羡。
- 理論上應(yīng)該創(chuàng)建一個二維數(shù)組表示棋盤，但實(shí)際上通過算法读慎，用一個一維數(shù)組即可(下標(biāo)為行，值為列)闰靴。
八皇后問題實(shí)現(xiàn)：
import java.util.Arrays;
// 八皇后問題遞歸實(shí)現(xiàn)
public class NQueens {
static int max = 8; // 一共有幾個皇后
static int[] arr = new int[max]; // 保存一個結(jié)果
static int total = 0;
static int judgeCount = 0;
public static void main(String[] args) {
check(0);
System.out.println(max + "個皇后解法：" + total); // 92
System.out.println("判斷次數(shù)：" + judgeCount); // 15720
}
// 放置第n個皇后
public static void check(int n) {
if (n == max) {
// max個皇后已經(jīng)放好，顯示結(jié)果
total++;
System.out.println(Arrays.toString(arr));
return;
}
// 依次放入皇后，并判斷是否沖突
for (int i = 0; i < max; i++) {
// 先把當(dāng)前皇后n放到該行第一列
arr[n] = i;
// 判斷第n個皇后在i位置是否沖突
if (Conflict(n) == false) { // 不沖突
// 接著放n+1個皇后淑翼，即開始遞歸
check(n + 1);
}
// 如果沖突，繼續(xù)循環(huán)遭京，將第n個皇后后移一列
}
}
// 檢測第n個皇后是否與已擺放的皇后沖突
public static boolean Conflict(int n) {
judgeCount++;
for (int i = 0; i < n; i++) {
// 檢測是否在同一列或同一斜線(正方形長寬相等)
if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i]))
return true;
}
return false;
}
}
3. 馬踏棋盤問題
馬踏棋盤問題也稱騎士周游問題，是旅行商問題(TSP)或哈密頓回路問題(HCP)的一個特例。在8×8的國際象棋棋盤上堡僻，用一個馬跟隨馬步跳遍整個棋盤，要求每個格子都只跳到一次，最后回到出發(fā)點(diǎn)咨油。這是一個NP問題，通常采用回溯法或啟發(fā)式搜索類算法轉(zhuǎn)化棉胀。
馬踏棋盤問題解決思路：
- 將當(dāng)前位置設(shè)置為已經(jīng)訪問，然后根據(jù)當(dāng)前位置霎挟，計算還能走哪些位置赐纱，并將這些位置放入到一個集合中；最多有8個位置起胰，每走一步就讓step增1
- 遍歷集合中存放的所有位置，看哪個可以走通；如果走通瓜客，就繼續(xù)，走不通，就回溯
- 使用step和應(yīng)該走的步數(shù)比較，來判斷應(yīng)該走的步數(shù)是否走完了砂吞；若不相等，則將整個棋盤置0
- 不同的走法(策略)呼巷，得到的結(jié)果可能不同，效率也會有影響(可優(yōu)化)
馬在當(dāng)前位置可以踏的位置：
import java.awt.*;
import java.util.ArrayList;
import java.util.List;
public class Backtracking {
static int x = 8; // 棋盤行
static int y = 8; // 棋盤列
static int[][] chessboard = new int[x][y]; // 棋盤
static boolean[] visited = new boolean[x * y]; // 標(biāo)記棋盤的各個位置是否訪問過
static boolean finished = false; // 應(yīng)該走的步數(shù)是否走完了
// 回溯法解決馬踏棋盤問題
public static void knightTour(int row, int column, int step) {
// 第step步訪問該位置
chessboard[row][column] = step;
// 將該位置標(biāo)記為已訪問
visited[row * x + column] = true;
// 根據(jù)當(dāng)前位置，計算還能走哪些位置
List<Point> next = next(new Point(column, row));
/**
* 對next按照可走步數(shù)進(jìn)行升序排序，減少回溯的次數(shù)：
* 不同的走法(策略)，得到的結(jié)果可能不同
* 貪心選擇策略：選擇可走步數(shù)最少的位置
*/
next.sort(((o1, o2) -> next(o1).size() - next(o2).size()));
// 遍歷每一個還能走哪些位置
for (Point point : next) {
// 如果該位置還沒有被訪問，則訪問這個位置
if (!visited[point.y * x + point.x])
knightTour(point.y, point.x, step + 1);
}
// 判斷棋盤是否踏完傻工，如果沒踏完，將整個棋盤置0
// step < x * y - 1有兩種情況：1. 棋盤還沒踏完 2. 棋盤正在回溯
if (step < x * y - 1 && !finished) {
chessboard[row][column] = 0;
visited[row * x + column] = false;
} else {
finished = true;
}
}
// 根據(jù)當(dāng)前位置(Point為Java的內(nèi)置對象)，計算還能走哪些位置，最多有8個位置
// 返回還能走的位置的坐標(biāo)集合
private static List<Point> next(Point current) {
List<Point> points = new ArrayList<>();
Point point = new Point();
// 可以走0這個位置
if ((point.x = current.x + 2) < x && (point.y = current.y - 1) >= 0)
points.add(new Point(point));
// 可以走1這個位置
if ((point.x = current.x + 2) < x && (point.y = current.y + 1) < y)
points.add(new Point(point));
// 可以走2這個位置
if ((point.x = current.x + 1) < x && (point.y = current.y + 2) < y)
points.add(new Point(point));
// 可以走3這個位置
if ((point.x = current.x - 1) >= 0 && (point.y = current.y + 2) < y)
points.add(new Point(point));
// 可以走4這個位置
if ((point.x = current.x - 2) >= 0 && (point.y = current.y + 1) < y)
points.add(new Point(point));
// 可以走5這個位置
if ((point.x = current.x - 2) >= 0 && (point.y = current.y - 1) >= 0)
points.add(new Point(point));
// 可以走6這個位置
if ((point.x = current.x - 1) >= 0 && (point.y = current.y - 2) >= 0)
points.add(new Point(point));
// 可以走7這個位置
if ((point.x = current.x + 1) < x && (point.y = current.y - 2) >= 0)
points.add(new Point(point));
return points;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
knightTour(0, 0, 0);
long end = System.currentTimeMillis();
System.out.println("馬踏棋盤耗時" + (end - start) + "毫秒，結(jié)果為：");
for (int r = 0; r < chessboard.length; r++) {
for (int c = 0; c < chessboard[r].length; c++) {
System.out.printf("%4d", chessboard[r][c]);
}
System.out.println();
}
}
}
