7. 1. Backtracking
An algorithm that takes into account the number of all cases. This is the appropriate way to represent the state space as a tree. It may be considered a kind of tree search algorithm. Depth First Search (DFS), Breadth First Search (BFS), and Best First Search / Heuristic Search. It is advantageous to be able to knit without a brain.
If you have to consider the number of cases in all cases, DFS is better. Implementation is possible with BFS, but the size of the queue increases dramatically when implemented with BFS. Even speed is the same. Therefore, finding the number of cases is generally convenient for DFS. Most of the problems are answered by using DFS. And it will take a long time.
However, there are times when DFS should never be used, when the depth of the tree becomes infinite. If a loop occurs in finding a maze, the DFS will not be able to escape the branch. Of course, you can put a device to prevent duplicate inspection, but BFS is convenient for that. The advantage of backtracking is that you can solve without thinking … You can also die without a breakpoint. If you see long lengths, stack overflow can occur. Daze is slow if the above maze search has 4 points (or 8 directions) when it comes to the last entering direction. And it is convenient to use BFS in finding the shortest distance.
§ DFS (Depth First Search)
DFS is a way to go from one side of the tree representing the state space until it reaches the bottom. It is easy to think of finding a maze. If you walk in one direction and you reach a dead end (= get to the bottom of the tree), go back the other way. Repeat this until the target point (= desired year) is reached. It can be implemented as a recursive function, or if you are not familiar with recursive functions, you can use the stack. In fact, recursion is less intuitive and less coding
§ BFS (Breadth First Search)
BFS is a method of checking all the bifurcation points. What is the minimum number of victories a player can take to the point where he wants to play when Cheol-su and Young-hee play a game of clapping rocks on the stairs? It is effective in the same problem. In this case, DFS does not exit if the depth is infinite, and it takes time to find the right solution even if it prevents duplication. BFS searches all the branches and searches the state space. When the ball is defeated, the ball is scored, the ball is scored, and in each case all three possibilities are examined. If you find the solution you want in one part, this is the shortest distance.
BFS is implemented by writing a queue. Put a new case that occurs while examining each case into a queue, and subtract the checked element from the queue. The advantage of BFS is that it can solve the problem that DFS does not touch, but because the space complexity explodes on an exponential scale, if you do not do the pruning properly, you can overflow faster than DFS.
§ Best First Search
The best first search method is a little more advanced in this BFS. It is implemented using a priority queue (usually implemented as a heap) instead of a queue. Unlike Breadth First Search, which sequentially checks for new occurrences, it is relatively efficient because it examines the most optimal cases first. Backtracking takes care of everything, so when you’re nervous, you might be able to solve it a bit. It is very useful to solve only the time and memory because you can implement anything you can do with dynamic programming. It took a lot of time when I could not solve it. It can also be a very effective solution if you apply appropriate heuristics by applying a Bounded (Promising) function to prevent meaningless searches. In the case of the previous withdrawal problem, there is no need to search for the target point and the opposite direction to continue. This improves the computation performance because no search is performed for the case where there is no possibility at all.
