EECS281- Project 4 Among Us Solved

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. 

 

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. ○ Do some web searching for “TSP heuristics”, don’t choose one worse than O(n​2​).

●       Use a visualization tool to help with debugging.

 

 

Map Input 
On 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:

5

6 1 

2 3 

-5 -4 

-1 6 

0 -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. 

 

Path Rules 
  

Distance 
2

We 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. 

 

The Lab 
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.​   

 

Other 
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).

 

Command Line Input 
Your program, amongus,​           should take the following case-sensitive command line options:​                                                                                                      

  

●       -m, --mode <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 amongus​ ​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:

./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.

 

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 
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.

  

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: 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.02 

0 1 

2 4 

1 3 

1 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:

1  2

is a possible valid edge of output, but  

2  1

is 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)​ .​

  

 

 

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 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.

 

 

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

0 4 2 3 1  

 

or

 

31.64

0 1 3 2 4  

 

Part B Only Description 
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!

  

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” 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.