Question

In: Computer Science

Write a Java program that reads an input graph data from a user. Then, it should...

Write a Java program that reads an input graph data from a user. Then, it should present a path for the travelling salesman problem (TSP). In the assignment, you can assume that the maximum number of vertices in the input graph is less than or equal to 20.

Input format: This is a sample input from a user.

4

12

0 1 2

0 3 7

0 2 5

1 0 2

1 2 8

1 3 3

2 0 5

2 1 8

2 3 1

3 0 7

3 1 9

3 2 1

0

The first line (= 4 in the example) indicates that there are four vertices in the graph. The next line (= 12 in the example) indicates the number of edges in the graph. The remaining 12 lines are the edge information with the “source vertex”, “destination vertex”, and “cost”. The last line (= 0 in the example) indicates the starting vertex of the travelling salesman problem. This is the graph with the input information provided.

Sample Run 0: Assume that the user typed the following lines

4

12

0 1 2

0 3 7

0 2 5

1 0 2

1 2 8

1 3 3

2 0 5

2 1 8

2 3 1

3 0 7

3 1 9

3 2 1

0

This is the correct output. Your program should present the path and total cost in separate lines.

Path:0->1->3->2->0

Cost:11

Sample Run 1: Assume that the user typed the following lines

5

6

0 2 7

3 1 20

0 4 3

1 0 8

2 4 100

3 0 19

3

This is the correct output.

Path:

Cost:-1

Note that if there is no path for the TSP, your program should present empty path and -1 cost.

Sample Run 2: Assume that the user typed the following lines

5

7

0 2 8

2 1 7

2 4 3

1 4 100

3 0 20

3 2 19

4 3 50

3

This is the correct output of your program.

Path:3->0->2->1->4->3

Cost:185

This is the directed graph of the input data:

[Hint]: To solve this problem, you can use all permutations of the vertices, except the starting vertex. For example, there are three vertices 1, 2, and 3, in the first sample run, except the starting vertex 0. This is all permutations with the three vertices

            1, 2, 3

            1, 3, 2

            2, 1, 3,

            2, 3, 1

            3, 1, 2

            3, 2, 1

Solutions

Expert Solution

Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming)

Travelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Note the difference between Hamiltonian Cycle and TSP. The Hamiltoninan cycle problem is to find if there exist a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.

For example, consider the graph shown in figure on right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.

The problem is a famous NP hard problem. There is no polynomial time know solution for this problem.

Following are different solutions for the traveling salesman problem.

Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.

Time Complexity: Θ(n!)

Dynamic Programming:
Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting and ending point of output. For every other vertex i (other than 1), we find the minimum cost path with 1 as the starting point, i as the ending point and all vertices appearing exactly once. Let the cost of this path be cost(i), the cost of corresponding Cycle would be cost(i) + dist(i, 1) where dist(i, 1) is the distance from i to 1. Finally, we return the minimum of all [cost(i) + dist(i, 1)] values. This looks simple so far. Now the question is how to get cost(i)?
To calculate cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems. Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i.
We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset.

If size of S is 2, then S must be {1, i},
 C(S, i) = dist(1, i) 
Else if size of S is greater than 2.
 C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets don’t have nth in them.
Using the above recurrence relation, we can write dynamic programming based solution. There are at most O(n*2n) subproblems, and each one takes linear time to solve. The total running time is therefore O(n2*2n). The time complexity is much less than O(n!), but still exponential. Space required is also exponential. So this approach is also infeasible even for slightly higher number of vertices.

Travelling Salesman Problem | Set 2 (Approximate using MST)

Last Updated: 13-09-2018

We introduced Travelling Salesman Problem and discussed Naive and Dynamic Programming Solutions for the problem in the previous post,. Both of the solutions are infeasible. In fact, there is no polynomial time solution available for this problem as the problem is a known NP-Hard problem. There are approximate algorithms to solve the problem though. The approximate algorithms work only if the problem instance satisfies Triangle-Inequality.

Triangle-Inequality: The least distant path to reach a vertex j from i is always to reach j directly from i, rather than through some other vertex k (or vertices), i.e., dis(i, j) is always less than or equal to dis(i, k) + dist(k, j). The Triangle-Inequality holds in many practical situations.
When the cost function satisfies the triangle inequality, we can design an approximate algorithm for TSP that returns a tour whose cost is never more than twice the cost of an optimal tour. The idea is to use Minimum Spanning Tree (MST). Following is the MST based algorithm.

Algorithm:
1) Let 1 be the starting and ending point for salesman.
2) Construct MST from with 1 as root using Prim’s Algorithm.
3) List vertices visited in preorder walk of the constructed MST and add 1 at the end.

Let us consider the following example. The first diagram is the given graph. The second diagram shows MST constructed with 1 as root. The preorder traversal of MST is 1-2-4-3. Adding 1 at the end gives 1-2-4-3-1 which is the output of this algorithm.











In this case, the approximate algorithm produces the optimal tour, but it may not produce optimal tour in all cases.


