Mark: 23 revision(s)

2008-11-03T05:20:47Z

23 revision(s)

New page

==Preliminary Code Fixing==
I was only able to compile and run search.exe and graph.exe 40 minutes into the lab. These are the changes required.

static char* DOT_CMD = "\"C:/Program Files/ATT/Graphviz/bin/dot.exe\"";

//static char* DOT_CMD = "dot";

// init_State( &start, ".123456789abcdef" );

// init_State( &goal, "123456789abcdef." );

init_State( &start, ".12345678" );

init_State( &goal, "12345678." );

==Task 1==
In the 8 piece puzzle, there are 9 possible different values for each position. Therefore, the total number of states is 9! = 362880.

Calculating the number of edges in the total state space is a bit more difficult. Each state has a certain number of edges depending on whereabouts the blank space is... there are 9 possible positions for the blank space... summary:

4/9 positions are corners which have 2 edges
4/9 positions are edges which have 3 edges
1 position is a middle one which has 4 edges.

With 362880 possible states categorised by where the blank space is, I think:
* 161280 of these states are corners and yield 322560 edges
* 161280 of these states are edges and yield 483840 edges
* 40320 of these states are middles and yield 161280 edges

Total number of edges = 967680

Have to divide by 2 since an edge is bidirectional... edges = 483840

==Task 2==
Judging from the sparsely commented wall of code that is search.c, I think I'll skip this task for now. Other tasks are probably more important/useful.

==Task 3==
I drew the state space enclosed within 2 moves of the initial state and it was correct. There were 7 states included.

==Tasks 4 & 5==
Task 4 involved inserting a print_state call at some point in the program - I tried including it in various positions in search.c. In order to insert it in a sensible position, I attempted to understand search.c (this is Task 2 all over again!). Shown below is the output from a regular search followed by the output from a search with a print_state call. I've also included the print_state call which I added in after pop command in search.c

E:\lab10>search
123
456
.78
->
123
456
7.8
->
123
456
78.
->
Visited 5 states

***
123
456
.78

***
123
456
7.8

***
123
456
78.

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

E:\lab10>

CODE:
printf("\n***\n");
print_state( &s);
printf("\n");

Given the initial state, there were 2 possible routes from there (2 children). Judging from the output (5 nodes visited), the depth-first search chose the correct path for the first movement, but then the wrong one for the second and had to backtrack... this makes sense.

I think my code is in the wrong place though.

==Task 6 - Change from Depth First to Breadth First==
I have no idea which line to change in order to alter the search strategy - it might help if I had been to lectures recently. From what I understand, using a queue is natural for a breadth-first search and using a stack is natural for a depth-first search. Though I'm pretty sure that has nothing to do with the one line change required here.

Perhaps if in looking for children, we only add one child at a time per search, that might alter how it works. I don't really have any real idea of what to do here.

==Conclusion==
Again, it is annoying that the prepared code has problems because that only wastes time. The lab itself was fairly difficult mainly because I've missed a critical lecture or two. I could have been better prepared by reading over last year's HTTB section on state-space searching, but this week has been far too busy. Still, all things considered, I think I accomplished a reasonable amount.

SE250:lab-X:npit006 - Revision history

Mark: 23 revision(s)