Java实现推销员问题_java – 基于推销员的旅行问题

素颜马尾好姑娘i 2022-11-10 01:17 128阅读 0赞

我正在编写一个基于旅行商问题的程序.用户确定其x和y坐标有四个城市.销售员总是从city1开始,最后到city1,因此有6条可能的路线.但是,每条路线都有一条等效路线,即route1与asroute6的距离相同.我已经解释了这一点.我还试图考虑if(route1或route6)和(route2或route4)是否具有相同的距离.该计划告诉你.

但是,每当四条甚至全部六条路线的距离相同时,程序只会告诉我四条或六条路线中有两条路线的距离最短.这是我需要帮助的.

import java.util.Scanner;

import java.lang.Math;

public class CityDistancesProgram

public static void main(String\[\] args)

Scanner keyboard = new Scanner(System.in);

//x and y coordinates of each city

int x1, y1, x2, y2, x3, y3, x4, y4;

//Variable for the distances of each route

double route1, route2, route3, route4, route5, route6;

//Since the distance from cityA to cityB is the same as the distance from cityB to cityA,

//these are all the possible combinations of distances between each city

double city1city2, city2city3, city3city4, city4city1, city2city4, city3city1;

double city2city1, city3city2, city4city3, city1city4, city4city2, city1city3;

double shortestRoute;

System.out.println("Enter the value of each city's x-coordinate and y-coordinate");

System.out.println(" ");

//First city

System.out.println("City 1's x-coordinate:");

x1 = keyboard.nextInt();

System.out.println("City 1's y-coordinate:");

y1 = keyboard.nextInt();

//Second city

System.out.println("City 2's x-coordinate:");

x2 = keyboard.nextInt();

System.out.println("City 2's y-coordinate:");

y2 = keyboard.nextInt();

//Third city

System.out.println("City 3's x-coordinate:");

x3 = keyboard.nextInt();

System.out.println("City 3's y-coordinate:");

y3 = keyboard.nextInt();

//Fourth city

System.out.println("City 4's x-coordinate:");

x4 = keyboard.nextInt();

System.out.println("City 4's y-coordinate:");

y4 = keyboard.nextInt();

System.out.println("City 1's coordinates are: (" + x1 + ", " + y1 +")");

System.out.println("City 2's coordinates are: (" + x2 + ", " + y2 +")");

System.out.println("City 3's coordinates are: (" + x3 + ", " + y3 +")");

System.out.println("City 4's coordinates are: (" + x4 + ", " + y4 +")");

//Computing all possible combinations of distance between each city

city1city2 = Math.sqrt((x1 - x2)\*(x1 - x2) + (y1 - y2)\*(y1 - y2)); //distance from city1 to city2

city3city1 = Math.sqrt((x1 - x3)\*(x1 - x3) + (y1 - y3)\*(y1 - y3)); //distance from city1 to city3

city4city1 = Math.sqrt((x1 - x4)\*(x1 - x4) + (y1 - y4)\*(y1 - y4)); //distance from city4 to city1

city2city3 = Math.sqrt((x2 - x3)\*(x2 - x3) + (y2 - y3)\*(y2 - y3)); //distance from city2 to city3

city3city4 = Math.sqrt((x3 - x4)\*(x3 - x4) + (y3 - y4)\*(y3 - y4)); //distance from city3 to city4

city2city4 = Math.sqrt((x2 - x4)\*(x2 - x4) + (y2 - y4)\*(y2 - y4)); //distance from city2 to city4

city2city1 = city1city2; //distance from city2 to city1

city3city2 = city2city3; //distance from city3 to city2

city4city3 = city3city4; //distance from city4 to city3

city1city4 = city4city1; //distance from city1 to city4

city4city2 = city2city4; //distance from city4 to city2

city1city3 = city3city1; //distance from city1 to city3

//Computing the distance of each possible route

route1 = city1city2 + city2city3 + city3city4 + city4city1;

route2 = city1city2 + city2city4 + city4city3 + city3city1;

route3 = city1city3 + city3city2 + city2city4 + city4city1;

route4 = city1city3 + city3city4 + city4city2 + city2city1;

route5 = city1city4 + city4city2 + city2city3 + city3city1;

route6 = city1city4 + city4city3 + city3city2 + city2city1;

System.out.println(" ");

System.out.println("The first route has a total distance of " + route1 + " km");

System.out.println("The second route has a total distance of " + route2 + " km");

System.out.println("The third route has a total distance of " + route3 + " km");

System.out.println("The fourth route has a total distance of " + route4 + " km");

System.out.println("The fifth route has a total distance of " + route5 + " km");

System.out.println("The sixth route has a total distance of " + route6 + " km");

shortestRoute = Math.min(Math.min(route1, Math.min(route2,route3)), Math.min(route4,Math.min(route5,route6)));

System.out.println(" ");

if(shortestRoute == route1 || shortestRoute == route6)

System.out.println("route1 and route6 have the shortest distance");

else if(shortestRoute == route2 || shortestRoute == route4)

System.out.println("route2 and route4 have the shortest distance");

else if(shortestRoute == route3 || shortestRoute == route5)

System.out.println("route3 and route5 have the shortest distance");

else if((shortestRoute == route1 || shortestRoute == route6) && (shortestRoute == route2 || shortestRoute == route4))

System.out.println("route1, route6, route2 and route4 have the shortest distance");

else if((shortestRoute == route1 || shortestRoute == route6) && (shortestRoute == route3 || shortestRoute == route5))

System.out.println("route1, route6, route3 and route5 have the shortest distance");

else if((shortestRoute == route3 || shortestRoute == route5) && (shortestRoute == route2 || shortestRoute == route4))

System.out.println("route3, route5, route2 and route4 have the shortest distance");

else

System.out.println("There is no shortest distance, they are all the same");

Java实现推销员问题_java – 基于推销员的旅行问题

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关基于遗传算法求解中国地图旅行商问题的 Matlab 实现

相关实现旅行售货员问题的回溯算法

相关华为OD 技术综合面，手撕代码真题整理（四二）：NP 完全问题 - 旅行推销员问题（TSP） | 区间调度问题 - 最大不重叠区间

相关华为OD 技术综合面，手撕代码真题整理（二四）：盗贼的背包 | 旅行推销员问题

相关实现旅行商问题算法（Java）

相关 Java实现推销员问题_java – 基于推销员的旅行问题

相关遗传算法解决旅行商问题JAVA

相关 P2672推销员

相关《世界上最伟大的推销员》阅读实践

相关《世界上最伟大的推销员》阅读分享