SE250:lab-X:srag014
Lab X
This lab is all about State Space Search! Started off by reading through the lab sheet...looked much better than last weeks!
Task 1
The first task involved calculating how many different states existed for the 8-piece puzzle we were given. This was pretty straightforward, there was 8 pieces but 9 spaces so therefore to find the total number of states:
9! = 362,880
The second part of this task was to estimate the number of edges in the complete state space graph. This was difficult to work out.So when the space is in the middle there are 4 possibile options, when its in a corner there are 2 possibile options and I think if its anywhere else its 3 possibile options.Im not really sure how to estimate the edges for the graph, but if i have to guess Im guessing (4!*(3!^3)*(2!^4)).
Task 2
The second task was to write a summary of the searching algorithm. I had no idea what the algorithm meant...I think Ill get back to this task...
Task 3
Hand drew the graph of the region of the state space within two
consecutive moves of the initial state that was on the handout...just to make sure I did right I checked it with
one of my peers. Once i drew that the next part told me to check it with the graph.c code, which I ran to get an error!
But then I came across the fix and fixed it to get a massive graph/tree!
I wasnt sure if it was right or not but I got some help and was told to change the code slightly which I did and the graph
that it came up with matched mine!
<html>
<img src='http://img160.imageshack.us/img160/6734/68740268th0zl3.png'>
</html>
Task 4
Fourth task was pretty straightforward...the output i got was:
123 456 .78 -> 123 456 7.8 -> 123 456 78. -> Visited 5 states
The output tells us that it visits 5 states but it only shows 3 states!?!