回溯算法設計技術定義

Question

我正在閱讀回溯算法設計技術。提到如下。

回溯是蠻力的方法，其中 系統地搜索所有可用的 選項中解決問題的改進。它通過假定解決方案是通過值的向量（v1，v2，...，vm）以及通過遍歷 以深度優先方式表示的 來實現的，向量的域直到找到解決方案。

我在上面的文本中的quesitons如下。

1. 作者用解決方案表示的意思是由矢量表示的嗎？

2. 作者是什麼意思的矢量域？

感謝您的澄清。

Answer 1

讓我們以八皇后問題爲例。

該解決方案是8個職位的矢量，每個女王1。矢量屬於空間：([0,7]x[0,7])^8。這是一個非常大的空間，所以回溯算法將使用條件：'沒有女王應該檢查另一個女王'，限制到解決方案向量存在的較小'域'（子空間([0,7]x[0,7])^8）。

在這種情況下，該算法將通過嘗試第一個女王的允許值之一創建一個解矢量，給出矢量：[ (0,0), X, X, X ...]。然後使用條件它將限制第二個位置應被搜索的子空間，並繼續這樣做直到它找到合適的向量。

深度優先意味着移動到域的溶液[ (0,1), X, X, X ...]算法將排出從所定義的域的所有潛在的載體由[ (0,0), X, X, X ...]

之前