고유의 스타일은 생각만큼 쉽게 낡지 않습니다. 쉽게 낡는 것은 모방자들과 원조들보다 재능 없는 2차 수용자들입니다. --Djuna
- 원문 링크 :
![[http]](/wiki/imgs/http.png)
http://www.siteexperts.com/tips/functions/ts20/page3.asp
- 원문은 자바스크립트를 사용한 예제로 되어있습니다. 제가 나름대로 손을 좀 봐서 고칠건 고치고, 예제는 C로 다시 만들었다고 생각하시면 됩니다.
- 의역도 많고 몇몇 문장은 과감히 삭제하였습니다. 참고 바랍니다.
Chapter 1 : Recursion #
Backtracking is a simple, yet elegant, recursive technique which can be put to a variety of uses. In this article, we will explore this technique in detail, and analyze its usefulness in tree spanning. We will also take an inside look into a sample game 'Mysterious Maze', which uses a depth-first algorithm to span a decision tree in order to dynamically generate mazes. First of all, however, let us discuss the basic principles of recursion, on which backtracking, as well as the more sophisticated algorithms we will be covering later, depend on.
Understanding Recursion #
The factorial of an integer N (written as N!), is defined as N multiplied by all the integers lower than N. Thus 5! is calculated as 5 x 4 x 3 x 2 x 1 = 120. Let us examine a simple function that takes a single integer parameter and returns the factorial of that integer.
function fact(N){
var retval=1;
for(i=N;i>0;i--){
retval=retval*i;
}
return retval;
}
The loop is pretty straightforward. retval starts off with the value 1, is then multiplied by N, then N-1, and similarly all the integers between N and 1, inclusive. Now, let us write the same function in a slightly different way.
function fact(N){
if(N==1)
return 1
else
return N*fact(N-1)
}
Elegant, is it not? The algorithm takes advantage of the fact that the factorial of any integer N can be defined as the product of N and the factorial of N-1. For example 5! = 5 x 4!. The function above is an example of a recursive function, because, as you can see in the second 'return' statement, the function calls itself.
Recursive functions are closely related to inductive definitions of functions in mathematics. In order to evaluate whether an algorithm is a candidate for recursion, we must first try to deduce an inductive definition of the algorithm. For example, the factorial function can be defined inductively in this way :
1 if N=1 N! = N x (N-1)! if N>1
Algorithms that are by nature recursive, like the factorial example above, can be coded either as a loop, as in the first example, or as a recursive function, as in the second example. However recursive functions are generally smaller and more efficient than their looping equivalents.
The Stack #
The Stack is an special area of memory in which temporary variables are stored. The Stack acts on the LIFO (Last In First Out) principle, which is the same principle involved in, say, the stacking of cardboard boxes one atop the other, where the topmost box, which was the last box stacked (Last In), will the the first to be removed (First Out). Thus, if the values 9,3,2,4 are stored (Pushed) on the Stack, they will be retrieved (Popped) in the order 4,2,3,9.
In order to understand how recursive functions use the Stack, we will walk through how the second algorithm above works. For your convenience, it is reproduced below.
if(N==1) return 1 else return N*fact(N-1)
Let us assume we want to find the value of 3!, which is 3 x 2 x 1 = 6. The first time the function is called, N holds the value 3, so the else statement is executed. The function knows the value of N, but not of fact(N-1), so it pushes N (value=3) on the stack, and calls itself for the second time with the value 2. This time round too the else statement is executed, and N (value=2) is pushed on the stack as the function calls itself for the third time with the value 1. Now the if statement is executed as n==1, so the function returns 1. Since the value of fact(1) is now known, it reverts back to it's second execution by popping the last value (2) from the stack and multiplying it by 1. This operation gives the value of fact(2), so the function reverts to it's first execution by popping the next value (3) from the stack, and multiplying it with fact(2), giving the value 6, which is what the function finally returns.
From the above example, we see that
- The function runs 3 times, out of which it calls itself 2 times. The number of times that a function calls itself is known as the recursive depth of that function.
- Each time the function calls itself, it stores one or more variables on the Stack. Since the Stack holds a limited amount of memory, functions with a high recursive depth may crash because of non-availability of memory. Such a condition is known as Stack Overflow.
- Recursive functions usually have a terminating condition. In the above example the function stops calling itself when n==1. If this condition were not present, the function would keep calling itself with the values 3,2,1,0,-1,-2... and so on for infinity. This condition is known as Endless Recursion.
- All recursive functions go through 2 distinct phases. The first phase, Winding, occurs when the function is calling itself and pushing values on the Stack. The second phase, Unwinding, occurs when the function is popping values from the stack.
Chapter 2 : Decision Trees #
Trees are one of the most frequently occuring data structures used in programming. In fact, the HTML document you are reading now contains tags nested within one another in a tree structure. We will not concern ourselves with data structures in this chapter however; what we will be looking at are decision trees, sometimes known as game trees.
Solving a maze #
Consider a maze, shown in the diagram above, where a player has to decide how to get from room A to room B. The player can move from room to room through the corridors provided, but has no way of telling how many corridors a room is connected to until he reaches that room. We will now see a sample session to understand the approach the player uses to solve the maze.
- The player moves from room A to room 2.
- From here he can move either to rooms 1 or 3. He chooses 1.
- Dead End. He returns to room 2, then goes on to room 3.
- He has no choice but to move to room 4.
- Given a choice between rooms 5 and 6, he chooses 6.
- Another choice between 7 and 8, he chooses 7.
- Dead End. He returns to 6 and chooses 8.
- Dead End again. He returns to 6 and sees that he has exhausted his choices.
- He goes back to room 4, and chooses room 5.
- He sees room B, moves to it, and solves the maze.
function CheckRoom(RoomNumber) begin if RoomNumber has been visited, return. for each room connected to this room if ConnectedRoomNumber == B, the maze has been solved else CheckRoom(ConnectedRoomNumber) end for end function
That's all! The algorithm takes care of rooms with Dead Ends, rooms with multiple corridors, and anything you care to throw at it. It has the elegant simplicity characteristic of all recursive procedures, but it differs slightly from the functions we have studied previously. It is a backtracking algorithm.
How Backtracking works #
The sample maze, like all mazes, is essentially a tree, with room A at the root of the tree. Consequently, the backtracking algorithm discussed above is a tree-spanning algorithm. When it reaches a node like room 2, where it has more than one path to choose from, it picks one path (to room 1) which is a leaf node, or Dead End. Finding that it can proceed no more, it unwinds to it's previous execution, (back to room 2) and takes the other path, to room 3. Such an algorithm is known as a depth-first spanning algorithm, because it tends to follow a path right down to the bottom of the tree, before it gives up and unwinds to a previous execution in order to choose a different path. Manually apply the CheckRoom function above to the tree to get a feel of how the algorithm works.
Backtracking procedures are characterized by multiple recursive calls, typically within a loop (see the CheckRoom function above). Unlike the simple recursion examples we had encountered in the previous chapter, a backtracking procedure goes through multiple winding and unwinding stages as it loops through the choices it has to make at every node. One of the most common applications of backtracking is in the evaluation of moves for strategy games like chess. We will look at a much simpler game, tic-tac-toe, and see how a backtracking strategy can be used to ensure that we can never lose the game.
Game Trees #
Tic-tac-toe is played on a 3x3 grid, so there are 9 possible starting moves. Each of these can be followed by 8 possible countering moves, which can each be further be followed by 7 moves, and so on. These moves can be viewed as branches of a tree, with the resulting state of the playing grid as the nodes of the tree. It is important to note that the grid itself is not a tree structure, it is the possible grid states after each move that form the decision tree.
The tree will have 3 types of leaf nodes, grid structures representing wins, losses and draws. A typical game playing program will use backtracking to move through this tree, assigning high values to each node which leads to a winning scenario, lower values to the nodes which could conceivably lead to draws, and very low values to nodes that may result in losses. The program then uses the unwinding phase of the algorithm to trickle these values upwards through the tree, so that each of the nodes that represent the next move of the program will have a value. Finally the program chooses the node with the highest value to make it's next move.
This is only a (very) simplistic explanation of how programs evaluate alternative strategies using backtracking. If you would like to view the source code of a tic-tac-toe program which uses a backtracking algorithm, you can download it from here. For other games and algorithms, do visit the awesome X2FTP game programming site.
3 장 : 미로 생성 #
이 장에서는 어떻게 '이상한 미로' 프로그램이 난수로 미로를 생성하는 법에 대해 살펴볼 것이다. 프로그램이 생성하는 미로들의 종류는 완벽한 미로들로 생성된다. 왜냐면 미로상의 어떤 2개의 칸들도 단지 하나의 단일한 경로로써 연결되어지기 때문이다. 프로그램은 상단왼쪽칸을 시작칸으로, 하단오른쪽칸을 종착점으로 간주하고 미로를 생성한다. 그러나 어느 곳이던지 시작점과 종착지로 2개의 칸을 선택할 수 있다. 완벽한 미로는 어떤 데드 존(도달하지 못하는 지역)도 담고 있지 않다.
이것들은 환형 미로 - 한개 이상의 길이 존재하는 미로 - 와도 다르다. 깊이우선탐색 알고리즘이 미로를 생성하는 데 사용된다.
알고리즘 #
대부분의 미로 생성기와 같이 이 프로그램은 칸과 칸 사이에 벽을 모두 설정한 미로를 생성함으로써 시작한다. 그리고 임의의 칸을 설정한 후 그것을 시작점으로 간주하고 다음과 같은 알고리즘을 사용하여 벽을 부수어 나간다.
- 현재의 칸에 "방문했음" 표시를 한다.
- 만일 현재 칸이 방문하지 않은 어떤 이웃된 칸을 가지고 있다면,
- 방문하지 않은 한개의 이웃을 선택한다.
- 현재의 칸을 스택에 Push한다.
- 선택된 칸과 현재칸 사이의 벽을 제거한다.
- 선택한 칸을 현재 칸으로 만든다.
- 이 함수를 재귀적으로 호출한다.
- 그렇지 않으면
- 가장 최근의 현재 칸을 스택으로 부터 꺼낸다.
- 이 함수의 가장 최근의 실행으로 역추적(Backtrack)한다.
The Data Structure #
The maze is represented internally by the program as a three-dimensional array of cells, with the first and second dimensions being the Row and Column of the cell respectively, and the third dimension representing the attributes of the cell. Each cell in the maze has 3 binary attributes, BOTTOMWALL, which is 0 if the cell has no bottom wall and 1 if it does, RIGHTWALL, which similarly represents whether the cell has a right wall or not, and VISITED, which is used by the maze generation algorithm.
Thus, the maze above would be internally represented as -
Maze[0][0][RIGHTWALL]=0; Maze[0][0][BOTTOMWALL]=1; Maze[0][1][RIGHTWALL]=1; Maze[0][1][BOTTOMWALL]=0; Maze[0][2][RIGHTWALL]=1; Maze[0][2][BOTTOMWALL]=0; Maze[1][0][RIGHTWALL]=1; Maze[1][0][BOTTOMWALL]=0; Maze[1][1][RIGHTWALL]=1; Maze[1][1][BOTTOMWALL]=0; Maze[1][2][RIGHTWALL]=1; Maze[1][2][BOTTOMWALL]=0; Maze[2][0][RIGHTWALL]=0; Maze[2][0][BOTTOMWALL]=1; Maze[2][1][RIGHTWALL]=0; Maze[2][1][BOTTOMWALL]=1; Maze[2][2][RIGHTWALL]=1; Maze[2][2][BOTTOMWALL]=1;
The Code #
We will now look at the code that uses the depth-first search algorithm on the maze data structure in order to generate the maze.
The program calls the MakeMaze function to begin the maze generation. This function initializes the RIGHTWALL and BOTTOMWALL attributes of all the cells to 1 (remember the algorithm starts out with all walls intact). It also initializes all VISITED attributes to false. It then chooses a random cell as it's starting point, and proceeds to call the MakePath function with the Row and Column of this chosen cell as parameters.
MakePath is a backtracking function which takes 3 parameters, the Row and the Column of the cell it is currently evaluating, and the Direction that the previous execution of the algorithm had taken. It uses this Direction parameter to decide which wall to break down. Of course, when it is called initially by the MakeMaze function, the Direction parameter is blank, therefore no walls are broken. The first thing that the MakePath function does is to mark the current cell as visited (Maze[R][C]VISITED=true).
The function then builds an array of the possible directions it can take (N,S,E or W), goes through these directions one by one, calling itself with the Row and Column of the cell in that direction, with the direction itself as the third parameter. Of course, it will only go in that direction if the cell in that direction has not already been visited.
A word of warning here, before we move on to see the program itself. Variables within recursive procedures like the MakePath function must be declared with the var statement. This is because undeclared variables do not revert to their previous values when the procedure backtracks to a previous execution. To understand what I mean, open the Mysterious Maze program in a text editor, and remove the word var wherever it occurs in the function. Then try running the program. You will find that the maze will have only been partially generated, and that the MakePath function stopped executing the first time it tried to backtrack. On to the program now, and have fun.
