EECS 281 – Winter 2022 Programming Project 4 Gotta Catch ’em All! v1.1
Due Tuesday, April 19 before midnight
With just a Pikachu1, you, a Pokemon Trainer, have left Pallet Town to fill up your PokeDex and catch all the pokemon! Pokemon are located all over, and you can walk, surf, or fly2 to get from pokemon to pokemon. On your journey, you may face other Pokemon Trainers, who make traveling more difficult, but once you fight a trainer, you never have to fight him/her again. Your task is to identify the most efficient routes for you to travel.
In Trainer Evasion Mode (Part A), we assume you have not faced any trainers and you must fight some of them such that all pokemon in the country are reachable. You need to create Trainer-Free paths by fighting as few trainers as possible and by traveling the least distance (one metric will account for both of these).
Copyright By PowCoder代写 加微信 powcoder
In Champion Mode (Parts B and C), we assume you have visited all of the country, beaten every Trainer, and have access to Fly, meaning you can skip fighting trainers altogether and fly from pokemon to pokemon. You will be constructing a path (rather, a cycle, as you return home) to catch every pokemon while minimizing the distance traveled.
To be clear: these scenarios are separate; the program will create a plan for one or the other, but not both in the same run (though you may find that algorithms from one mode help with another mode).
In this project, your output does not need to be exactly the same as ours to be correct. As long as it provides a valid answer, and follows the rules for formatting output, it can be in a different order and still be correct.
Project Goals
● Understand and implement MST algorithms. Be able to determine whether Prim’s or Kruskal’s is more efficient for a particular scenario.
● Understand and implement a Branch and Bound algorithm. Develop a fast and effective bounding algorithm.
● Explore various heuristic approaches to achieving a nearly-optimal solution as fast as possible. ○ Dosomewebsearchingfor“TSPheuristics”,don’tchooseoneworsethanO(n2).
● Use a visualization tool to help with debugging.
1 Pikachu is the mascot of Pokemon; it is unimportant for the sake of this project.
2 Surfing is where a trainer rides a water-type pokemon to travel on water. Flying is where a trainer rides a flying-type pokemon to fly directly to different locations
Version 03-30-22
Written by many 281 staff
© 2022 Regents of the University of Michigan
On startup, your program, poke, reads input from standard input (cin) describing the locations of the pokemon in the country. The country is mapped on a grid with water on the bottom left quadrant (see ‘Path Rules’). You will be given a list of M pokemon in the country with associated integer coordinates (x, y). Pokemon are identified by integer indices which correspond to the order in which they are read in (the first pokemon coordinate you read corresponds to pokemon location 0, the second pokemon coordinate to pokemon location 1, etc.). For parts B and C you always start at the location of the 0-th pokemon.
Formally, the input will be formatted in this manner: The first line will contain a single number denoting the number of pokemon in the country. That will be followed by a list of integer x/y, coordinates in the form: x y. You may assume that the input will always be well-formed (it will always conform to this format and you do not need to error check). There may be additional blank lines at the end of the file (but nowhere else).
5 61 23 -5 -4 -1 6 0 -1
The above sample can be visualized as in the figure below, where the numbers shown are the pokemon indices that starts at the 0-th pokemon, and the blue line indicates the coastline (for more details, see the ‘Path Rules’ section) which separates land from sea: pokemon 2 is in the sea, 4 is on the coastline, the rest are on land..
There is more than one way to represent this configuration internally in your program, and this will affect your runtime. Choose your data structures wisely!
For Part A, there will always be at least two points. For Parts B and C, there will always be at least 3.
Path Rules
We represent the paths3 you take as a set of pairs of points or as a sequence of points. Your calculations should use Euclidean distance, and you should represent your distances as doubles.
In Part A, you may only walk and surf. In order to reach pokemon in the sea from the land (or vice-versa), you must first reach a pokemon on the coast.
In Parts B and C, you have access to Fly, meaning you can fly directly from location to location. You move along the line segments that connect pokemon. Please be very careful with rounding errors in your distance calculations; the autograder will allow you a 0.01 margin of error to account for rounding, but you should avoid rounding at intermediate steps.
There is a sea that is located in the bottom left quadrant of the map. When first embarking on your journey (in Part A), you must tread the sea with a pokemon with Surf (assume you have this). The sea is bounded by its coast, which consists of the negative portions of the x and y axes, including the origin (0, 0). In Part A, you may only enter and exit the sea by passing through a location on the coast. For example, you are not allowed to travel directly from (-5, -4) to (6, 1). You must first travel from (-5, -4) to (0, -1), and then from (0, -1) to (6, 1).
For the sake of simplicity, assume two land locations that “cross” the sea can be connected by a direct path. The example below shows two validly connected land pokemon, at locations A and B.
In this example, there is a direct path from A to B.
3 “Path,” in this project, can be understood as a route between two locations.
When you are a Champion (in Parts B and C), you have access to Fly, meaning you can fly directly from land locations to locations on the sea, and vice versa; in other words, you may ignore water limitations.
Important: For parts B and C, you always start at the 0-th pokemon location.
You are also not allowed to ‘wrap around the edges of the world’ (you cannot go above the top of the map to arrive at the bottom).
Command Line Input
Your program, poke, should take the following case-sensitive command line options:
● -m,–mode
This command line option must be specified, if it is not, print a useful error message to standard error (cerr) and exit(1). MODE is a required argument. Set the program mode to MODE. MODE must be one of MST, FASTTSP, or OPTTSP. The MODE corresponds to the algorithm poke runs (and therefore what it outputs).
● -h,–help
Print a short description of this program and its arguments and exit(0).
Valid examples of how to execute the program:
poke –mode MST
poke -h < inputFile.txt
poke -m OPTTSP < inputFile.txt
poke -m BLAH
(OK, but you must type the input by hand or copy/paste it)
(OK, -h happens before we realize there’s no -m; input ignored) (OK, reads from a file on disk)
(BAD mode following -m)
Remember that when we redirect input, it does not affect the command line. Redirecting input just sends the file contents to cin. You should not have to modify your code to allow this to work; the operating system will handle it.
We will not be specifically error-checking your command-line handling, however we expect that your program conforms with the default behavior of getopt_long(). Incorrect command-line handling may lead to a variety of difficult-to-diagnose problems.
Algorithms
Your program should run one and only one of the following modes at runtime depending on the mode option for that particular program call. We divide it into ‘parts’ for your convenience, though you may find that elements and algorithms of some parts can help with others.
Part A – MST mode Description
5 This mode will devise a path that visits every pokemon location while minimizing the total distance of that path.
When the program is run in the MST mode, it should calculate and print out an MST connecting all of the pokemon locations. You may use any MST algorithm to connect all the locations. Hint: Unless you want to implement both and compare, think about the nature of the graph (how many vertices and edges does it have?). You are free to adapt code from the lecture slides to fit this project, but you will want to carefully think about the data structures necessary to do each part (storing unnecessary data can go over memory limits). Your program must always generate one valid MST for each input.
Remember that in this part, you must respect the boundary between land and sea. Your MST cannot connect a pokemon in the sea to one on land, without passing through a pokemon on the coastline.
Output Format (for Part A only)
For the MST mode, you should print the total weight of the MST you generate by itself on a line; this weight is the sum of the weights of all edges in your MST (in terms of Euclidean distance). You should then print all edges in the MST. All output should be printed to standard output (cout).
The output should be of the format:
The nodes are the pokemon location numbers corresponding to the vertices of the MST and a pair of nodes on a given line of the output describes an edge in the MST from the first node to the second. To be clear, the weight should be formatted as a double (2 decimal point precision is enough - see Appendix A), and the node numbers should all be integer values when printed. For example, given the example input file above, your MST mode output might be:
19.02 01 24 13 14
You should also always print the pairs of vertices that describe an edge such that the index on the left has a smaller integer value than the index on the right. In other words:
is a possible valid edge of output, but
If it is not possible to construct an MST for all pokemon (i.e. if there are pokemon on both the land and in the sea, with no pokemon on the coastline), your program should print the message "Cannot construct MST" to cerr and exit(1).
Parts B & C (FASTTSP & OPTTSP mode)
Description (for both Parts B and C)
In this mode, you will figure out how to travel to every pokemon and then return to your starting location. The route will always start at pokemon index 0, visit every other pokemon exactly once, and return to the starting point. Your job will thus be to solve the TSP (Traveling Salesperson Problem) and choose paths to pokemon locations so as to minimize the total distance traveled. Euclidean (straight-line) distance is used here again to compute distances between pokemon. Because you have now discovered a flying pokemon, there is no longer any restrictions on land-coastline-sea; you can fly from any pokemon location to any other.
For FASTTSP mode, you do not need to produce an optimal TSP tour, but your solution should be close to optimal. Because your FASTTSP algorithm does not need to be perfectly optimal, we expect it to run much faster than finding a perfect optimal solution. Do some online searching for “TSP heuristics”. There are several types, some easier to implement, some with better path lengths, some both.
For OPTTSP mode, you must find an optimal solution to the TSP (the actual minimum Euclidean distance necessary). More on the differences between OPTTSP and FASTTSP modes will be discussed later.
For both methods:
You must start the tour from the 0-th pokemon location (your starting location).
You must visit every pokemon exactly once (there's no point in returning to a place already checked), and at the end of the tour, you must return back to the 0-th location.
The length of a tour is defined as the sum of all pairwise distances traveled - that is, the sum of the lengths of all of the paths taken (using Euclidean distance).
Your program must print the indices of the locations in an order such that the length of this tour is as small as possible. More details about how to accomplish this are listed below.
Output Format (for both Parts B and C)
You should begin your output by printing the overall length of your tour on a line. On the next line, output the nodes in the order in which you visit them. The initial node should be the starting location index and the last node should be the location number directly before returning back to the 0-th location. The nodes in your tour should be printed such that they are separated by a single space. There can be a space after the last location listed. All output should be printed to standard output (cout).
For example, if given the input file above, your program could produce:
31.64 04231
31.64 01324
Part B Only Description
When we have a large number of possible pokemon to visit, finding an optimal method for visiting all of them may be too slow, and you may grow old and die before completing your task. You can use heuristics instead to find nearly-optimal tours. A heuristic is a problem-solving method (an algorithm) that can produce a good answer that is not necessarily the best answer. For example, you can skip a branch speculatively rather than waiting to know for a fact that it can be skipped. There are many other simple heuristic techniques, such as starting with a random tour and trying to improve it by small changes.
You should be able to produce a solution to the Traveling Salesperson Problem (TSP) that is as close as possible to the optimal tour length (though it does not need to be optimal). In the best case, your produced tour length will equal the optimal tour length.
You are allowed to use any combination of algorithms for this section that we have covered in class, including the MST algorithm you wrote for Part A.
You will need to be creative when designing your algorithms for this section. You are free to implement any other algorithm you choose, so long as it meets the time and memory constraints. However, you should not use any advanced algorithms or formulas (such as Simulated Annealing, Genetic Algorithms and Tabu search - they are too slow) that are significantly different from what has been covered in class. Instead, creatively combine the algorithms that you already know and come up with concise optimizations. Your heuristic will very likely be greedy in some way, but there are different ways to be greedy! Just make sure to limit yourself to heuristics whose time complexity is O(n2).
Part C Only Description
To find an optimal tour, you could start with the brute force method of exhaustive enumeration that evaluates every tour and picks a smallest tour. By structuring this enumeration in a clever way, you could determine that some branches of the search cannot lead to optimal solutions. For example, you could compute lower bounds on the length of any full tour that can be found in a given branch. If such a lower bound exceeds the cost of a full solution you have found previously, you can skip this branch as hopeless. If implemented correctly, such a branch-and-bound method should always produce an optimal solution. It will not scale as well as sorting or searching algorithms do for other problems, but it should be usable with a small number of locations. Clever optimizations (identifying hopeless branches of search early) can make your algorithm a hundred times faster. Drawing TSP tours on paper and solving small location configurations to optimality by hand should be very useful. Remember that there is a tradeoff between the time it takes to run your bounding function and the number of branches that bound lets you prune.
MAKE SURE that you use the version of genPerms() presented in either the “Project 4 Tutorial” or the “Backtracking BB TSP” lecture slides. The one presented earlier in the semester, in the “Stacks and Queues”lectureslidesismuchslower. ThereisacopyofthecorrectcodeonCanvas(intheProject 4 folder) in the file named genPerms.txt, which is safe to copy from (PDF files are not).
Given an input set of N locations defined by integer coordinates, your job is to produce an optimal tour using branch-and-bound algorithms. Your program should always produce the shortest possible tour as a solution,
even if computing that solution is time-consuming. You will be given a 35-second cpu time limit to generate your solution. If your program does not produce a valid solution, it will fail the test case. Your solution will also be judged by time and space budgets as per previous projects.
Libraries and Restrictions
We highly encourage the use of the STL for this project, with the exception of several prohibited features. Do not use:
● The C++11 regular expressions library
● The STL thread/atomics libraries (which spoil runtime measurements)
● Shared or unique pointers.
● Other libraries (e.g., boost, pthreads, etc).
Testing and Debugging
Part of this project is to prepare several test files that will expose defects in buggy solutions - your own or someone else’s. As this should be useful for testing and debugging your programs, we recommend that you first try to catch a few of our intentionally-buggy solutions with your test files, before completing your solution. The autograder will also tell you if one of your own test files exposes bugs in your solution.
Each test that you submit should consist of an input file. When we run your test files on one of intentionally-buggy project solutions, we compare the output to that of a correct project solution. If the outputs differ, the test file is said to expose that bug.
Test files should be named test-n-MODE.txt where 1 ≤ n ≤ 10. The autograder’s buggy solutions will run your test files in the specified MODE. The mode must be MST, FASTTSP, or OPTTSP.
Your test files may not have more than 10 coordinates in any one file. You may submit up to 10 test files (though it is possible to get full credit with fewer test files). The tests the autograder runs on your solution are NOT limited to 10 coordinates in a file; your solution should not impose any size limits (as long as sufficient system memory is available).
Submitting to the Autograder
Do all of your work (with all needed source code files, as well as test files) in some directory other than your home directory. This will be your "submit directory". Before you turn in your code, be sure that:
● Every source code and header file contains the following project identifier in a comment at the top of the file:
● //ProjectIdentifier:5949F553E20B650AB0FB2266D3C0822B13D248B0
● The Makefile must also have this identifier (in the first TODO block)
● You have deleted all .o files and your executable(s). Typing ‘make clean’ shall accomplish this.
● Your makefile is called Makefile. Typing ‘make -R -r’ builds your code without errors and generates
an executable file called poke. The command-line options -R and -r disable automatic build rules, which will not work on the autograder.
● Your Makefile specifies that you are compiling with the gcc optimization option -O3. This is extremely important for getting all of the performance points, as -O3 can speed up code by an order of magnitude.
● Your test files are named test-n-MODE.txt and no other project file names begin with test. Up to 10
test files may be submitted. The “mode” portion of the filename must be MST, OPTTSP or FASTTSP.
● The total size of your program and test files does not exceed 2MB.
● You don't have any unnecessary files (including temporary files created by your text editor and
compiler, etc) or subdirectories in your submit directory (i.e. the .git folder used by git source code
management).
● Your code compiles and runs correctly using version 6.2.0 of the g++ compiler. This is available on the
CAEN Linux systems (that you can access via login.engin.umich.edu). Even if everything seems to work on another operating system or with different versions of GCC, the course staff will not support anything other than GCC 6.2.0 running on Linux (students using other compilers and OS did observe incompatibilities). To compile with g++ vers
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com