Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COSC 1285/2123 Algorithms and Analysis
Pair (Group of 2) Assignment
1 Ob jectives
There are three key objectives for this assignment:
• Consider real problems and how algorithms can be used to solve them.
• Study path finding and develop algorithms and data structures to solve path finding for different realistic scenarios.
• Research and extend to practice developing algorithmic solutions beyond just applying them. 2 Background
The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an important problem and has many applications, including robotics, games and simulations, and maze solving. In this assignment, we’ll implement and develop approaches for path finding and extend these to interesting but realistic scenarios.
In the following, we first provide more details about path finding, then provide some ideas on how to represent a map and finally describe existing approaches to find these. In lectures we will also go through some of these in more details, so make sure you attend or if you can’t make it, as least tune in and look at the notes that will be put up.
2.1 Path finding
Path finding involves finding a path from A to B. Typically we want the path to have certain properties, such as being the shortest or to avoid going through certain obstacles. As the main aim is to think about path finding, we focus on the common task of finding shortest paths from A to B – shortest here means the path that has less total costs (more on this later, but given if we can travel at a constant speed over all parts of the map, then this equates to a path that is of least distance). The path is typically on a map (e.g., game) or a surface (e.g., robot).
Consider the map below (see Figure 1a), where we want to find a shortest path from origin point A to destination point B. There are obstacles and impassable locations (e.g., consider them walls in a maze, or a building one cannot enter in a game etc) that we cannot traverse (these are the block areas in the figure). If we use Euclidean distance as the cost (so the further one travels, the more costly), then the orange path, labelled (2), in Figure 1b is the shortest one1. The other two are possible paths but not the shortest.
To find (shortest) paths, we need to represent this map on a computer. There are several approaches to do so, which we will describe in the following subsection.
1Assume Jeff’s hand drawings are straight.
(a) Original map. (b) Map with a number of paths.
Figure 1: Example map and paths. The blue dot is the origin point, and red is the destination point. The black areas are obstacles and impassable locations that cannot be traversed.
2.2 Representing the surface or map
To represent the map, we can divide it into a number of coordinates. For this assignment, we assume a flat map/world so all coordinates are 2D, e.g., (row,column) or (r,c). To represent these coordinates and the map, there are generally two approaches:
• Grid representation: Dividing the map into a number of regular sized cells and considering the map as a grid of cells (see Figure 2a for an example with rectangular cells). Each cell represents a coordinate.
• Graph representation: Representing the map as a graph, where each node represents a coordinate and edges represent the possibility of moving from one coordinate to an adjacent one (think of the problem in tutes about mazes and how we can use a graph to represent the maze) (see Figure 2b). Edge weights represent the cost to travel between the coordinates.
Because of the one to one mapping between cell, coordinate and node, each cell maps to a node, hence in essence both convey the same information about a map.
The grid representation is generally easier to understand, and we have a basic implementation in the skeleton code to provide map and path visualisation. However, it has weaknesses, including difficulty in representing “non-standard” adjacencies and not able to directly use the multiple graph algorithms available to solve the path finding related problems. In comparison, the graph representation, although conceptually more difficult to understand initially, once it is understood has the same representation power as the grid one, but is generally more flexible and has many graph-based algorithms that can solve different path finding scenarios. In this assignment, you can use either, but conceptually we suggest it is easier to think about it as a graph, and in lectures we will discuss in terms of a graph representation.
2.3 Path finding Approaches
Once we represent a map as a graph, we can use the full set of graph algorithmic tools. A path in the original map is also a path2 in the graph, which means we can use algorithms such as BFS to find a
2Technically can be a (graph) walk, but if you don’t know what this is, don’t worry, not important just a curious side note.
(a) Grid representation, with rectangular(b) Graph representation. Each node repre- cells. sents a coordinate and each edge represents
adjacency and ability to traverse.
Figure 2: Example of the two map representations.
path from a origin point/coordinate (which corresponds to a starting node in the graph representation) to a destination point/coordinate (another node in the graph).
The cost of a path on a graph representation is then the sum of all the individual travel cost between nodes it traversed, or the sum of edge weights on the path. E.g., in Figure 3 the path is the orange line, it traverses from the origin (blue), over 8 nodes between the origin (blue) and destination (red), then to the destination. The travel cost is the sum of all the edge weights between the the traversed nodes. In this example, it is an unweighted graph so we can assume all edges have weight of 1 or unit (travel) cost).
To find a shortest path, we can either use BFS for unweighted graphs, or Dijsktra’s for weighted ones, see Figure 3 again for an example.
But one can imagine (and in this assignment, see task B) where the travel cost is not uniform, e.g., travelling up slope/gradients, on different surfaces etc, and we don’t have uniform travel cost between adjacent coordinates. Then the shortest path may not be the orange one anymore.
Figure 3: Shortest path found with Dijsktra’s algorithm. Note that while the shortest path may not be unique, the total length/cost is.
Before we finish this section, note that the graph representation used in the examples are undi-
rected, which assumes travelling from two adjacent coordinates, say A to B has the same cost as B to A, hence we don’t need direction as they convey the same information. But if the cost aren’t the same from A to B and B to A, then we need to use a directed (and weighted) graph representation.
2.4 Quick note about the coordinates system used
In this assignment, specifications and skeleton code implementation, the coordinates are based on (row, column) dimensions. Hence, the left most, bottom most coordinate on a map is row = 0, column = 0 or (0,0). In the example for either of the representations (Figure 2), the origin (blue) is row = 2, column = 0 or (2,0) and destination is row = 4, column = 5 or (4,5).
This concludes the background. In the following, we will describe the tasks of this assignment.
3 Tasks
The assignment is broken up into a number of tasks. Apart from Task A that should be completed ini- tially, all other tasks can be completed in an order you are more comfortable with, although completion of task C is likely to help with task D and we consider task D as a distinction level one.
Task A: Implement Dijkstra’s Algorithm for Path finding (4 marks)
To develop an initial approach to path finding, you should implement Dijkstra’s algorithm. For this task initially, if not specified, assume all locations and coordinates have unit cost to travel to the adjacent one, e.g., (2,1) to (2,2) has a unit cost/cost of 1 to travel between.
Given input, your implementation should return a (shortest) path between origin and destination. Note there may be more than one shortest path, hence we ask for a shortest path. A path should include the origin cooridinate, all coordinates between, and the destination coordinate.
Hint: For a graph representation, we can use Dijkstra’s algorithm as is. For a grid representation, you’ll need to consider how to implement Dijkstra’s on it. For both, we suggest to first figure it out conceptually, then translate into code.
Task B: Handling different Terrain (3 marks)
In maps, we frequently have locations that are of different surfaces, e.g., sand, gravel, mud etc. This can affect travelling speeds.
Up to this task, traversal between adjacent locations/coordinates are assumed to have a cost of 1. But in this task, now the costs can be greater than 1, and will be specified in a terrain parameter file (see Details of Files section for more details).
In this task, you’ll need to modify your data structures and algorithms to handle terrain cost greater than 1. This might mean a path that was shortest for uniform unit cost map will now be very costly, e.g., it has to go through many coordinates of high terrain cost such as mud. As an example, see Figure 4, where the original orange path of Figure 2b is no longer the shortest as it has to go through coordinates with high costs, e.g., coordinate (5,2) with cost 12. Instead the purple coloured path is the shortest.
Hint: you’ll need to consider how to translate this into the graph representation if you using that. There are at least two ways you can model this. One is to carefully consider what is the meaning of an edge weight in the graph representation, then whether you need a directed graph representation.
Task C: Handling multiple origins and destinations (3 marks)
Sometimes we can have multiple origin and destination points, e.g., we have a number of ambulances waiting at a number of hospitals (these are our origin locations) and we have a number of emergencies
Figure 4: Map with terrain cost greater than 1 (coordinates/cells with numbers). Corresponding shortest path is rediverted in the other direction because of the terrain costs.
to attend to (these are the destination locations). We want to send an ambulance to one of the cases asap, hence it doesn’t matter which hospital (origin) or to which emergency (destination), as long as the path is shortest.
In this task, you’ll modify your implementation to cater for multiple origin and/or destinations. Note that we just need to find a shortest path between any of the origins to any of the destinations.
As an example, see Figure 5. There are two origins and two destinations, hence four possible paths between the origins and destinations. Path labelled (1) and coloured orange is the shortest one among the four.
Figure 5: Map with multi-origin (blue) and multi-destinations (red). There are 4 possible paths, but the shortest one is the orange one, labelled (1).
Hint: Consider how Dijsktra’s searches for its shortest path.
Task D: Waypoints (3 marks)
Note this task is probably the hardest of the four and we consider it as an distinction level task, but you are welcome to tackle these in the order you find easiest or desire. In path finding, it is typical that we must visit a number of waypoints when traversing from origin to destination, e.g., in a game, the player sets some waypoints so their units can avoid certain enemies etc.
Figure 6: Map with multiple waypoints (yellow circles). Corresponding shortest path has to go through the waypoints instead of direct shortest path from origin to destination.
In this task, you are given a number of waypoints, and your path needs to traverse through all of them and be the shortest one that does.
Hint: There a number of solutions for this. But as a hint, consider task C and whether it has some similarities to task D.
4 Details for all tasks
To help you get started and to provide a framework for testing, you are provided with skeleton code that implements some of the mechanics of the path finding program. The main class (PathFinderTester) implements functionality of path finding, parsing parameters and read in the details of the map/surface that we are seeking a (shortest) path on. The list of main java files provided are listed in Table 1.
file
PathFinderTester.java
pathFinder/PathFinder.java
pathFinder/DijkstraPathFinder.java
map/Coordinate.java
map/PathMap.java
map/StdDraw.java
description
Class implementing basic framework of the data service. Do not modify useless have to.
Abstract class for path finding algorithms (in case you wanted to experiment with others). Can add to, but don’t modify existing methods.
Class implementing the Dijsktra’s path finding algorithm You need to implement this, minimum for task A.
Class implementing some coordinate functionality Can add to, but don’t modify existing methods, as visualisation relies on them.
Class implementing a basic grid representation. Can add to, but don’t modify existing methods, as visualisation relies on them.
Class implementing the visualisation. Do not modify. Table 1: Table of supplied Java files.
Note, you may modify the PathFinderTester class, but we strongly suggest you not to, as this contains the code to load input/output and call relevent methods in your implementations and you do
not want to break this. You may add java files and methods, but it should be within the structure of the skeleton code, i.e., keep the same directory structure. Similar to assignment 1, this is to minimise compiling and running issues. However, you should implement all the missing functionality in *.java files. However, ensure your structure compiles and runs on the core teaching servers. Note that the onus is on you to ensure correct compilation and behaviour on the core teaching servers before submission.
As a friendly reminder, remember how packages work and IDE like Eclipse will automatically add the package qualifiers to files created in their environments. This is a large source of compile errors, so remove these package qualifiers when testing on the core teaching servers – and this was the case for assignment 1 so please avoid this.
Compiling and Executing
To compile the files, run the following command from the root directory (the directory that PathFind- erTester.java is in):
javac -cp .:jopt-simple-5.0.2.jar PathFinderTester.java map/*.java pathFinder/*.java
Note that for Windows machine, remember to replace ’:’ with ’;’ in the classpath specifier (-cp part).
To run the framework:
java -cp .:jopt-simple.5.0.2.jar PathFinderTester [-v] [-o <path output file>] [-t
<terrain file>] [-w <waypoints file>] <main parameter file>
where
• optional [-v]: visualise map and (if implemented) discovered path.
• optional [-o <output file>]: for our testing purposes, outputs the discovered path to “output file”.
• optional [-t <terrain file>]: specify the loading of terrain information from “terrain file”.
• optional [-w <waypoints file>]: specify the loading of waypoint information from “waypoints
file”.
• main parameter file: name of the file that specifies the map, origin and destination and impass- able coordinates information.
We next describe the contents of the parameter files.
4.1 Details of Files
Main parameter file
This specifies the main configuration of the tasks and assignment, including: • number of rows and columns in the map
• list of origin coordinates in (row, column) format
• list of destination coordinates in (row, column) format
• list of impassable coordinates in (row, column) format
The exact format is as follows:
[number of rows in map] [number of columns in map]
[ List of row, col coordinates [ List of row, col coordinates [row column (coordinates) of
Using the example from Figure 2a,
77 20 45 22 32 42 12 13 23 33 24
First line, “7 7” is the number of
coordinate of the origin. Third line, “4 5” is the (row, column) coordinate of the destination. Fourth to end (starting at “2 2”) are the (row, column) coordinates of each impassable coordinate. So in this case, there are 8 impassable ones.
The skeleton code will parse and load these. We explain the format here so you can develop your own test cases. Examine the skeleton code, the origin and destination coordinates are loaded as List of coordinates, while the terrain information is loaded into the PathMap class itself.
Terrain parameter file
Coordinates that have terrain cost greater than 1 are listed in the terrain input files (all coordinates not mentioned in the terrain file are assumed to have unit cost (cost = 1)), which has the following format:
[row column (coordinates) terrain cost]
Using the example from Figure 4, the terrain parameter file is as follows:
5 2 12 6 2 10 539 446
We have added code in the provided skeleton that loads this information from the terrain parameter files and stores them as a Map (Coordinate, Terrain cost) structure that you can use to construct your approach to handle different terrain.
- 经济Economics
- 金融Finance
- 会计Accounting
- 工商管理Business Management
- 计算机computer science
- 商业分析business analysis
- 法律Law
- 管理Management
- 市场营销Marketing
- 哲学Philosophy
- 心理学Psychology
- 物理Physical
- 统计学statistics
- 电气工程electric engineering
- 化学chemistry
- 生物biology
- 数学mathematics
- 语言学linguistics
- 土木工程civil engineering
- 工程力学engineering mechanics
- 艺术art
PROFESSIONAL HELP!
在线咨询
立即下单
Wechat：THEend8_ 
Email：