Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums  General SQL Server Forums  Script Library  Traveling Salesman Problem Algorithm

Author  Topic

mynameispaulie
Starting Member

2 Posts

 Posted - 2012-03-06 : 12:49:01 I created this brute force algorithm to solve the traveling salesman problem using T-SQL in a SQL Server database class I took some time ago and I was just wondering what the experts thought of it.I believe it gives the correct solution although I don't know if anyone has a more complex comprehensive test. I also believe it works faster than similar algorithms implemented in other languages as it uses the speed of T-SQL.NOTE: I understand that the brute force method is not an elegant solution for solving the traveling salesman problem and is impractical for anything over 8 cities (I will post my times) but the assignment was to create a brute force algorithm using T-SQL.I received an A+ for my project but I still wondered what the real experts thought. I am fully prepared to get ripped to shreads. :-]`---Create tablesdrop table ROUTESgodrop table CITIESgocreate table CITIES ( NAME varchar(30) primary key)gocreate table ROUTES ( FROM_CITY varchar(30) references CITIES, TO_CITY varchar(30) references CITIES, MILES float not null, primary key (from_city, to_city))go---Create view to show all routes, because it is an undirected graphdrop view ALL_ROUTESgocreate view ALL_ROUTES (FROM_CITY, TO_CITY, MILES) as select FROM_CITY, TO_CITY, MILES from ROUTES union select TO_CITY, FROM_CITY, MILES from ROUTESgo---Procedure to rotate values in #array to create all permutations of the possible paths --- using all cities except the startCitydrop procedure rotategocreate procedure rotate @count intas ---Declare temp variable declare @temp varchar(30), @i int ---Save first value set @temp = (select NAME from #array where id = 1) set @i = 0 ---Shift all values to the left while (@i < @count) begin update #array set ID = @i where ID = @i + 1 set @i = @i + 1 end ---Add temp value to the end update #array set ID = @count where ID = 0go---Procedure to test and save permutation if it is a good route that existsdrop procedure savePermgocreate procedure savePerm @count int, @startCity varchar(30)as ---Allow for @startCity at beginning of route set @count = @count + 1 ---Declare and initialize needed variables declare @i int, @value varchar(1000), @prevCity varchar(30), @nextCity varchar(30), @totalMiles int, @currentMiles int, @goodRoute int, @numRoutes int set @i = 1 set @value = @startCity set @prevCity = @startCity set @nextCity = (select NAME from #array where ID = 1) set @totalMiles = 0 set @currentMiles = 0 set @goodRoute = 1 ---Loop through permutation array while (@i < @count) begin set @i = @i + 1 ---See if such a path exists in the routes table set @numRoutes = (select COUNT(*) from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @nextCity) ---If a path exists if @numRoutes > 0 begin ---Get the number of miles and add to total miles set @currentMiles = (select MILES from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @nextCity) set @totalMiles = @totalMiles + @currentMiles ---Store good route set @value = @value + '->' + @nextCity ---Get next city in permutation array set @prevCity = @nextCity set @nextCity = (select NAME from #array where ID = @i) end ---If no path exists else begin ---This route is no good, set the exit condition to exit the loop set @goodRoute = 0 set @i = @count end end ---One more time to add @startCity to end of route set @numRoutes = (select COUNT(*) from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @startCity) if @numRoutes > 0 begin set @currentMiles = (select MILES from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @startCity) set @totalMiles = @totalMiles + @currentMiles set @value = @value + '->' + @startCity end else begin set @goodRoute = 0 end ---If got this far and route is good, save to perms table if @goodRoute = 1 begin insert into #perms values(@value, @totalMiles) endgo---Recursive procedure to create all possible permutations of the possible paths --- using all cities except the startCitydrop procedure permutegocreate procedure permute @size int, @n int, @startCity varchar(30), @val1 varchar(30), @val2 varchar(30)as ---Declare and initialize neede variables declare @i int, @permuteVar int, @rotateVar int, @val1pos int, @val2pos int, @max int set @i = @size - @n ---If a permutation is ready for checking call savePerm if @size = @n begin ---Limit to half of permutations, --- only care about routes where arbitrary city 1 is before arbitrary city 2 set @val1pos = (select ID from #array where NAME = @val1) set @val2pos = (select ID from #array where NAME = @val2) if (@val1pos < @val2pos) begin exec savePerm @size, @startCity end end else begin ---Recursively call itself and then rotate values in array to generate all permutations while (@i > 0) begin set @permuteVar = @n + 1 exec permute @size, @permuteVar, @startCity, @val1, @val2 set @rotateVar = @size - @n exec rotate @rotateVar set @i = @i - 1 end endgo---Main procedure to get answer for TSP routedrop procedure getTSPRoutegocreate procedure getTSPRoute @startCity varchar(30)as ---Create array of cities, --- needs AUTO_ID and ID because rotate function wont work with IDENTITY column create table #array (AUTO_ID int identity, ID int, NAME varchar(30)) insert into #array select 0, NAME FROM cities where NAME <> @startCity update #array set ID = AUTO_ID ---Create table to store good permutations create table #perms (ROUTE_PATH varchar(1000), MILES int) ---Get 2 arbitrary cities, so that only routes where city 1 is before city 2 will be looked at declare @val1 varchar(30), @val2 varchar(30), @size int set @val1 = (select top 1 NAME from CITIES where NAME <> @startCity order by name) set @val2 = (select top 1 NAME from CITIES where NAME <> @startCity order by name desc) ---Get size of city array for number of cities set @size = (select COUNT(*) from #array) ---Call recursive permute function to generate all possible permutations of the possible paths --- using all cities except the startCity exec permute @size, 0, @startCity, @val1, @val2 ---When done select the shortest route from the perms table of good routes select ROUTE_PATH, MIN(MILES) as MILES from #perms group by ROUTE_PATH having MIN(MILES) = (select MIN(miles) from #perms)go``---**************************************************************************************************************************--- Test attempt 1--- 5 cities--- Running time: 2 secondsdelete from routesdelete from citiesinsert into cities values ('A')insert into cities values ('B')insert into cities values ('C')insert into cities values ('D')insert into cities values ('E')insert into routes values ('A', 'B', 5)insert into routes values ('A', 'C', 20)insert into routes values ('A', 'D', 28.28)insert into routes values ('A', 'E', 20)insert into routes values ('B', 'C', 15)insert into routes values ('B', 'D', 25)insert into routes values ('B', 'E', 20.62)insert into routes values ('C', 'D', 20)insert into routes values ('C', 'E', 28.28)insert into routes values ('D', 'E', 20)goexec getTSPRoute 'A'---**************************************************************************************************************************--- Test attempt 2--- 8 cities--- Running time: 5 secondsdelete from routesdelete from citiesinsert into cities values ('A')insert into cities values ('B')insert into cities values ('C')insert into cities values ('D')insert into cities values ('E')insert into cities values ('F')insert into cities values ('G')insert into cities values ('H')insert into routes values ('A', 'B', 200)insert into routes values ('B', 'C', 300)insert into routes values ('C', 'D', 200)insert into routes values ('D', 'E', 300)insert into routes values ('E', 'F', 100)insert into routes values ('F', 'G', 200)insert into routes values ('G', 'H', 250)insert into routes values ('H', 'A', 250)insert into routes values ('D', 'F', 200)insert into routes values ('E', 'G', 250)insert into routes values ('A', 'E', 50)insert into routes values ('B', 'E', 50)goexec getTSPRoute 'A'---**************************************************************************************************************************--- Test attempt 3--- 9 cities--- Running time: 41 secondsdelete from routesdelete from citiesinsert into cities values ('New York')insert into cities values ('Washington')insert into cities values ('Chicago')insert into cities values ('St. Louis')insert into cities values ('Dallas')insert into cities values ('Denver')insert into cities values ('Phoenix')insert into cities values ('Los Angeles')insert into cities values ('San Francisco')insert into routes values ('New York', 'Washington', 200)insert into routes values ('New York', 'Chicago', 700)insert into routes values ('St. Louis', 'Washington', 700)insert into routes values ('St. Louis', 'Chicago', 250)insert into routes values ('St. Louis', 'Dallas', 550)insert into routes values ('St. Louis', 'Denver', 800)insert into routes values ('Chicago', 'Denver', 900)insert into routes values ('San Francisco', 'Denver', 950)insert into routes values ('San Francisco', 'Los Angeles', 350)insert into routes values ('Phoenix', 'Los Angeles', 350)insert into routes values ('Phoenix', 'Dallas', 900)goexec getTSPRoute 'New York'---**************************************************************************************************************************--- Test attempt 4--- 10 cities--- Running time: 6 minutes 34 secondsdelete from routesdelete from citiesinsert into cities values ('New York')insert into cities values ('Washington')insert into cities values ('Miami')insert into cities values ('Chicago')insert into cities values ('St. Louis')insert into cities values ('Dallas')insert into cities values ('Denver')insert into cities values ('Phoenix')insert into cities values ('Los Angeles')insert into cities values ('San Francisco')insert into routes values ('New York', 'Washington', 200)insert into routes values ('New York', 'Chicago', 700)insert into routes values ('Miami', 'Washington', 900)insert into routes values ('St. Louis', 'Washington', 700)insert into routes values ('St. Louis', 'Miami', 1050)insert into routes values ('St. Louis', 'Chicago', 250)insert into routes values ('St. Louis', 'Dallas', 550)insert into routes values ('St. Louis', 'Denver', 800)insert into routes values ('Chicago', 'Denver', 900)insert into routes values ('San Francisco', 'Denver', 950)insert into routes values ('San Francisco', 'Los Angeles', 350)insert into routes values ('Phoenix', 'Los Angeles', 350)insert into routes values ('Phoenix', 'Dallas', 900)insert into routes values ('Miami', 'Dallas', 1100)goexec getTSPRoute 'New York'---**************************************************************************************************************************--- Test attempt 5--- 11 cities--- Running time: 1 hr 30 mins 43 secondsdelete from routesdelete from citiesinsert into cities values ('New York')insert into cities values ('Washington')insert into cities values ('Miami')insert into cities values ('Chicago')insert into cities values ('St. Louis')insert into cities values ('Dallas')insert into cities values ('Denver')insert into cities values ('Phoenix')insert into cities values ('Los Angeles')insert into cities values ('San Francisco')insert into cities values ('Seattle')insert into routes values ('New York', 'Washington', 200)insert into routes values ('New York', 'Chicago', 700)insert into routes values ('Miami', 'Washington', 900)insert into routes values ('St. Louis', 'Washington', 700)insert into routes values ('St. Louis', 'Miami', 1050)insert into routes values ('St. Louis', 'Chicago', 250)insert into routes values ('St. Louis', 'Dallas', 550)insert into routes values ('St. Louis', 'Denver', 800)insert into routes values ('Chicago', 'Denver', 900)insert into routes values ('Seattle', 'Denver', 1000)insert into routes values ('San Francisco', 'Denver', 950)insert into routes values ('San Francisco', 'Seattle', 700)insert into routes values ('San Francisco', 'Los Angeles', 350)insert into routes values ('Phoenix', 'Los Angeles', 350)insert into routes values ('Phoenix', 'Dallas', 900)insert into routes values ('Miami', 'Dallas', 1100)goexec getTSPRoute 'New York'`Thanks for taking the time to look at it. Enjoy. :-]

