馃攳
Traveling Salesman Problem (TSP) By Nearest Neighbor - JAVA Prototype Project - YouTube
Channel: Prototype Project
[1]
this tutorial will cover solving the traveling
salesman problem with JAVA 8 and the nearest
[10]
neighbor algorithm i will start with a demo
of a prebuilt application and 2nd i will write
[20]
explain and run this application using an
eclipse ide now here each city is identified
[29]
by its lattitude and longitude coordinates
and the haversine formula is used to calculate
[38]
distances between cities and the application
will find and display the shortest route this
[47]
is a prebuilt application so if i go ahead
and run it so this is the initial route that
[58]
we have and it have this total distance and
we first pick Boston so the remaining cities
[69]
does not contain Boston and we check the distance
between this city and each one of the cities
[77]
here and we find that New York has the shortest
distance to Boston so we have those 2 cities
[87]
now in the shortest route and there not here
and we keep doing that so now we have Boston
[95]
New York and Chicago until we end up with
this route and the remaining cities in this
[114]
initial route is zero so the shortest route
found is this with this total distance and
[126]
if we run it again we get start from Houston
next i'll go ahead and create a new project
[145]
and it is gonna be running on Java 8 and it
will have a City class that will be in this
[174]
package and
a Route class
[194]
and a Nearest Neighbor class where the nearest
neighbor logic will be and a Driver class
[214]
with a main method
now the logic in the City class will be exactly
[226]
the same as in other traveling salesman projects
that we have done so a city is identified
[236]
by its name longitude and latitude which are
initialized from the constructor and the haversine
[248]
formula is used to calculate distances between
cities and the toString method will return
[256]
the name of this city and we have those 3
constants defined the earth equatorial radius
[264]
and converting degrees to radians and converting
km to miles and the route class will also
[275]
have the same code as in other traveling salesman
projects that we have done so we have an ArrayList
[293]
of cities in this route and we initialize
it with this constructor and we have a get
[303]
cities that return that ArrayList and calculate
total distances that calculates the distance
[311]
between city 1 and city 2 city 2 and city
3 etc and sum them them up and than add the
[320]
distance from the last city to the originating
city and we have a toString method that prints
[328]
out the cities in this route now going to
the Nearest Neighbor class here we will have
[343]
a find shortest route method that takes in
an ArrayList of initial cities
[360]
and returns the shortest route using the nearest
neighbor algorithm and here we are printing
[384]
this cities in the initial route and than
picking a city at random from the cities ArrayList
[397]
and i need this method update routes and what
it does is it removes the city the passed
[409]
in city from the cities ArrayList and add
it to the shortest route cities ArrayList
[424]
and also it prints the current shortest route
cities and the remaining route cities so we
[437]
will add that city the shortest route city
and remove it from cities and print out cities
[459]
in shortest route and the remaining cities
that are in the cities ArrayList and we will
[471]
be calling that method from here and we want
to keep removing cities from the cities ArrayList
[482]
and putting them in the shortest route cities
ArrayList so i'll have a while loop while
[490]
cities dot size bigger or equal to 1 and i
need a method that chooses the next city i'll
[501]
have this get next city method that uses Java
8 to measure the distance from the passed
[511]
in city to each one of the cities in the cities
ArrayList and returns the city with the minimum
[527]
distance we're doing min here and will call
that method from here and having this new
[546]
city we will call the update routes passing
it and this should do it for this class
[568]
and now going to the Driver class we will
have this ArrayList of cities so initial cities
[588]
and in main i will instantiate a Driver and
an ArrayList of cities and add all the initial
[605]
cities to this ArrayList and let me have a
convenience method that print the shortest
[620]
route
and i will use it to print the shortest route
[632]
so driver dot print shortest route and we
will instantiate a nearest neighbor instance
[642]
and call find shortest route on it which would
return the shortest route that we will print
[664]
next let's go ahead and test run this application
so this was the initial route with this distance
[684]
in miles and than we started by picking up
the New York from here and so this doesn't
[696]
have New York in it the remaining cities and
than we check the distance between New York
[703]
and each one of those cities and found the
shortest is with Boston so we pick Boston
[712]
and now this one doesn't have either New York
or Boston and same thing than we get to Chicago
[718]
and keep doing that until we have this ArrayList
of cities and we don't have any cities remaining
[731]
in the initial route so the shortest route
we found is this and it has this distance
[750]
and let's see what happens if we run it again
so started from Houston and we ended with this
[774]
shortest route having this distance
Most Recent Videos:
You can go back to the homepage right here: Homepage