I think I went off on a tangent in my last posts but the basic idea through backtracking search is that the computer is able to know where it's been and where it needs to go. This is where recursion and the stack comes in, mainly.
Whenever a function is called, the variables passed get loaded onto either the stack or into registers, depending on the architecture of the computer. The actual implementation details aren't too terribly important, except that the first function also saves a copy of its registers in the stack space. This DETAIL does become vitally important for recursion to work properly. When you go into recursion, you have to go out eventually. It's like running into a forest. You can only run so far before you start running out.
Most programmers know that, if you declare a variable called foo, set it to contain the value "5" as a number, and call another function, foo still contains 5 when you come back. However, things tend to get a little trickier when you're dealing with recursion, because then a function is calling itself. Which means you now have to think of foo as a local variable but also as a local variable that may have a completely different value. They're named the same, they come from the same function, so recursion is a little tricky to think about sometimes, especially when going out of it.
Going out of recursion means the calls you have made are returning, and control is returning to functions that made these calls. These functions and their variables sit lower on the stack, and as control is returned, the functions will keep doing what they need to do with the variables they had started with, despite any changes other function calls might have made.
This is assuming the variables were passed by value, of course. This isn't something you want to do with large objects, and sometimes, you want recursive algorithms to manipulate the data they are passing to copies of themselves, since the whole idea is to break down a problem into parts. Merge sort is a good example. Break an unsorted list into multiple unsorted lists until they are of a certain size, and then sort those lists, and then merge the smaller sorted lists into one big list.
Now what do you do if you want to manipulate the data passed, but you want to also don't want to make the changes permanent? We could do pass-by-value, but what if it's a big object, or a big array? It is also possible to do pass-by-reference and just undo what we did after the function call, and this is generally how a backtracking search gets implemented.
First, you find a partial solution. In the case of the n-queens problem, this can be an empty board. An empty board can be considered a partial solution in much the same way that, if you have an idea of something, then you have a partial solution to that problem (no idea -- nowhere near to getting a solution). From there, you place your queen, make a call, try to place another queen, and if that doesn't work, you return the control to the function that called you and let him clean up the placement of his queen and try again. This would just look like the opposite of what you just did before you make another call. I should probably point out that backtracking search requires a loop to make this possible.
Backtracking search doesn't require a computer though, of course. If you got stuck in a minotaur's labyrinth you would be able to find your way out if you were able to keep track of where you need to look, and where you've already looked.
No comments:
Post a Comment