tkizer
Almighty SQL Goddess

38200 Posts

 Posted - 2012-03-06 : 12:58:38 Your code looks like T-SQL and not PL/SQL. Are you sure this was for Oracle and not Microsoft SQL Server? It makes a difference here since SQLTeam.com is for MSSQL.Tara KizerMicrosoft MVP for Windows Server System - SQL Serverhttp://weblogs.sqlteam.com/tarad/Subscribe to my blog

mynameispaulie
Starting Member

2 Posts

 Posted - 2012-03-06 : 13:13:47 quote:Originally posted by tkizerYour code looks like T-SQL and not PL/SQL. Are you sure this was for Oracle and not Microsoft SQL Server? It makes a difference here since SQLTeam.com is for MSSQL.Tara KizerMicrosoft MVP for Windows Server System - SQL Serverhttp://weblogs.sqlteam.com/tarad/Subscribe to my blogMy apologies. It appears I have the incorrect terminology. My code was written for and ran in SQL server. So I guess it is T-SQL and not PL/SQL. I have updated the post. I learned something already! :-]

AnthonyNedu
Starting Member

2 Posts

 Posted - 2014-10-23 : 05:35:35 Mynameispaulie, please can i contact you for details with the travel salesman problem I am faced with such question now.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

 Posted - 2014-10-26 : 06:51:18 The Travelling Salesman problem is an np-complete problem and has to be solve with "brute force".Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA

