Advertisement
Guest User

Untitled

a guest
Apr 27th, 2019
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.52 KB | None | 0 0
  1. import java.util.*;
  2. import java.sql.*;
  3. public class tsp {
  4.  
  5. static double[][] distances;
  6.  
  7. public static void main(String args[]) {
  8.  
  9. /* Variables to store data. */
  10. ArrayList<Town> towns = new ArrayList<Town>();
  11. ArrayList<Integer> int1 = new ArrayList<Integer>();
  12. /* Read all towns and store in data structure. */
  13. /*try {
  14. File file = new File("C:/Users/Silvio/Desktop/MAD/monumenti.txt");
  15. FileReader fileReader = new FileReader(file);
  16. BufferedReader bufferedReader = new BufferedReader(fileReader);
  17.  
  18. String line;
  19.  
  20. while ((line = bufferedReader.readLine()) != null) {
  21.  
  22. // Get the data from each line.
  23. String[] data = line.split(",");
  24.  
  25. int id = Integer.parseInt(data[0]) - 1; // Minus one as IDs start from 1. Plus 1 while printing.
  26. String name = data[1];
  27. double x = Double.parseDouble(data[2]);
  28. double y = Double.parseDouble(data[3]);
  29.  
  30. // Store all the data as an object and store in arrayList.
  31. Town newTown = new Town(id, name, x, y);
  32. towns.add(newTown);
  33.  
  34. }
  35.  
  36. fileReader.close();
  37.  
  38. } catch (IOException e) {
  39. e.printStackTrace();
  40. }*/
  41.  
  42. //connessione con il database
  43. try {
  44. Connection myConn = (Connection) DriverManager.getConnection("jdbc:mysql://localhost:3306/db.triplan?useUnicode=true&useJDBCCompliantTimezoneShift=true&useLegacyDatetimeCode=false&serverTimezone=UTC", "root", "root");
  45.  
  46. Statement myStmt = myConn.createStatement();
  47. Statement myStmt2 = myConn.createStatement();
  48.  
  49. ResultSet myRs = myStmt.executeQuery("SELECT * FROM places;");
  50. ResultSet myRs2 = myStmt2.executeQuery("SELECT * FROM city;");
  51. //int count1 =0;
  52. while(myRs2.next()) {
  53. System.out.println(myRs2.getInt("idcity")+","+myRs2.getString("name_city"));
  54. //count1++;
  55. }
  56. Scanner sc = new Scanner(System.in);
  57. System.out.println("Inserisci id citta:\n");
  58. //Scanner input = new Scanner(System.in);
  59. int s_city = sc.nextInt();
  60. //Scanner sc = new Scanner(System.in);
  61. int count1=0;
  62. while(myRs.next()) {
  63. if(myRs.getInt("city_idcity")==s_city) {
  64. System.out.println(count1+1+","+ myRs.getString("name_places"));
  65. count1++;
  66. }
  67. }
  68. System.out.println("Inserisci id monumento:\t");
  69. //int indice = 0;
  70. int count = 0;
  71. //int index = 0;
  72. while(sc.hasNextInt()){
  73.  
  74. int1.add(sc.nextInt());
  75. System.out.println("Inserisci id monumento:\t");
  76. if(sc.next().equals("exit")) {
  77. break;
  78. }
  79. }
  80. Iterator<Integer> it1 =int1.iterator();
  81. while(it1.hasNext()) {
  82. System.out.println(it1.next());
  83. }
  84.  
  85. int1.add(sc.nextInt());
  86. //System.out.println("Inserisci id monumento:"+int1.get(index));
  87. //index++;
  88. System.out.println(int1);
  89.  
  90.  
  91.  
  92.  
  93.  
  94. while(myRs.next()) {
  95. if(myRs.getInt("city_idcity")==s_city) {
  96. //System.out.println(count+1+","+ myRs.getString("name_places"));
  97. int id = count;
  98. String name = myRs.getString("name_places");
  99. double x = myRs.getDouble("latitude");
  100. double y = myRs.getDouble("longitude");
  101. if(int1.contains(id)) {
  102. Town newTown = new Town(id, name, x, y);
  103. towns.add(newTown);
  104. }
  105.  
  106. count++;
  107. //indice++;
  108. }
  109. }
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118. sc.close();
  119.  
  120. }catch(Exception exc) {
  121. exc.printStackTrace();
  122. }
  123.  
  124.  
  125.  
  126.  
  127. /* Find the distance between all the towns. Store results in a 2D array for reuse. */
  128. distances = new double[towns.size()][towns.size()];
  129.  
  130. for(Town a : towns) {
  131. for(Town b : towns) {
  132. if(a.id==b.id) { // If a & b are the same town.
  133. distances[a.id][b.id] = 0;
  134. continue;
  135. }else {
  136. distances[a.id][b.id] = a.distanceTo(b); }
  137.  
  138. // Find and store the distance between towns.
  139.  
  140. }
  141. }
  142.  
  143.  
  144.  
  145. /* Calculate all the possible solutions for the shortest route. */
  146.  
  147. double bestDistance = 0.0;
  148. ArrayList<Integer> bestSquence = new ArrayList<Integer>();
  149. ArrayList<Integer> visitSequence = new ArrayList<Integer>();
  150.  
  151. // For selecting starting point. Try everything as a starting point.
  152. try {
  153. Scanner input1 = new Scanner(System.in);
  154. System.out.print("Inserisci id monumento di partenza:\n");
  155.  
  156. //Scanner input1 = new Scanner(System.in);
  157. int s_monument = input1.nextInt();
  158. visitSequence.add(s_monument);
  159.  
  160. input1.close();
  161. for(Town t : towns){
  162. if(s_monument == t.id){
  163. /* Copy town's arrayList and use it to remove visited towns. */
  164. ArrayList<Town> toVisit = new ArrayList<Town>(towns);
  165. removeTown(t.id, toVisit); // Remove the starting town.
  166.  
  167. /* Nearest neighbour algorithm. */
  168.  
  169. double totalDistance = 0.0;
  170. //visitSequence.add(s_town);
  171. visitSequence.add((t.id+1)); // Save the visiting sequence as a string.
  172.  
  173. int currentTownID = t.id;
  174. while(!toVisit.isEmpty()) { // Till we have visited all the towns.
  175.  
  176. int nearestTownID = nearestTown(currentTownID, toVisit);
  177.  
  178. visitSequence.add(nearestTownID+1); // Add to sequence. Plus 1 to get actual ID.
  179. totalDistance += distances[currentTownID][nearestTownID]; // Add the distance visited.
  180.  
  181. removeTown(nearestTownID, toVisit); // Visit the nearest town.
  182. currentTownID = nearestTownID; // We are now in that town.
  183. }
  184.  
  185.  
  186. // If first time OR if current result is better.
  187. if(bestDistance == 0.0 || totalDistance < bestDistance) {
  188. bestDistance = totalDistance;
  189. bestSquence = visitSequence;
  190. }
  191.  
  192. // System.out.println("Starting town: " + t.name + ". Travelled Distance: " + totalDistance);
  193.  
  194. }
  195.  
  196. }
  197.  
  198. ArrayList<String> al = new ArrayList<String>();
  199. for(int m=0;m<bestSquence.size();m++){
  200. for(Town t1 : towns){
  201. if(t1.id==bestSquence.get(m)){
  202. al.add(t1.name);
  203. break;
  204. }
  205. }
  206. }
  207.  
  208.  
  209. System.out.println("\n\nBest sequence with total distance of " + bestDistance + ":\n\n" + al);
  210.  
  211. }catch(NoSuchElementException e) {
  212. e.printStackTrace();
  213. }
  214. }
  215.  
  216.  
  217. /* Method to remove a town from ArrayList<Town>. */
  218. private static void removeTown(int town_id, ArrayList<Town> towns) {
  219.  
  220. // Go through each item in the list till we find the town and remove.
  221. for(int i = 0; i < towns.size(); i++) {
  222. Town current = towns.get(i);
  223.  
  224. if(current.id == town_id) { // Found the town.
  225. towns.remove(i); // Remove from the same array that was passed.
  226. break;
  227. }
  228.  
  229. }
  230. }
  231.  
  232.  
  233. /* Method to find the nearest town from a list of towns that are available to visit. */
  234. private static int nearestTown(int town_id, ArrayList<Town> canVisit) {
  235. int nearestTownID = town_id;
  236. double nearestDistance = 0.0;
  237.  
  238. for(int i = 0; i < distances[town_id].length; i++) {
  239. if(distances[town_id][i] == 0.0) continue; // Skip comparing with same town.
  240.  
  241. // Skip if town ID is not in the list of town that we can visit.
  242. if(!hasTown(i, canVisit)) continue; // Cannot visit this town.
  243.  
  244. // If no value for nearest distance, set this town to be the nearest. (Runs first time).
  245. if(nearestDistance == 0.0) {
  246. nearestTownID = i;
  247. nearestDistance = distances[town_id][i];
  248. continue;
  249. }
  250.  
  251. // Check if current town's distance is shorter.
  252. if(distances[town_id][i] < nearestDistance) {
  253. nearestTownID = i;
  254. nearestDistance = distances[town_id][i];
  255. }
  256. }
  257.  
  258. return nearestTownID;
  259. }
  260.  
  261.  
  262. /* Method to check if a town is in ArrayList<Town>. */
  263. private static boolean hasTown(int town_id, ArrayList<Town> towns) {
  264.  
  265. // Go through each item in the list till we find the town.
  266. for(Town t : towns) {
  267. if(t.id == town_id) { // Found the town.
  268. return true; // Return true.
  269. }
  270. }
  271.  
  272. return false; // Assume that we don't have the town.
  273. }
  274.  
  275.  
  276. /* Method to print out 2D array of doubles. */
  277. public static void printDistances(double[][] array) {
  278. for (double[] arr : array) {
  279. System.out.println(Arrays.toString(arr));
  280. }
  281. }
  282.  
  283. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement