Recursion n. See recursion
Search v. Definition hidden at the end
Greetings
I am came across an interesting problem sometime back on the net. The problem in a nutshell was to calculate the least of amount of steps that it would take a knight to get from square(a,b) to square(x,y). The real task at hand was to map out the whole chessboard, with values denoting the depth or breadth level from the starting square. This question could be solved two ways, using either the Depth First Search Method, or the Breadth First Search Method. I am going to speak about them in this post.
DEPTH FIRST SEARCH:
The Depth First Search or DFS is a recursive searching method, where by, on goes down as long as they can until they hit a dead end. When they do, they go one up, and starting going down again, although this time in a different path. Consider it like this. Imagine a house full of rooms. Inside these rooms there are more rooms, inside which there are even more. Your task is to find how many rooms one has to go through to get to room 8. Diagram given below.
In a typical DFS search, the longest search order would be something like this:
Start->1->4(Dead End!)->1->5->9->5->1->Start->2->6->10->6->11->6->2->Start->3->7->12->7->3->8
In a typical DFS search, the shortest search order would be something like this:
Start->3->8
...............and many possible permutations in between.
As you can see, something that is just two levels away from the start takes a maximum of 23 node visits, where as the shortest one takes just 3 node visits. There is no way to ensure the DFS method to make the shortest node visits, as the DFS wont know the location of the node in absolute terms, only in relationship to other nodes. In part, the DFS has such a high, unacceptable worst case scenario result is because many of the nodes are re-visited many times over.(Start, 1, 5, etc). The difference between the best and worst cases is way too big for the search to be efficient.
BREADTH FIRST SEARCH
The search technique in BFS involves grouping nodes with the same absolute distance nodal distance from Start Point in the same breadth. Imagine that after the BFS technique identifies the nodes with nodal distance 1 from the start point. All these nodes are in Breadth Level 1. These nodes will then be pushed into a stack, where EACH on of these nodes will become the Start Point. Now the nodes with a nodal distance of 1 from these Start points will be grouped in Breadth Level 1 more than than the breadth level of their starting points, something like (Node Level = Start Point Level + 1). In this manner all the nodes will be mapped and assigned a value denoting their absolute nodal distance from the first Start Point. Here is a diagram.
In a typical BFS search the search order would be something like this:
Start->1,2,3 stack.push(1,2,3)-1st Level
loop through stack as long as there are nodes.
1->4,5 stack.pop(1) stack.push(4,5)-2nd Level
2->6 stack.pop(2) stack.push(6)-2nd Level
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
4->Dead End! stack.pop(4)-3rd Level
5->9 stack.pop(5) stack.push(9)-3rd Level
6->10,11 stack.pop(6) stack.push(10,11)-3rd Level
7->12 stack.pop(7) stack.push(12)-3rd Level
8->Dead End! stack.pop(8) -3rd Level
9->Dead End! stack.pop(9) -4th Level
10->Dead End! stack.pop(10) -4th Level
11->Dead End! stack.pop(11) -4th Level
12->Dead End! stack.pop(12) -4th Level
Another, faster case
Start->3,2,1 stack.push(3,2,1)-1st Level
loop through stack.
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
As you can see, each node is not visited more than once, only its location is pushed into the stack. After its immediate nodes are visited, it should be popped out or removed, otherwise you will have an infinite loop.
The difference between the best and worst case scenarios is not much, and is generally more efficient than DFS, as it takes less time, resources and searched intuitively.
The C++ program that I built also uses the same technique of BFS to solve the problem. Have a look at it, annotations are included and post your feedback or questions regarding the program.
Link for the .cpp File
Link for the .exe File
Until the NXT post
Aravind Rao, chief Hacker(claimed)
Search v. Definition hidden at the end
Greetings
I am came across an interesting problem sometime back on the net. The problem in a nutshell was to calculate the least of amount of steps that it would take a knight to get from square(a,b) to square(x,y). The real task at hand was to map out the whole chessboard, with values denoting the depth or breadth level from the starting square. This question could be solved two ways, using either the Depth First Search Method, or the Breadth First Search Method. I am going to speak about them in this post.
DEPTH FIRST SEARCH:
The Depth First Search or DFS is a recursive searching method, where by, on goes down as long as they can until they hit a dead end. When they do, they go one up, and starting going down again, although this time in a different path. Consider it like this. Imagine a house full of rooms. Inside these rooms there are more rooms, inside which there are even more. Your task is to find how many rooms one has to go through to get to room 8. Diagram given below.
 |
| The room location map. |
In a typical DFS search, the longest search order would be something like this:
Start->1->4(Dead End!)->1->5->9->5->1->Start->2->6->10->6->11->6->2->Start->3->7->12->7->3->8
In a typical DFS search, the shortest search order would be something like this:
Start->3->8
...............and many possible permutations in between.
As you can see, something that is just two levels away from the start takes a maximum of 23 node visits, where as the shortest one takes just 3 node visits. There is no way to ensure the DFS method to make the shortest node visits, as the DFS wont know the location of the node in absolute terms, only in relationship to other nodes. In part, the DFS has such a high, unacceptable worst case scenario result is because many of the nodes are re-visited many times over.(Start, 1, 5, etc). The difference between the best and worst cases is way too big for the search to be efficient.
BREADTH FIRST SEARCH
The search technique in BFS involves grouping nodes with the same absolute distance nodal distance from Start Point in the same breadth. Imagine that after the BFS technique identifies the nodes with nodal distance 1 from the start point. All these nodes are in Breadth Level 1. These nodes will then be pushed into a stack, where EACH on of these nodes will become the Start Point. Now the nodes with a nodal distance of 1 from these Start points will be grouped in Breadth Level 1 more than than the breadth level of their starting points, something like (Node Level = Start Point Level + 1). In this manner all the nodes will be mapped and assigned a value denoting their absolute nodal distance from the first Start Point. Here is a diagram.
 | ||
| The room Location Map, now with Breadth levels. |
Start->1,2,3 stack.push(1,2,3)-1st Level
loop through stack as long as there are nodes.
1->4,5 stack.pop(1) stack.push(4,5)-2nd Level
2->6 stack.pop(2) stack.push(6)-2nd Level
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
4->Dead End! stack.pop(4)-3rd Level
5->9 stack.pop(5) stack.push(9)-3rd Level
6->10,11 stack.pop(6) stack.push(10,11)-3rd Level
7->12 stack.pop(7) stack.push(12)-3rd Level
8->Dead End! stack.pop(8) -3rd Level
9->Dead End! stack.pop(9) -4th Level
10->Dead End! stack.pop(10) -4th Level
11->Dead End! stack.pop(11) -4th Level
12->Dead End! stack.pop(12) -4th Level
Another, faster case
Start->3,2,1 stack.push(3,2,1)-1st Level
loop through stack.
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
As you can see, each node is not visited more than once, only its location is pushed into the stack. After its immediate nodes are visited, it should be popped out or removed, otherwise you will have an infinite loop.
The difference between the best and worst case scenarios is not much, and is generally more efficient than DFS, as it takes less time, resources and searched intuitively.
The C++ program that I built also uses the same technique of BFS to solve the problem. Have a look at it, annotations are included and post your feedback or questions regarding the program.
Link for the .cpp File
Link for the .exe File
Until the NXT post
Aravind Rao, chief Hacker(claimed)
