 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ODL 129 TEAM B Coursework 1 |
|
|
|
Question 4 |
|
|
|
Consider which kind of search strategy your algorithm makes use of and compare that strategy with at least one other strategy you have investigated from the readings. |
|
|
|
Answer |
|
|
|
The algorithm outlined in question three utilised the depth-first search strategy. This algorithm traverses through the grid world matrix (visiting every shape) keeping the goal state (rectilinear adjacent blocks) in mind. Any shapes found to share (but not overlap) identical grid locations are deemed to be adjacent. |
|
|
|
An initial start point is selected eg (x,y = 0,0) & visited. The search continues vertically along the same path (storing the grid line locations) of the first shape found. This is repeated until a 2nd shape is detected & so on. This type of algorithm selects an individual pathway searching for its assigned goal state which it stores. When it has exhausted all possible options in one pathway it then retraces its footsteps (recursion) & selects a different pathway. (This repetitive sequence of instructions is known as loop control). |
|
|
|
Another type of search strategy that could have been considered is that of a breadth-first strategy. This type of search (as its name implies) adopts the type of search where it searches horizontally across the grid world one grid line at a time from left to right (or 0 - 19 in this case). This type of search uses more memory space as it searches every gridline within the grid world rather than selecting the more ?promising? pathways as is the case with a depth-first search. |
|
|
|
The Best first search is a strategy which combines both strategies previously mentioned, (depth first search and breath first search). This follows a single pathway but will select a different pathway if it thinks it is more promising. The disadvantage of this technique is that it is unable to predict if the node it is switching to is more likely to enable it to acheive its goal state than any other node it has not visited. (It could potentially be moving away from its intented goal)! Therefore this combination strategy may not be as efficient as the individual strategies. |
|
|
|
The A* search technique also combines breath first and depth first strategies by attempting to find a solution which minimizes the number of moves (or cost) of a specific pathway. It attempts to find the shortest path first (breadth first) and then searches for the node which appears to be closed to its goal state next. It allocates a score (minimum number of steps required to reach goal) to a node which consists of combination of the cost (number of steps) so far and the estimated number of steps required to reach the goal. This type of search strategy will always find the shortest path to the goal state first. |
|
|
|
 |
|
|
|
 |
|
|
|
Question 1 |
|
|
|
Question 2 |
|
|
|
Question 3 |
|
|
|
 |
|
|
|
To top |
|
|
|
|
|
Question 5 |
|