SE250:May 28
Minutes
Minute-Taker: npit006
If anything is incorrect, please fix it!
Lab 9 Post-Mortem
We started the lecture with a student poll on the hardest SE course thus far. Perhaps this was intended to indirectly gauge how our assuredly amiable attitudes towards SOFTENG250 have changed after yesterday's mind boggling lab? Either way, the difficulty of Lab 8 was discussed and we came to the conclusion that in order to successfully complete Tasks 2 and/or 3, the preceding tasks had to be completed. We examined the lab reports of students for each different task. Given the trouble which most students experienced in doing this lab, the lecturer hopes that it at least enlightened us about the general idea of parsing and the processes involved, even if we couldn't write our own tokeniser/parser/compiler.
Introduction to State-Space Searching
It is estimated that half of artificial intelligence programming is related to searching. The idea of state space search is that we have a problem with parameters and the situation at any time can be represented in terms of states. Our primary example application for this technique is writing a program which can solve the sliding block puzzle. An example is given below.
<html> <img src="http://img140.imageshack.us/img140/9069/400px15puzzlesvgcp2.jpg"> </html>
The underlying idea is that our problem is in a particular state, and it tries to search for another legal state (of which there might be millions). Eventually (or as soon as possible), we want to reach a goal state. We might represent the above state as 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,B with B for blank. We can't use a tree to represent this situation because this is more general than a tree, as states can loop around and cycle. We instead represent states with a graph diagram (and this is beginning to sound like COMPSYS201). The problem is that state spaces tend to become exponentially large as problems grow more complex - even as we go from a 3x3 to a 4x4 puzzle. It is more desirable to use an implicit solution like state space searching whereby we don't store all the possible states of our problem (because that would be a mammoth task in most cases).
Next, we discussed how we might discriminate between potential subsequent states. In regards to the sliding block puzzle, one possible solution was to quantify the (potential) problem progress by counting the number of blocks in their correct places. Another was to sum the total distance (Manhattan distance) of each block from its destination. If we can quantify potential progress, then we can use heuristic methods to determine how suitable each option is.
Following that, we discussed the 8 Queens problem. I have a feeling this was mentioned because it is more complex (64 choose 8 possible states) than the sliding block puzzle and it reinforces the idea that it isn't feasible to load the whole state space graph into memory. Either way, this introduced the idea that some states are illegal... such as a state which involves any queen obstructing the path of another.
Finally, the lecturer drew an exemplary state space graph for us, indicated (by circling) a starting node, and left us with a question - how do we visit all nodes without revisiting any (i.e. no loops)?