Back-tracking設計技術的一般定義

Question

我正在閱讀Anany Levtin的算法設計和分析簡介中的跟蹤算法設計技術。

我很難理解反向跟蹤算法的通用定義，並將其映射到4皇后問題。

爲了從更一般的 透視回溯算法設計技術，最回溯算法符合下列 描述。

一個回溯算法的輸出可被認爲是n元組 （X1，X2，X3，...，xn）映射，其中每個座標xi是一些 有限線性有序集Si的元素。例如，對於n皇后 問題，每個Si是整數1到n的集合。元組可能需要滿足一些額外的約束條件（例如，在n皇后問題中的非攻擊性需求）。

例如，對於4王后問題每個Si的集合{1，2​​，3，4}

甲反向跟蹤算法生成顯式或implicityly，一個 狀態空間樹，其節點代表部分構造元組 具有由 算法的早期動作定義的第一個「i」座標。如果這樣的元組（x1，x2，x3，... xi）不是解，則算法找出Si + 1中與（x1，x2，x3 ... xi）的值 一致的下一個元素，和問題約束，並將其作爲其（i + 1）st座標添加到元組中。如果這樣的元素不存在，算法回溯考慮xi的下一個值，以及 等等。

我上面的文字問題是

1. 什麼是筆者的「背跟蹤算法生成明示或implicityly，狀態空間樹，它的節點代表部分地與第一構造元組的意思如果這樣一個元組（x1，x2，x3，... xi）不是一個解，那麼算法會在Si + 1中找到下一個元素 ，它與（x1，x2，x3 ... xi）的值以及問題約束，並將其作爲第（i + 1）個座標添加到元組中。「 ？

   具體來說，算法作者所指的是Si + 1中的下一個元素？

   請用四皇后問題解釋上述說法。

2. 如果元素不存在，算法回溯到考慮xi的下一個值？請用4皇后問題來解釋這個問題。

謝謝！

Answer 1

這種回溯的解釋確實很難遵循，因爲它使用了很多正式的符號，它並沒有用於特定的目的或證明。讓我試着用一種不太正式的方式來解釋它，這是一個很好的例子：

在回溯過程開始時，板子是空的。這是狀態空間樹的根。這個根有子節點，每個可能的位置我們可以放第一個女王。我們在進入下一級之前（這將導致狀態空間樹的BFS），而不是構造每個子節點，我們爲第一個皇后選擇一個可能的位置，從而構造一個子節點。從這個子節點我們有多個選項來放置第二個女王，所以我們選擇一個，依此類推。

如果我們到達了我們沒有可能放置剩餘女王的節點，我們回溯 - 我們上升到該節點父節點的一個水平，並檢查是否還有我們尚未探索的剩餘可能性。如果是，我們通過創建相應的子節點來探索它們，如果沒有我們再次回溯，再往上一級，直到我們找到問題的解決方案（所有皇后被放置）或者我們擴展了根節點的所有孩子併到達回溯操作期間的根節點 - 這意味着沒有解決方案。