SE250:lab-X:hpan027
Final lab
Task One
'Calculate how many different states exist for the 8-piece puzzle. 'Estimate the number of edges in the complete state space graph. 'Explain how you made these calculations in your report.'
- Number of state 9!
- Number of edges:
- When space is at a corner - 2 possible moves (4/9)
- When space is at a side - 3 possible moves (4/9)
- When space is at centre - 4 possible moves (1/9)
- If the space is fixed, then there are 8! possible states
- Hence 8! * 2 * 4 + 8! * 3 * 4 + 8! * 4 + 1
- 967681
- Have to recheck this later
- Upon doing task three
- There are a lot of overlaps (e.g. 1->3 and 3->1 would be along the same edge)
- Number should be halved?
Task Two
'The main search code can be found in search.c. In your own 'words, write a summary of the search algorithm in your report.'
- There seems to be a stack. Probably a depth-first search. Too much code to read, might revisit later.
- Read task four. Heh.
Task Three
'By hand, draw a graph of the region of the state space within two 'consecutive moves of the initial state shown. Highlight the start 'and goal states, and the solution path from the start to the goal.
<html> <img src="http://studwww.cs.auckland.ac.nz/~hpan027/250-10-art.jpg"> </html>
- Forgot to point out the goal state
- New and exciting intermittent step of trying to get code to compile
- Stuff on main lab page was helpful
- Seems to check out - the 123456.78 has 2 neighbours, each of which has 2 other neighbours
Task Four
'Use the print state function to print the first few states the search 'code checks, compare this to your graph and describe in your 'own words how this search strategy traverses the search space.'
- Output
.12 345 678 1.2 345 678 12. 345 678 125 34. 678 125 348 67. 142 3.5 678
- One consecutive move at a time
- Backtrack
Task Five
'Run the search code. What do you notice about the solution compared 'with the solution in your state graph?'
- My state graph did not print out properly - this task is kinda hard for me to do
- Solution is probably not the shortest path etc.
Task Six
'Make a one-line change to the code in search.c to convert the algorithm from depth-first 'to breadth first search. 'What do you notice about the breadth-first solution compared 'with the depth first one?'
- Requires some thought
- Changing a stack to a queue in 1 line is hard
- Does rewriting OrderedStackList into a queue count?
- Skipping ahead for now
Task Seven
'Conduct searches from the initial state to the goal state below for 'both breadth first and depth first search. 'How many states have to be examined before the solution is found 'in each case? Compare the path returned for both solutions.'
Task Eight
'What are the obvious benefits of using each of these two different 'search strategies? Under what circumstances would we prefer one 'over the other? Suggest some features of the state-space that will 'affect the relative performance of the algorithms.'
- Depth-first to conserve memory, finite state space
- Breadth-first for shortest path, infinite state space
Task Nine
'How are infinite loops (such as moving a piece back and forth) 'prevented in the supplied code? What data structures are used?'
- A set was implemented using hash tables
- Happened to be applicable because of the relatively small number of states for an 8-puzzle
Task Ten
'Implement iterative deepening search.'
- .
Conclusions
- Code still does not compile 'out of the box' :(
- C sucks with chain #include of things - it's hard to find where functions and structs are defined
- Makes code very hard to read in general
- Having to make one line modification to fully written code is annoying