[SOLVED] algorithm database graph Algorithm Design and Analysis

Algorithm Design and Analysis
Assignment Two
The purpose of this assignment is to develop an intelligent system for moving a vehicle through variable terrain.
The terrain consists of a rectangular re-
gion broken up into quadrants, where each
quadrant is assigned a difficulty factor be- tween 5 and 15. A vehicle can start anywhere along the bottom of the terrain and must move one quadrant at a time either directly forward, or diagonally for- ward (one quadrant forward to the left or right unless the vehicle is on one of the two edges of the terrain). Some sample terrains are available on the raptor2 database server in a database called terrains. The goal is to move through the terrain so as to minimize the total difficulty for a vehicle.
The system should include the following components:
User Interface which should allow any of the terrains on the database to be obtained and present some graphical representation of the chosen terrain. Parts of the user interface should utilize the Observer design pattern, so that they are notified by a vehicle whenever the vehicle moves in the terrain. (15 marks)
Manual Control which allows the user to manually move a vehicle through the terrain, displaying a tally of the difficulty as the vehicle is moved.
(5 marks)
Automated Control which should move an automated vehicle intelligently through the terrain, and present the path in a suitable manner.
(10 marks)
Intelligence Algorithm which should use some level of intelligence (selectable between 0% and 100% by the user) to efficiently choose the most appro- priate path through the terrain. For example, with an intelligence of 100% a vehicle would be able to choose its path based on the entire terrain, so
1
1
4
5
4
9
6
8
9
3
1
9
3
5
7
8
4
2
1
8
4
3
5
2
1
9

it might start in the third (or fourth) quadrant along, and progressively move forward-left, forward, forward-left, forward for a total difficulty of 10. Instead, with an intelligence of 40% a vehicle would only be able to choose its path based on the two rows (40% of the maze) that are currently ahead of it. (15 marks)
Justification which should be a text document that justifies why your algo- rithm chosen for the automated control does give a path with minimum difficulty when the intelligence is set to 100%, its order, along with some reasoning for how it works for lower levels of intelligence. (5 marks)
2