Question: Write a Java program called hw5_2.java that reads an input graph data from a user. Then, it should present a path for the travelling salesman
Write a Java program called hw5_2.java 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 Monterey LA SF SD 12 Monterey LA 2 Monterey SD 7 Monterey SF 5 LA Monterey 2 LA SF 8 LA SD 3 SF Monterey 5 SF LA 8 SF SD 1 SD Monterey 7 SD LA 9 SD SF 1 |
The first line (= 4 in the example) indicates that there are four vertices in the graph. The following four lines describe the names of four cities such as Monterey, LA, SF, and SD. For the problem, you should assume that the first city (= Monterey in the example) is the starting city of the TSP. In addition, you can assume that the city name is always one word. 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 city, destination city, and cost. Thus, the input data describes a directed graph like below:
Sample Run 0: Assume that the user typed the following lines
4
Monterey
LA
SF
SD
12
Monterey LA 2
Monterey SD 7
Monterey SF 5
LA Monterey 2
LA SF 8
LA SD 3
SF Monterey 5
SF LA 8
SF SD 1
SD Monterey 7
SD LA 9
SD SF 1
This is the correct output. Your program should present the path and total cost in separate lines.
Path:Monterey->LA->SD->SF->Monterey
Cost:11
Sample Run 1: Assume that the user typed the following lines
5
Fresno
LA
SD
SF
NYC
6
Fresno SD 8
SD LA 7
SD NYC 3
LA NYC 100
SF Fresno 20
SF SD 19
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
Fresno
LA
SD
SF
NYC
7
Fresno SD 8
SD LA 7
SD NYC 3
LA NYC 100
SF Fresno 20
SF SD 19
NYC SF 50
This is the correct output of your program.
Path:Fresno->SD->LA->NYC->SF->Fresno
Cost:185
This is the directed graph of the input data:
[Hint]: To solve this problem, you can use all permutations with the cities, except the origin city. For example, there are three cities, LA, SF, and SD in the first sample run, except the origin city Monterey. To make the explanation easy, you can think that LA is number 1, SF is number 2, and SD is number 3. This is all permutations with the three cities
1, 2, 3
1, 3, 2
2, 1, 3,
2, 3, 1
3, 1, 2
3, 2, 1
For each permutation, you can calculate the cost. For example, in the case of the permutation 1, 2, 3, add the origin city at the very beginning and end to the permutation which generates 0, 1, 2, 3, 0. This list corresponds to the path Monterey -> LA -> SF -> SD -> Monterey. Therefore, the cost of this path is 18. Similarly, the next permutation (= 1, 3, 2) corresponds to Monterey -> LA -> SD -> SF -> Monterey. The cost is 11. This way, you can check all possible paths for the TSP.
This is a sample C++ program to display permutations: https://repl.it/@YBYUN/permutationsusingSTL
2 Monterey LA 2 8 8 3 3 9 5 5 1 SF SD 1 1 Fresno LA 8 7 20 SD 100 19 SF NYC Fresno LA 8 20 SD 100 19 3 SF NYC 50
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help