HIT220 Algorithms And Complexity
Questions
Preparation
This exercise is based on created data, but the context is relevant. There are much less sighting than used in this exercise.
Information: Crocodiles are often sighted around the Darwin area. Some of these are quite historic but they show where crocodiles have been breeding and feeding. They can travel down rivers, around bays and we have reason to believe they travel across areas of land marked with red trails. The exact route of these trails is not known, we are providing the best estimate given sightings of croc at different times in this area.
The red dots are sightings, usually associated with breeding locations, as the croc is less mobile at this time so more likely to be tracked. Sighting can be through finding fresh tracks or sightings of the animal in the location, which will include the number of sightings over a season.
Your first task is to process the data files and populate the variable location list, with the data of the graph within the python file. You can calculate the travelling distance between two locations using the most direct path between two geo-locations, hence it is only an approximation of the actual distance between two locations.
Some extra points are provide as assumed stops on the transit routes of the croc when travelling between water courses. Otherwise points are joined along rivers and around the coast. Neighbours are only given in one direction the opposite direction is assumed to exist also.
Question 1
To test the possibility of blocking route between two locations, the rangers have to perform an exhaustive search on the path options between the two locations. This will involve them moving between known sightings and along estuaries or shoreline to assess the ability for crocs to pass, or possible ways to block their passage.
Your task is to devise an algorithm to determine the minimum cost of performing an exhaustive search between two points, where this cost is proportional to ground covered. Also give the list of locations that were chosen to segment the route in order to obtain this minimum cost. The cost is estimated just in units (how many units of work time required). Routine is compute Costing (location1, location 2).
Question 2
The engineers are now conducting a study on the benefit of constructing a croc barrier between two existing locations. One important data that they need is a comparison between the current distance between two locations using existing trails, and the hypothetical distance between two locations if there is a blockage in the present shortest route between them. For instance a monitoring device could be set up to alert if a croc
passes and have a crew sent in.
These devices are expensive and risk being stolen, so we want the optimum place on the path to locate this. For any two locations or group of locations, the higher the ratio between current distance and hypothetical distance is, the more benefit can be obtained by building a blockage along that route. You should return the ratio of this improvement and the edge that will be blocked to achieve this using method improveDistance()
Question 3
You are again asked to find the minimum distance between two locations in terms of number of metres and hence time for croc to travel. Croc speed is about 16 km/hr in water and 6km/hr on land. You are required to specify the route in terms of the points travelled through on the path. Method minTime() returns an array and a time value As an extension, provide the number of crocs in a certain radius of a beach. Using this
array of locations, decide which is the optimum path segment between two points to insert a blockage that would make the beach safer, by increasing the time the maximum number of crocs would have to travel.