How is this algorithm 2-approximate? The cost of the output produced by the above algorithm is never more than twice the cost of best possible output. Let us see how is this guaranteed by the above algorithm.
Let us define a term full walk to understand this. A full walk is lists all vertices when they are first visited in preorder, it also list vertices when they are returned after a subtree is visited in preorder. The full walk of above tree would be 1-2-1-4-1-3-1.
Following are some important facts that prove the 2-approximateness.
1) The cost of best possible Travelling Salesman tour is never less than the cost of MST. (The definition of MST says, it is a minimum cost tree that connects all vertices).
2) The total cost of full walk is at most twice the cost of MST (Every edge of MST is visited at-most twice)
3) The output of the above algorithm is less than the cost of full walk. In above algorithm, we print preorder walk as output. In preorder walk, two or more edges of full walk are replaced with a single edge. For example, 2-1 and 1-4 are replaced by 1 edge 2-4. So if the graph follows triangle inequality, then this is always true.

From the above three statements, we can conclude that the cost of output produced by the approximate algorithm is never more than twice the cost of best possible solution.

We have discussed a very simple 2-approximate algorithm for the travelling salesman problem. There are other better approximate algorithms for the problem. For example Christofides algorithm is 1.5 approximate algorithm.


Related Solutions

Write a C++ or Java program that reads an input graph data from a user. Then,...
Write a C++ or Java program that reads an input graph data from a user. Then, it should present a path for the travelling salesman problem (TSP). In the assignment, you can assume that the maximum number ofvertices in the input graph is less than or equal to 20. Input format: This is a sample input from a user. 4 12 0 1 2 0 3 7 0 2 5 1 0 2 1 2 8 1 3 3 2...
Write a Java program (name it PasswordTest) that reads from the user a string input (representing...
Write a Java program (name it PasswordTest) that reads from the user a string input (representing a password) and determines whether the password is “Valid Password” or “Invalid Password”. A valid password has at least 7 characters and includes at least one lower-case letter, at least one upper-case letter, at least one digit, and at least one character that is neither a letter nor a digit. Your program will need to check each character in the string in order to...
Write a JAVA program that reads in a string from standard input and determines the following:...
Write a JAVA program that reads in a string from standard input and determines the following: - How many vowels are in the string (FOR THE PURPOSE OF THIS PROGRAM 'Y' is NOT considered a vowel)? - How many upper case characters are in the string? - How many digits are in the string? - How many white space characters are in the string? - Modify the program to indicate which vowel occurs the most. In the case of a...
Java Write a program that reads 4 integer numbers from the user combine it into a...
Java Write a program that reads 4 integer numbers from the user combine it into a single number. You need to ask the user to first specify how to combine the numbers (forward or backward). Note that for the backward option you need to check that the last digits should be 0, also for the forward option you need to check that the fist digit is not 0. Use for loops and switch for the menu.                       4. Write an application...
in. java Write a program that reads a string from the user, and creates another string...
in. java Write a program that reads a string from the user, and creates another string with the letters from in reversed order. You should do this using string concatenation and loops. Do not use any method from Java that does the work for you. The reverse string must be built. Do not just print the letters in reversed order. Instead, concatenate them in a string. --- Sample run: This program will create a string with letters in reversed order....
Write Java program that asks a user to input a letter, converts the user input to...
Write Java program that asks a user to input a letter, converts the user input to uppercase if the user types the letter in lowercase, and based on the letter the user the user enters, display a message showing the number that matches the letter entered. For letters A or B or C display 2 For letter D or E or F display 3 For letter G or H or I display 4 For letter J or K or L...
Write Java program Lab52.java which reads in a line of text from the user. The text...
Write Java program Lab52.java which reads in a line of text from the user. The text should be passed into the method: public static String[] divideText(String input) The "divideText" method returns an array of 2 Strings, one with the even number characters in the original string and one with the odd number characters from the original string. The program should then print out the returned strings.
Write a java program. The program requirements are: the program will let the user input a...
Write a java program. The program requirements are: the program will let the user input a starting number, such as 2.  It will generate ten multiplication problems ranging from 2x1 to 2x10.  For each problem, the user will be prompted to enter the correct answer. The program should check the answer and should not let the user advance to the next question until the correct answer is given to the question being asked currently. After testing a total of 10 multiplication problems,...
Write a program that reads a line of text input by the user and places each...
Write a program that reads a line of text input by the user and places each word in a TreeSet. Print the elements of the TreeSet to the screen. This will cause the elements to be printed in ascending order. Using Eclipse for this. TreeSetUse.java.
JAVA Take in a user input. if user input is "Leap Year" your program should run...
JAVA Take in a user input. if user input is "Leap Year" your program should run exercise 1 if user input is "word count" your program should run exercise 2 Both exercises should run in separate methods Exercise 1: write a java method to check whether a year(integer) entered by the user is a leap year or not. Exercise 2: Write a java method to count all words in a string.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT