設(shè)計思想：

(1)適用：求解搜索問題和優(yōu)化問題。

(2)搜索空間：數(shù)，節(jié)點對應(yīng)部分解向量，可行解在樹葉上。

(3)搜索過程：采用系統(tǒng)的方法隱含遍歷搜索樹。

(4)搜索策略：深度優(yōu)先，寬度優(yōu)先，函數(shù)優(yōu)先，寬深結(jié)合等。

(5)結(jié)點分支判定條件：

滿足約束條件----分支擴張解向量

不滿足約束條件----回溯到該節(jié)點的父節(jié)點

經(jīng)典算法

N皇后

class Solution {

List> res = new ArrayList<>();

List curr = new ArrayList<>();

int[][] tag;

int n;

public List> solveNQueens(int n) {

this.n = n;

tag = new int[n][n];

backtrace(0);

return res;

}

private void backtrace(int level) {

if (level == this.n) {

res.add(new ArrayList<>(curr));

}else{

StringBuilder sb = new StringBuilder();

for (int i = 0; i < this.n; i++) {

if (tag[level][i] == 0) {

addTag(level, i);

sb.append("Q");

int col = i;

while (++col < n) sb.append(".");

} else {

sb.append(".");

continue;

}

curr.add(sb.toString());

backtrace(level + 1);

curr.remove(curr.size() - 1);

removeTag(level, i);

sb = new StringBuilder(sb.substring(0, i));

sb.append(".");

}

}

}

public void addTag(int row, int col) {

int le = row;

while (le < n) tag[le++][col]++;//該列

le = row + 1;

int x = col + 1;

while (le < n && x < n) tag[le++][x++]++;//右下角

le = row + 1;

x = col - 1;

while (le < n && x >= 0) tag[le++][x--]++;//左下角

}

;

public void removeTag(int row, int col) {

int le = row;

while (le < n) tag[le++][col]--;//該列

le = row + 1;

int x = col + 1;

while (le < n && x < n) tag[le++][x++]--;//右下角

le = row + 1;

x = col - 1;

while (le < n && x >= 0) tag[le++][x--]--;//左下角

}

}

總結(jié)

以上是生活随笔為你收集整理的回溯 皇后 算法笔记_算法笔记_04_回溯的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。