Ch05. Backtracking

# Backtracking

Backtracking，枚舉多維度數值的方法。
運用遞迴依序窮舉各個維度的數值，製作所有可能的多維度數值，並且在遞迴途中避免枚舉不正確的多維度數值。
Backtracking is a modified depth-first search of a tree (DFS).

# Promising₁ & Nonpromising

• A node is Nonpromising if it cannot possibly lead to a solution.
• Otherwise, Promising.

# Pruning₂

• Backtracking consists of
  • doing a DFS of a State Space Tree
  • checking whether each node is promising
  • if it is nonpromising, backtracking to the node’s parent.
• Pruned State Space Tree: the subtree consisting of the visited nodes (after pruning).

# n-Queens Problem (n 皇后問題)

n 皇后問題的目標在於，在一個 n*n 大小的棋盤上擺放 n 個皇后，要讓他們恰好無法互相攻擊對方 (no two queens threaten each other)。也就是說，任何一個皇后都要在不同行 (row)、不同列 (column) 且不同斜線 (diagonal) 上。

# 想法

• 以 4*4 的棋盤為例:

我們可以很直覺地想到，任何一個皇后不會在同一個列上 (row)。
因此，這個問題可以簡化成，什麼樣的行 (column) 組合能符合題目的要求。
因為每個皇后都有 4 個選擇，所以我們總共有 $4 \times 4 \times 4 \times 4 = 256$ 種可能的組合。我們可以建立一個樹來表達所有的組合。

為了更有效率的搜尋解答，我們可以設置一些條件來篩選掉那些不可能的路徑。
同上例子:

• 我們知道，沒有兩個皇后可以在同一行上。假設我們已將 皇后1 放在第一行上 (<1, 1>)，之後就不可再有人可以放在第一行上，因此當我們遇到 <2, 1> 時就可以直接跳過。
• 同樣的，沒有兩個皇后可以在同一個對角線上。所以遇到 <2, 2> 時，我們就可以不用再去管它後面的路徑了。

# Pruning

1. <1, 1> is promising.
2. <2, 1> is nonpromising. {because queen 1 is in column 1}
   <2, 2> is nonpromising. {because queen 1 is on left diagonal}
   <2, 3> is promising.
3. < 3, 1> is nonpromising {because queen 1 is in column 1}
   < 3, 2> is nonpromising {because queen 2 is on right diagonal}
   < 3, 3> is nonpromising {because queen 2 is in column 3}
   < 3, 4> is nonpromising
4. Backtrack to <1, 1>
   <2, 4> is promising
5. < 3, 1> is nonpromising {because queen 1 is in column 1}
   < 3, 2> is promising {this is the second time we’ve tried < 3, 2>}

這裡顯示經過 backtracking 後部分的 pruned state space tree

# Promising Function

Check whether two queens are in the same column or diagonal.

• let col(i) be the column where the queen in the ith row is located, then to check whether the queen in the kth row is in the same column.

• to check the diagonal, suppose n=8 . In the following figure, the queen in row 6 is being threatened in its left diagonal by the queen in row 3, and in its right diagonal by the queen in row 2.

# Sum-of-Subset Problem

There are n positive integers (weights) wi and a positive integer W .
The goal is to find all subsets of the integers that sum to W .

# Promising Function

If we sort the weights in ascending order before doing the search, then w_i+1 is the lightest weight remaining when we are at the ith level.

Let weight be the sum of the weights that have been included up to a node at level i.
If w_i+1 would bring the value of weight above W, then so would any other weight following it.

There is another, if, at a given node, adding all the weights of the remaining items to weight does not make weight at least equal to W, then weight could never become equal to W by expanding beyond the node.

# Pruned State Space Tree

Supppose that n = 4 , W = 13 , and w1 = 3 , w2 = 4 , w3 = 5 , w4 = 6 .

