回溯算法和貪心算法

回溯算法 (Backtracking Algorithms)

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems. It incrementally builds candidates to the solutions, and abandons each partial candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

回溯是一種通用算法，用于查找某些計算問題(尤其是約束滿足問題)的所有(或某些)解決方案。 它逐步為解決方案構建候選對象，并在確定候選對象不可能完成有效的解決方案后立即放棄每個部分候選對象(“回溯”) 。

示例問題(騎士的旅行問題) (Example Problem (The Knight’s tour problem))

The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once.

騎士被放置在一個空棋盤的第一塊上，并且根據國際象棋的規則移動，必須對每個廣場精確地訪問一次。

騎士走過的路覆蓋了所有牢房 (Path followed by Knight to cover all the cells)

Following is chessboard with 8 x 8 cells. Numbers in cells indicate move number of Knight.

以下是帶有8 x 8格的棋盤。 單元格中的數字表示騎士的移動次數。

騎士之旅的樸素算法 (Naive Algorithm for Knight’s tour)

The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints.

樸素算法是一一生成所有巡視，并檢查生成的巡視是否滿足約束條件。

while there are untried tours
{ generate the next tour if this tour covers all squares { print this path;}
}

騎士之旅的回溯算法 (Backtracking Algorithm for Knight’s tour)

Following is the Backtracking algorithm for Knight’s tour problem.

以下是騎士巡回問題的回溯算法。

If all squares are visited print the solution
Elsea) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step).b) If the move chosen in the above step doesn't lead to a solutionthen remove this move from the solution vector and try other alternative moves.c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" )

翻譯自: https://www.freecodecamp.org/news/backtracking-algorithms-explained/

回溯算法和貪心算法