Among Us You are playing the popular multiplayer murder mystery game Among U s1, in which there are one or more impostors among a group of crewmates on a spaceship. The impostors’ goal is to sabotage the spaceship by killing all their crewmates before the crew finishes their tasks; the crewmates win by either completing their tasks or ejecting the impostors out of the spaceship before they can kill everyone. Impostors have access to an underground vent network that allows them to quickly move across the spaceship without detection. If a crewmate dies, they become a “ghost”; ghosts can still complete their tasks, and they can travel without restriction throughout the map. In this project, you will be playing the roles of both an Impostor (Part A) and a ghost Crewmate (Parts B and C) to identify efficient routes through the spaceship that will help you win the game. In Impostor mode (Part A), you’ll be setting up the vent network to travel quickly between rooms. You need to make sure that you can access any room from any other room. However, excavating is expensive, so you also want to minimize the total distance of the network. In Ghost mode (Parts B and C), you can move freely across the map, and you want to finish your tasks as quickly as possible to win. You can fly through walls, and you want to find the optimal path to finish all your tasks and end at the first task you did. You may assume that there is one task per room to be completed. 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. 1On startup, your program, amongus , reads input from standard input (cin) describing the locations of the rooms. The map is a grid with the decontamination zone on the bottom left quadrant (see ‘Path Rules’). You will be given a list of M rooms with associated integer coordinates (x, y). Rooms are identified by integer indices which correspond to the order in which they are read in (the first room location corresponds to location 0, the second room location to location 1, etc.). For parts B and C you always start in the 0th room. Formally, the input will be formatted in this manner: The first line will contain a single number denoting the number of rooms on the map. 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). Sample:56 12 3-5 -4-1 60 -1 The above sample can be visualized as in the figure below, where the numbers shown are the room indices that starts at the 0-th room, and the blue line indicates the decontamination border (for more details, see the ‘Path Rules’ section) which separates the outer area from the lab: room 2 is in the lab, 4 is in decontamination, and the rest are in the outer area. 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. 2We represent the paths you take as a set of pairs of points or as a sequence of points. Your calculations should use Euclidean distanc e, and you should represent your distances as doubles. To connect rooms in Part A, you must only move between rooms in the same area. In order to reach rooms in the lab from the outer area (or vice-versa), you must first pass through a decontamination room. In Parts B and C, you are now a ghost (a minor inconvenience), and can fly directly from room to room. You move along the line segments that connect rooms. 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 lab that is located in the bottom left quadrant of the map. When first embarking on your journey (in Part A), you can travel using vents between different locations in the outer area. The lab is only accessible through decontamination , 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 lab by passing through a location in decontamination. 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 outer area locations that “cross” the lab can be connected by a direct path. The example below shows two validly connected outer area rooms, at locations A and B. In this example, there is a direct path from A to B, by using vents. When you are a ghost (in Parts B and C), you can fly directly from locations in the lab to locations in the outer area, and vice versa; in other words, you may ignore decontamination.2 “Path,” in this project, can be understood as a route between two locations. Important: For parts B and C, you always start at the 0-th room 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). Your program, amongus, should take the following case-sensitive command line options: 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 amongus runs (and therefore what it outputs).Print a short description of this program and its arguments and exit(0). Valid examples of how to execute the program:./amongus –mode MST (OK, but you must type the input by hand)./amongus -h < inputFile.txt (OK, -h happens before we realize there’s no -m)./amongus -m OPTTSP < inputFile.txt (OK, reads from a file on disk)./amongus -m BLAH (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. 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. This mode will devise a vent system that connects every room location while minimizing the total distance of vents needed. When the program is run in the MST mode, it should calculate and print out an MST connecting all of the room 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 the lab and the outer area. . Your MST cannot connect a room in the lab to one in the outer area, without passing through a room in decontamination. 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: weight node node node node…… The nodes are the room 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.020 12 41 31 4 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, butis not. If it is not possible to construct an MST for the rooms (i.e. if there are rooms in both the outer area and in the lab, with no decontamination rooms), your program should print the message “Cannot construct MST” to cerr and exit(1) . In this mode, you will figure out how to travel to every room and then return to your starting location. The route will always start at room index 0, visit every other room exactly once, and return to the starting point. Your job will thus be to solve the TSP (Traveling Salesperson Problem) and choose paths to room locations so as to minimize the total distance travelled. Euclidean (straight-line) distance is used here again to compute distances between rooms. Because you are now a ghost, you no longer have to worry about decontaminating; you can go from any room 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 room location (your starting location). You must visit every room 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 travelled – that is, the sum of the lengths of all 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. 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.640 4 2 3 1 or 31.640 1 3 2 4 In the case where we have a large number of possible rooms 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! 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” lecture slides is much slower. 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. We highly encourage the use of the STL for this project, with the exception of several prohibited features. Do not use: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 have no 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).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: PATH := /usr/um/gcc-6.2.0/bin:$(PATH)LD_LIBRARY_PATH := /usr/um/gcc-6.2.0/lib64LD_RUN_PATH := /usr/um/gcc-6.2.0/lib64 Turn in all of the following files: You must prepare a compressed tar archive (.tar.gz file) of all of your files to submit to the autograder. One way to do this is to have all of your files for submission (and nothing else) in one directory. In this directory, rundos2unix *; tar czvf ./submit.tar.gz *.cpp *.h* Makefile test-*.txtThis will prepare a suitable file in your working directory. If you’re using our Makefile , use the command make fullsubmit. Submit your project files directly to either of the two autograders at:https://g281-1.eecs.umich.edu/ or https://g281-2.eecs.umich.edu/. When the autograders are turned on and accepting submissions, there will be an announcement on Piazza. The autograders are identical and your daily submission limit will be shared (and kept track of) between them. You may submit up to four times per calendar day (more during the Spring). For this purpose, days begin and end at midnight (Ann Arbor local time). We will count only your best submission for your grade. If you would instead like us to use yourLAST submission, see the autograder FAQ page, or use this for m. Please make sure that you read all messages shown at the top section of your autograder results! These messages often help explain some of the issues you are having (such as losing points for having a bad Makefile or why you are segfaulting). Also be sure to check if the autograder shows that one of your own test files exposes a bug in your solution (at the bottom). Search the autograder results for the word “Hint” (without quote marks) for potentially useful information. 80 points — Your grade will be derived from correctness and performance (runtime). This will be determined by the autograder. On this project we expect a much broader spread of runtimes than on previous projects. As with all projects, the test cases used for the final grading are likely to be different. 10 points — Your program does not leak memory. Make sure to run your code under valgrind before each submit. This is also a good idea because it will let you know if you have undefined behavior (such as reading an uninitialized variable), which may cause your code to crash on the autograder.10 points — Student test file coverage (effectiveness at exposing buggy solutions). We also reserve the right to deduct up to 5 points for bad programming style, code that is unnecessarily duplicated, etc. In this project there is no single correct answer (unlike previous projects). Accordingly, the grading of your problem will not be as simple as a ‘diff’, but will instead be a result of evaluating your output. For example, if we gave you a square for Part A, you might choose any 3 of the 4 edges, and print them in any order, meaning there are 24 possible correct output files! Particularly for Part B, we expect to see greater variation in student output. Part B asks you to solve a hard problem, and with the given time constraints, we don’t actually expect your output to be optimal for all cases. The quality of your solutions may even vary from case to case. We want you to quickly produce solutions that are close to optimal. This inevitably creates tradeoffs between solution optimality and runtime. You may find it useful to implement more than one algorithm or heuristic that you use in Part B, and do some testing plus use the autograder to determine which works the best.. Your grade for Part B will be determined based on how close you are to the best solution, computed as a percentage. There’s a project tutorial video available: https://youtu.be/hdTrbU28pn k It will be difficult to get this project correct without visualizing your MSTs and TSP tours. We have provided a visualization tool on the Autograder that you can use; follow this link: https://g281-2.eecs.umich.edu/p4viz/ . Running your code (on CAEN or locally) using valgrind can help you find and remove undefined (buggy) behavior and memory leaks from your code. This can save you from losing points in the final run when you mistakenly believe your code to be correct. It is extremely helpful to compile your code with the following gcc options: - Wall -Wextra -Wvla -Wconversion -pedantic. This way the compiler can warn you about poor style and parts of your code that may result in unintended/undefined behavior. Make sure that you are using getopt_long() for handling command-line options. In order to ensure that your output is within the tolerable margins of error for the autograder to correctly grade your program you must run the following lines of code before you output anything to cout. We highly recommend that you simply put them at the top of main() so that you don’t forget about them. cout << std::setprecision(2); //Always show 2 decimal places cout << std::fixed; //Disable scientific notation for large numbers You will need to #include <iomanip> to use this code. If you use a stringstream for output, you should send these lines to your stringstream instead of cout. Don’t use a stringstream for output. One possible heuristic (NOT the only one, NOT an easy one) is to construct a starting point for your TSP tour by following MST edges and skipping previously visited vertices. By using this technique correctly, you can find a tour that is guaranteed to be no more than twice the optimal solution’s length (and use this “2x” check for debugging). You can then use this starting point to make adjustments and do better. This is not necessarily the best approach! It is one approach used to illustrate how a heuristic can be used, there are better ones out there. This example method is VERY hard to code. Do some research on other heuristics! Suppose locations are distributed in an input map as shown below: Below is an MST that would be formed from the above locations. Below is a path taken by strictly following the edges of the MST. However, by “cutting corners,” as described in the picture below, an effective TSP solution can be generated. This is possible because once a vertex is visited, it will not be visited again. In the above path that strictly follows the edges of the MST, the middle vertex is visited four times (visited after an outer vertex is visited). If the middle vertex is skipped after the first visit, a TSP tour shown below is achieved. The reason we bring up this ‘twice-around-the-tree’ heuristic is to state the theorem that the resulting tours are no worse than 2x the MST cost. The following is an explanation/proof sketch as to why the 2x bound is valid: If you perform a DFS traversal of a tree and return to the initial node, you have visited every edge exactly twice (“going in” and “returning”), so this gives you exactly double the cost/length of the MST (the fact that the tree is minimal is not important for the logic of the proof – this works for any tree). Since the tree is spanning, you have visited all locations. The only problem with this twice-around-the-tree self-intersecting path is that it’s not a tour. It can be turned into a tour by taking shortcuts (i.e., taking shortcuts is important not only to reduce the length). When considering other heuristics:3bound . As a consequence, your heuristic should also satisfy the 2x upper bound; if not, you can just implement the twice-around-the-tree heuristic. However, we do not require this because there are much better heuristics – ones that are faster and produce better results. Autograder test names are broken down by the mode used with each test: Test files that start with “C ” are much smaller in size than those that start with “A ” and “B ”. The number of rooms for such files is smaller than 40 as compared to tens of thousands of rooms for the others. The reason is that TSP is NP-complete and finding an optimal solution in a reasonable amount of time is only possible for small-sized problems. When you start submitting test files to the autograder, it will tell you (in the section called “Scoring student test files”) how many bugs exist, the number needed to start earning points, and the number needed for full points. It will also tell you how many are needed to start earning an extra submit/day!3 Such heuristics are also called approximation algorithms.
Shopping Cart
Reviews
There are no reviews yet.