Backtracking [Guide]

Правка en3, от AlRntn, 2024-07-19 11:48:06

Backtracking: This algorithm helps you solve problems in a specific way using your skills in recursive programming. It comes in handy whenever you have a set of valid answers to a problem and need to search through them all or construct a suitable answer, this algorithm is a general algorithm for finding all or some solutions in some computational problems. The backtracking method is an algorithmic method to solve some kind of problems in which we need to build and examine all possible situations or a number of good situations of an arrangement(combination), in this algorithm all possible situations are created , and after examining each one, if it is approved based on the request of the problem we will accept it as a answer(kind of like brute force we find each possible combination). Note that this method is useful when we cant use a faster algorithm(like: Greedy or Dp).

the General Backtracking Method is like this(pseudocode):

solve(X):
if X is accepted:
   X is answer
   exit
while we can change X:
   change X
   if X is valid:
      solve(X)
   undo last change from X

The base of the algorithm is in 4 parts: the condition of finding the answer (lines 1 to 3) — finding all the different states of the answer (lines 4 to 6) — recursive call (line 7) — return the last change made (line 8).

Some Backtracking Problems:

1-Print all strings of length n that are made only of letters a, b, and c.

The Answer

2-A horse is in the cell (0,0) in a n*n chessboard. That is, in the upper-left corner, you have to say the number of cells that the horse can reach with exactly k moves.

The Answer

3-476B - Dreamoon and WiFi

The Answer
Теги backtracking, #backtracking

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский AlRntn 2024-07-20 16:21:11 1 Tiny change: 'cn_with_studio(false)' -> 'cn_with_stdio(false)'
en3 Английский AlRntn 2024-07-19 11:48:06 4 Tiny change: ' cout << ‘\n’;\n}\nvoid' -> ' cout << "\n";\n}\nvoid'
en2 Английский AlRntn 2024-07-18 20:24:43 54
en1 Английский AlRntn 2024-07-12 18:02:34 5036 Initial revision (published)