Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.sql.*;
- public class tsp {
- static double[][] distances;
- public static void main(String args[]) {
- /* Variables to store data. */
- ArrayList<Town> towns = new ArrayList<Town>();
- ArrayList<Integer> int1 = new ArrayList<Integer>();
- /* Read all towns and store in data structure. */
- /*try {
- File file = new File("C:/Users/Silvio/Desktop/MAD/monumenti.txt");
- FileReader fileReader = new FileReader(file);
- BufferedReader bufferedReader = new BufferedReader(fileReader);
- String line;
- while ((line = bufferedReader.readLine()) != null) {
- // Get the data from each line.
- String[] data = line.split(",");
- int id = Integer.parseInt(data[0]) - 1; // Minus one as IDs start from 1. Plus 1 while printing.
- String name = data[1];
- double x = Double.parseDouble(data[2]);
- double y = Double.parseDouble(data[3]);
- // Store all the data as an object and store in arrayList.
- Town newTown = new Town(id, name, x, y);
- towns.add(newTown);
- }
- fileReader.close();
- } catch (IOException e) {
- e.printStackTrace();
- }*/
- //connessione con il database
- try {
- Connection myConn = (Connection) DriverManager.getConnection("jdbc:mysql://localhost:3306/db.triplan?useUnicode=true&useJDBCCompliantTimezoneShift=true&useLegacyDatetimeCode=false&serverTimezone=UTC", "root", "root");
- Statement myStmt = myConn.createStatement();
- Statement myStmt2 = myConn.createStatement();
- ResultSet myRs = myStmt.executeQuery("SELECT * FROM places;");
- ResultSet myRs2 = myStmt2.executeQuery("SELECT * FROM city;");
- //int count1 =0;
- while(myRs2.next()) {
- System.out.println(myRs2.getInt("idcity")+","+myRs2.getString("name_city"));
- //count1++;
- }
- Scanner sc = new Scanner(System.in);
- System.out.println("Inserisci id citta:\n");
- //Scanner input = new Scanner(System.in);
- int s_city = sc.nextInt();
- //Scanner sc = new Scanner(System.in);
- int count1=0;
- while(myRs.next()) {
- if(myRs.getInt("city_idcity")==s_city) {
- System.out.println(count1+1+","+ myRs.getString("name_places"));
- count1++;
- }
- }
- System.out.println("Inserisci id monumento:\t");
- //int indice = 0;
- int count = 0;
- //int index = 0;
- while(sc.hasNextInt()){
- int1.add(sc.nextInt());
- System.out.println("Inserisci id monumento:\t");
- if(sc.next().equals("exit")) {
- break;
- }
- }
- Iterator<Integer> it1 =int1.iterator();
- while(it1.hasNext()) {
- System.out.println(it1.next());
- }
- int1.add(sc.nextInt());
- //System.out.println("Inserisci id monumento:"+int1.get(index));
- //index++;
- System.out.println(int1);
- while(myRs.next()) {
- if(myRs.getInt("city_idcity")==s_city) {
- //System.out.println(count+1+","+ myRs.getString("name_places"));
- int id = count;
- String name = myRs.getString("name_places");
- double x = myRs.getDouble("latitude");
- double y = myRs.getDouble("longitude");
- if(int1.contains(id)) {
- Town newTown = new Town(id, name, x, y);
- towns.add(newTown);
- }
- count++;
- //indice++;
- }
- }
- sc.close();
- }catch(Exception exc) {
- exc.printStackTrace();
- }
- /* Find the distance between all the towns. Store results in a 2D array for reuse. */
- distances = new double[towns.size()][towns.size()];
- for(Town a : towns) {
- for(Town b : towns) {
- if(a.id==b.id) { // If a & b are the same town.
- distances[a.id][b.id] = 0;
- continue;
- }else {
- distances[a.id][b.id] = a.distanceTo(b); }
- // Find and store the distance between towns.
- }
- }
- /* Calculate all the possible solutions for the shortest route. */
- double bestDistance = 0.0;
- ArrayList<Integer> bestSquence = new ArrayList<Integer>();
- ArrayList<Integer> visitSequence = new ArrayList<Integer>();
- // For selecting starting point. Try everything as a starting point.
- try {
- Scanner input1 = new Scanner(System.in);
- System.out.print("Inserisci id monumento di partenza:\n");
- //Scanner input1 = new Scanner(System.in);
- int s_monument = input1.nextInt();
- visitSequence.add(s_monument);
- input1.close();
- for(Town t : towns){
- if(s_monument == t.id){
- /* Copy town's arrayList and use it to remove visited towns. */
- ArrayList<Town> toVisit = new ArrayList<Town>(towns);
- removeTown(t.id, toVisit); // Remove the starting town.
- /* Nearest neighbour algorithm. */
- double totalDistance = 0.0;
- //visitSequence.add(s_town);
- visitSequence.add((t.id+1)); // Save the visiting sequence as a string.
- int currentTownID = t.id;
- while(!toVisit.isEmpty()) { // Till we have visited all the towns.
- int nearestTownID = nearestTown(currentTownID, toVisit);
- visitSequence.add(nearestTownID+1); // Add to sequence. Plus 1 to get actual ID.
- totalDistance += distances[currentTownID][nearestTownID]; // Add the distance visited.
- removeTown(nearestTownID, toVisit); // Visit the nearest town.
- currentTownID = nearestTownID; // We are now in that town.
- }
- // If first time OR if current result is better.
- if(bestDistance == 0.0 || totalDistance < bestDistance) {
- bestDistance = totalDistance;
- bestSquence = visitSequence;
- }
- // System.out.println("Starting town: " + t.name + ". Travelled Distance: " + totalDistance);
- }
- }
- ArrayList<String> al = new ArrayList<String>();
- for(int m=0;m<bestSquence.size();m++){
- for(Town t1 : towns){
- if(t1.id==bestSquence.get(m)){
- al.add(t1.name);
- break;
- }
- }
- }
- System.out.println("\n\nBest sequence with total distance of " + bestDistance + ":\n\n" + al);
- }catch(NoSuchElementException e) {
- e.printStackTrace();
- }
- }
- /* Method to remove a town from ArrayList<Town>. */
- private static void removeTown(int town_id, ArrayList<Town> towns) {
- // Go through each item in the list till we find the town and remove.
- for(int i = 0; i < towns.size(); i++) {
- Town current = towns.get(i);
- if(current.id == town_id) { // Found the town.
- towns.remove(i); // Remove from the same array that was passed.
- break;
- }
- }
- }
- /* Method to find the nearest town from a list of towns that are available to visit. */
- private static int nearestTown(int town_id, ArrayList<Town> canVisit) {
- int nearestTownID = town_id;
- double nearestDistance = 0.0;
- for(int i = 0; i < distances[town_id].length; i++) {
- if(distances[town_id][i] == 0.0) continue; // Skip comparing with same town.
- // Skip if town ID is not in the list of town that we can visit.
- if(!hasTown(i, canVisit)) continue; // Cannot visit this town.
- // If no value for nearest distance, set this town to be the nearest. (Runs first time).
- if(nearestDistance == 0.0) {
- nearestTownID = i;
- nearestDistance = distances[town_id][i];
- continue;
- }
- // Check if current town's distance is shorter.
- if(distances[town_id][i] < nearestDistance) {
- nearestTownID = i;
- nearestDistance = distances[town_id][i];
- }
- }
- return nearestTownID;
- }
- /* Method to check if a town is in ArrayList<Town>. */
- private static boolean hasTown(int town_id, ArrayList<Town> towns) {
- // Go through each item in the list till we find the town.
- for(Town t : towns) {
- if(t.id == town_id) { // Found the town.
- return true; // Return true.
- }
- }
- return false; // Assume that we don't have the town.
- }
- /* Method to print out 2D array of doubles. */
- public static void printDistances(double[][] array) {
- for (double[] arr : array) {
- System.out.println(Arrays.toString(arr));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement