MultiThreaded Unidirectional TSP

Take your unidirectional TSP Java program, the one that works backwards from right to left, and make it multithreaded. For each row in the matrix, create an independent thread that works backwards from column n to column 1, calculating the minimum path from that column forward (to the right), as we discussed in class.

You will likely find your program does not work correctly because the threads are not synchronized. For the multithreaded approach to work correctly, each thread must wait after moving to the left one column for all the other threads to finish their column calculation. Then all the threads can move another column to the left. Do not worry about this now. You will introduce synchronization in a later assignment.

But you still want your code to work when correctly synchronized later. One way to do this now, a kludge for sure, is to have each thread nap(1000), that is sleep for one second, after it calculates the next column to the left. Try t.yield() instead and explain whether or not that worked too.

Have at least three classes in this program: a Matrix class that will contain the input data matrix, a Calculate class that will have one thread in it for each object created from it; and a driver class that has the main() method and creates all objects. The Matrix class will have accessor methods in it that return the value in the matrix for row and column arguments. The constructor for the Calculate class will contain a row parameter, telling the thread inside it which row of the matrix it is doing from right to left. The constructor will also have a Matrix object parameter so the thread can call the Matrix accessor methods. Here is some skeleton code.

Animate your program using First do the base assignment as specified above and turn it in. Then do an animation of it as a separate program.