• weight + w_(i+1) > W : The nodes containing 12, 8, and 9 are nonpromising because adding the next weight (6) would make the value of weight exceed W.
• weight + total < W : The nodes containing 7, 3, 4 and 0 are nonpromising because there is not enough total weight remaining to bring the value of weight up to W.

# Graph Coloring

Find all ways to color an undireccted graph using at most m different colors so that no two adjacent vertices are the same color.

# Example

• There is no solution to the 2-Coloring graph problem.
• One solution to the 3-Coloring graph problem for this graph is following:

Vertex	Color
v1	color 1
v2	color 2
v3	color 3
v4	color 2

# Planar Graph

A graph is called planar if it can be drawn in a plane in such a way that no two edges cross each other.

• For every map, there corresponds a planar graph.
  

# Pruned State Space Tree

# Hamiltonian Circuit

Find a path that visits each vertex exactly once and then return to the starting vertex.

• Similar to TSP (Traveling Salesman Problem) except that Hamiltonian Circuits Problem is only to find all tours in an undirected and unweighted graph.

• DP is inefficient for large TSP instance.

# Example

• (a) contains the Hamiltoniac Circuit [v1, v2, v8, v7, v6, v5, v4, v3, v1]
• (b) does not contain a Hamiltonian Circuit

# Promising Function

• the ith node is adjacent to the (i+1)th node
• the (n-1)th node is adjacent to the 0th node
• the ith node cannot be in the first i-1 nodes

# 0-1 Knapsack Problem

• profit: the sum of the profits of the items included up to the node.
• weight: the sum of the weights of those items.
• Suppose the node is at level i, and the node at level k is the one that would bring the sum of the weights above W. Then,
  • totweight = weight + $\sum_{j=i+1}^{k-1}w_j$
  • bound = (profit + $\sum_{j=i+1}^{k-1}p_j$) + (W - totweight) $\times$ $p_k/w_k$

# Promising Function

If maxprofit is the value of the profit in the best solution found so far, then a node at level i is nonpromising if $bound \le maxprofit$.

# Example

Suppose that n = 4 , W = 16 , and we have the following:

Nonpromising node:
node(3, 1)

1. Compute its profit and weight .
   • profit = 70 + 50 = 120
   • weight = 7 + 10 = 17
2. Because its weight = 17 is greater than W = 16 , maxprofit does not change.
3. Determine that it is nonpromising because its weight = 17 is greater than or equal to W = 16 .
4. The bound for this node is not computed, because its weight has determined it to be nonpromising
5. Backtrack to node(2, 1).

node(4, 1)

1. Compute its profit and weight .
   • profit = 80 + 0 = 80
   • weight = 7 + 5 = 12
2. Because its weight = 12 is less than W = 16 , and its profit = 80 is greater than maxprofit = 70 , set maxprofit = 80 .
3. Compute its bound . The fourth weight would not bring the sum of the items above W , and there are only four items. Therefore, k = 5 , and bound = 80 + 0 = 80 .
4. Determine that it is nonpromising because its bound = 80 equal to maxprofit = 80 .
5. Backtrack to node(3, 2).

node(4, 2)

1. Compute its profit and weight .
   • profit = 70 + 0 = 70
   • weight = 7 + 0 = 7
2. k = 5 , bound = 70 + 0 = 70 .
3. Determine that the node is nonpromising because its bound = 70 is less than maxprofit = 80 .
4. Backtrack to node(1, 1)

# 註解

1. promising 有希望的；有出息的；有前途的

Something that is promising shows signs that it is going to be successful or enjoyable.
ex. They won the award for the most promising new band of the year.

2. prune v.

• 修剪（樹枝）
  To cut off branches from a tree, bush, or plant, especially so that it will grow better in the future.
  ex. She spent the afternoon pruning roses.
• 刪除，刪節
  To reduce something by removing things that are not necessary.
  ex. I felt his essay needed a little pruning.

3. state space tree 狀態空間樹

選定一個狀態，衍生各式各樣的狀態，形成一棵樹。狀態空間樹無窮無盡。狀態可能重複出現、四處散布。