解釋BFS和DFS在回溯

Question

維基百科關於深度優先搜索方面：

深度優先搜索（DFS）是一種 算法遍歷或搜索 一棵樹，樹結構或圖形。其中一個 從根開始（選擇一些 節點作爲圖例中的根） 並在回溯之前儘可能沿着每個分支探索 。

那麼什麼是廣度優先搜索？

「那些選擇起始 節點的算法，檢查所有節點回溯， 選擇最短的路徑，選擇鄰居節點回溯， 選擇最短的路徑，最後 發現，因爲最佳路徑的 遍歷每個路徑由於連續 回溯。

正則表達式find的修剪 - 回溯？

術語回溯由於其多種用途而混淆。 UNIX的find修剪一個SO用戶，用回溯來解釋。如果你不限制Regexes的範圍，Regex Buddy使用術語「災難性的回溯」。這似乎是一個過於廣泛使用的總稱。所以：

1. 如何爲圖論定義「回溯」？
2. 什麼是廣度優先搜索和深度優先搜索中的「回溯」？

[新增]

約回溯良好定義和例子

1. The Brute-force method
2. Stallman的（？）發明了長期"dependency-directed backtracking"
3. 回溯和regex例如
4. Depth First Search definition.

Answer 1

混淆的來源，因爲回溯一些搜索過程中發生，但它也指的是一個具體的解決問題的技術，其中很多回溯的完成。這樣的程序被稱爲回溯。

駕駛車輛進入附近的圖片，總是先看到第一個回合（讓我們假設沒有迴路），直到你死亡，然後開車回到下一個未被訪問的街道的交叉點。這是「第一」類型的回溯，這大致相當於該詞的口語使用。

更具體的用法是指類似於深度優先搜索的問題解決策略，但是當它意識到不值得繼續下去某個子樹時回退。

換句話說 - 一個天真的DFS會盲目地訪問每個節點，直到達到目標。是的，它在葉節點上「回溯」。但一個回溯追蹤器也回溯在無用的分支。其中一個例子是在Boggle董事會搜尋文字。每個瓷磚被8個其他瓷磚包圍，所以樹很大，天真的DFS可能需要很長時間。但是當我們看到像「ZZQ」這樣的組合時，我們可以安全地停止從這一點開始搜索，因爲添加更多的字母不會成爲一個單詞。

我喜歡Julie Zelenski教授的這些講座。她解決了8個皇后，一個數獨謎題和一個使用回溯的數字替代謎題，並且一切都很好地動畫。 Programming Abstractions, Lecture 10 Programming Abstractions, Lecture 11

樹是一個圖，其中任意兩個頂點只有它們之間的一個路徑。這消除了循環的可能性。當你搜索圖表時，你通常會有一些邏輯消除循環，所以行爲是一樣的。另外，對於有向圖，您不能沿着「錯誤」的方向跟蹤邊緣。

從我所知道的，在Stallman論文中，他們開發了一個邏輯系統，它不僅在查詢中表示「是」或「否」，而且通過進行最小數量的更改建議修正錯誤查詢。你可以看到回溯的第一個定義可能會發揮作用。