SwePeso
Patron Saint of Lost Yaks

30421 Posts

 Posted - 2014-10-26 : 07:17:02 11 cities in 150 ms`SET NOCOUNT ON;-- Prepare sample dataCREATE TABLE #Nodes ( Name VARCHAR(30) PRIMARY KEY CLUSTERED );INSERT #Nodes ( Name )VALUES ('New York'), ('Washington'), ('Miami'), ('Chicago'), ('St. Louis'), ('Dallas'), ('Denver'), ('Phoenix'), ('Los Angeles'), ('San Francisco'), ('Seattle');CREATE TABLE #Routes ( FromNode VARCHAR(30) NOT NULL REFERENCES #Nodes(Name), ToNode VARCHAR(30) NOT NULL REFERENCES #Nodes(Name), Distance DECIMAL(28, 12) NOT NULL, PRIMARY KEY CLUSTERED ( FromNode, ToNode ) );INSERT #Routes ( FromNode, ToNode, Distance )OUTPUT inserted.ToNode AS FromNode, inserted.FromNode AS ToNode, inserted.DistanceINTO #Routes ( FromNode, ToNode, Distance )VALUES ('New York', 'Washington', 200), ('New York', 'Chicago', 700), ('Miami', 'Washington', 900), ('St. Louis', 'Washington', 700), ('St. Louis', 'Miami', 1050), ('St. Louis', 'Chicago', 250), ('St. Louis', 'Dallas', 550), ('St. Louis', 'Denver', 800), ('Chicago', 'Denver', 900), ('Seattle', 'Denver', 1000), ('San Francisco', 'Denver', 950), ('San Francisco', 'Seattle', 700), ('San Francisco', 'Los Angeles', 350), ('Phoenix', 'Los Angeles', 350), ('Phoenix', 'Dallas', 900), ('Miami', 'Dallas', 1100);-- SolutionDECLARE @Nodes INT = (SELECT COUNT(*) FROM #Nodes);WITH cteMap(Nodes, LastNode, Distance, NodeMap)AS ( SELECT 2 AS Nodes, ToNode, Distance, CAST('\' + FromNode + '\' + ToNode + '\' AS VARCHAR(MAX)) AS NodeMap FROM #Routes UNION ALL SELECT m.Nodes + 1 AS Nodes, r.ToNode AS LastNode, CAST(m.Distance + r.Distance AS DECIMAL(28, 12)) AS Distance, CAST(m.NodeMap + r.ToNode + '\' AS VARCHAR(MAX)) AS NodeMap FROM cteMap AS m INNER JOIN #Routes AS r ON r.FromNode = m.LastNode WHERE m.NodeMap NOT LIKE '\%' + r.ToNode + '%\')SELECT TOP(1)WITH TIES Distance, NodeMapFROM cteMapWHERE Nodes = @NodesORDER BY Distance DESCOPTION (MAXRECURSION 0);-- Clean upDROP TABLE #Routes, #Nodes;`Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA

AnthonyNedu
Starting Member

2 Posts

 Posted - 2014-10-26 : 19:08:35 Swepeso, please can you give me your email so that I can contact you concerning a travel salesman problem, or you can contact me on tzamanda@yahoo.comThanks

tkizer
Almighty SQL Goddess

38200 Posts

 Posted - 2014-10-27 : 11:47:05 quote:Originally posted by AnthonyNeduSwepeso, please can you give me your email so that I can contact you concerning a travel salesman problem, or you can contact me on tzamanda@yahoo.comThanksJust start a new thread in one of our forums.Tara KizerSQL Server MVP since 2007http://weblogs.sqlteam.com/tarad/