SE250:lab-X:bvic005

Lab X

In this lab we have to work with a state based search problem.

Task1

First up we have to calculate the number of states in an 8 piece puzzle. This is quite easy, as all it is is the number of pieces factorial. However, the name of the puzzle is rather misleading, as there is actually 9 pieces, not 8. There are the 8 pieces from the name, and then the empty space. Therefor, the number of states is 9!, or 362880.

The second part of this task, estimating the number if edges in a full graph of this puzzle, is a bit harder. After a bit of discussion, however, i settled on this:

As a general rule, the number of edges in a tree should be the number of states, multiplied by the average number of next states, divided by two(as each edge would be "detected" at both ends).

Therefor, the number of edges should be around:

(9! * 2.6666 ) / 2 = 483840

Task2

Here we had to write a summary of the search algorithm provided.

The algorithm starts with a initial stat passed into to search function. This is added to a list of states to check(which is actually a tree, but more on that later). Then, while there are at least one states in this list, a loop removes a states from the list, and checks if this state is the specified goal state. If so, the loop breaks out. If not, it gets all the children of the current state, and if they haven't been seen before, they are added to a path map, and to the list of states to check. The loop then moves on to the next state to check.

Once the loop ends, another loop works backwards from the goal state to he initial state, through the map that was built, and recording each step in a solution list.

Task3

In task three we had to draw some stuff by hand. Yea, not much to show here...

Task4

Here we have to describe the search strategy search.c uses. It states that it is a depth first search, but this does not appear to be the case at all. Looking at how the "list" storing states to check is implemented, i(and a few other people) found that it is actually a binary search tree, not a standard list/queue(which is what you usually be used for depth first/breadth first search).

After much puzzling at the code, we eventually surmised that when a state is added to the tree, its "Manhattan distance" is calculated, as an estimate as to its "closeness" to the goal state. This distance is then used as the key in the binary search tree, meaning that the whole tree is set up from left to right in increasing improbability of being the next state needed. When the next state to be searched is picked, the left most state in the tree, ie the state with the smallest manahttan distance, is used.

Therefor, it seems that the search is best first, not breadth or depth first.

Task5

Here we are asked to fun "the search code", and compare that solution to ours "state graph". I presume this means we are supposed to set up the search function to do what we did by hand in task 3, and then compare the results.

Results:

123
456
.78
 ->
123
456
7.8
 ->
123
456
78.
 ->
Visited 5 states

With such a small set of data, its kind hard to compare. However, what could be said is that when solving it by hand, all(most?) humans wouldn't need to visit the two extra states that the search function did.

Task6

Here we had to convert the provided depth first search function, into a breadth first one, by changing one line of code. However, as we have actually been provided with a best first function, it is kinda hard to do this task.

However, i guess what they where wanting was for us to convert a last in first out stack policy, into a first in first out one.

Tasks 7 and 8 also dealt with breadth/depth first functions, so i couldn't do those either.

Lab Problems

As usual, this lab had quite a few problems. The most major would obviously be the fact that the search function we where given is not the one we need for doing the tasks.

Also, as usual, the code we are supposed to be trying to understand had little to no commenting, and often used code that we have not yet been taught, making it quite hard to unravel ourselves.

The use of the imaginary "wt" write flag came up again, which was annoying for me doing this lab on Linux.