FT5 Travelling Salesman - SQL Server Forums

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

Site Related Forums

The Yak Corral

FT5 Travelling Salesman

Author

Topic

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-07 : 14:41:13

Here is another problem in the Funny Test Series

This one might be too trivial for some of ye ol' Yak's out there,
but it could be fun to do in SQL.( 1 select needed )

/*********************************
Travelling salesman
[url]http://mathworld.wolfram.com/TravelingSalesmanProblem.html[/url]
Start from one point, travel through all the other points,
visiting each point once, and return to starting point.
Find shortest and longest distance travelled
The sample data is provided below (just 10 points ):
**********************************/

-- Create the points, x, y coordinates
SET NOCOUNT ON
CREATE TABLE #points(
	p CHAR(1) PRIMARY KEY CLUSTERED,
	x FLOAT NOT NULL,
	y FLOAT NOT NULL,
	CONSTRAINT UIX_UNIQUE_x_y UNIQUE(x,y) )

INSERT #points( p, x, y )
SELECT 'A',0,0 UNION SELECT 'B',6,-5 UNION SELECT 'C',9,-1 UNION SELECT 'D',1,3 UNION SELECT 'E',-7,-9
UNION SELECT 'F',-7,9 UNION SELECT 'G',5,2 UNION SELECT 'H',3,-8 UNION SELECT 'I',-9,5 UNION SELECT 'J',7,-1

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-09-07 : 15:22:18

doesn't seem too easy to me ... you have a solution that uses just 1 SELECT ?

- Jeff

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-07 : 15:36:32

1 SELECT from #points table[s], yes.
Well, actually 1 to get the longest paths, and 1 to get the shortest paths.

Extra points if you eliminate all the "reverse" paths

starting from A: ABCDEFGHIJA is the same as AJIHGFEDCBA, but reverse.

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-09-07 : 16:25:18

you really have a solution for this? I'd love to see it ... can you give some hints, or the basic psuedo-code for the algorithm you've used? I believe there is no known solution for this other than brute force checking of all possibilities.

- Jeff

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-07 : 16:54:05

quote:
Originally posted by jsmith8858

you really have a solution for this? I'd love to see it ... can you give some hints, or the basic psuedo-code for the algorithm you've used? I believe there is no known solution for this other than brute force checking of all possibilities.

Thanx for the credit Jeff, but with (just 10 points) You only have to check 181440 possibilities.
People way smarter than me have spent way more time than me trying to figure out a smart algorithm

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-07 : 17:04:33

I know I cheated by generating a distance table, but it seems so inefficient to do it any other way...


SET NOCOUNT ON
CREATE TABLE #points(
	p CHAR(1) PRIMARY KEY CLUSTERED,
	x FLOAT NOT NULL,
	y FLOAT NOT NULL,
	CONSTRAINT UIX2_UNIQUE_x_y UNIQUE(x,y) )

INSERT #points( p, x, y )
SELECT 'A',0,0 UNION SELECT 'B',6,-5 UNION SELECT 'C',9,-1 UNION SELECT 'D',1,3 UNION SELECT 'E',-7,-9
UNION SELECT 'F',-7,9 UNION SELECT 'G',5,2 UNION SELECT 'H',3,-8 UNION SELECT 'I',-9,5 UNION SELECT 'J',7,-1

	Select 
		Id = IDENTITY(int, 1,1),
		P1 =  A.P,
		P2 =  B.P,
		Distance = Sqrt(Power(A.X-B.X,2)+Power(A.Y-B.Y,2))
	Into #distances
	From #points A, #points B
	Where A.P <> B.P
	Order By Distance Desc

Declare @startChr varchar(1)
Set @StartChr = 'A'
	
Select top 1 Pattern=Pattern + B.p2, ttlDistance = A.ttlDistance + B.Distance
From
(	
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = p1+p2, p=p2, ttlDistance=distance From #distances Where p1 = @StartChr
	) S2 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S3 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S4 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S5 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S6 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S7 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S8 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S9 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
) A
Inner Join #distances B
On A.p = B.p1
and B.p2=@StartChr
Order By ttlDistance Desc


Select top 1 Pattern=Pattern + B.p2, ttlDistance = A.ttlDistance + B.Distance
From
(	
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = pattern + p2, p=p2, ttlDistance=ttlDistance + distance From(
	Select pattern = p1+p2, p=p2, ttlDistance=distance From #distances Where p1 = @StartChr
	) S2 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S3 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S4 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S5 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S6 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S7 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S8 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
	) S9 Inner Join #distances On p = p1 and pattern not like  ('%' + p2  + '%')
) A
Inner Join #distances B
On A.p = B.p1
and B.p2=@StartChr
Order By ttlDistance

Drop Table #points
Drop Table #distances

Corey

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-07 : 17:15:47

Ok... here it is without cheating:


SET NOCOUNT ON
CREATE TABLE #points(
	p CHAR(1) PRIMARY KEY CLUSTERED,
	x FLOAT NOT NULL,
	y FLOAT NOT NULL,
	CONSTRAINT UIX1_UNIQUE_x_y UNIQUE(x,y) )

INSERT #points( p, x, y )
SELECT 'A',0,0 UNION SELECT 'B',6,-5 UNION SELECT 'C',9,-1 UNION SELECT 'D',1,3 UNION SELECT 'E',-7,-9
UNION SELECT 'F',-7,9 UNION SELECT 'G',5,2 UNION SELECT 'H',3,-8 UNION SELECT 'I',-9,5 UNION SELECT 'J',7,-1

Declare @startChr varchar(1)
Set @StartChr = 'A'
	
Select top 1 pattern = pattern + p, minDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2))
From
(	
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = p, pl=p, xl=x, yl=y, ttlDistance=0 From #points Where p = @StartChr
	) S1 Inner Join #points On pattern not like  ('%' + p + '%')
	) S2 Inner Join #points On pattern not like  ('%' + p + '%')
	) S3 Inner Join #points On pattern not like  ('%' + p + '%')
	) S4 Inner Join #points On pattern not like  ('%' + p + '%')
	) S5 Inner Join #points On pattern not like  ('%' + p + '%')
	) S6 Inner Join #points On pattern not like  ('%' + p + '%')
	) S7 Inner Join #points On pattern not like  ('%' + p + '%')
	) S8 Inner Join #points On pattern not like  ('%' + p + '%')
	) S9 Inner Join #points On pattern not like  ('%' + p + '%')
) A
Inner Join #points B
On @StartChr=B.p
Order By ttlDistance

Select top 1 pattern = pattern + p, maxDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2))
From
(	
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = pattern + p, pl=p, xl=x, yl=y, ttlDistance=ttlDistance + Sqrt(Power(x-xl,2)+Power(y-yl,2)) From(
	Select pattern = p, pl=p, xl=x, yl=y, ttlDistance=0 From #points Where p = @StartChr
	) S1 Inner Join #points On pattern not like  ('%' + p + '%')
	) S2 Inner Join #points On pattern not like  ('%' + p + '%')
	) S3 Inner Join #points On pattern not like  ('%' + p + '%')
	) S4 Inner Join #points On pattern not like  ('%' + p + '%')
	) S5 Inner Join #points On pattern not like  ('%' + p + '%')
	) S6 Inner Join #points On pattern not like  ('%' + p + '%')
	) S7 Inner Join #points On pattern not like  ('%' + p + '%')
	) S8 Inner Join #points On pattern not like  ('%' + p + '%')
	) S9 Inner Join #points On pattern not like  ('%' + p + '%')
) A
Inner Join #points B
On @StartChr=B.p
Order By ttlDistance Desc

Drop Table #points

Corey

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-07 : 17:48:35

Nice call Corey

, very good
I got different results with the 2 versions on my machine though.
( the cheating one was better )

BTW, I would hate to debug your code

Let's see if we get more callers...

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-09-07 : 19:36:28

Question: Are you asking for the shortest and longest starting with a specified point, or starting from any point?

Corey

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-09-08 : 02:17:59

quote:
Originally posted by Seventhnight

Question: Are you asking for the shortest and longest starting with a specified point, or starting from any point?

Corey

It does not matter because he's asking for a circuit-like path,

i.e., for an Hamiltonian cycle.

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-08 : 03:12:12

Seventhnight:
You can start at any point, the result should be the same, ( as your code shows ).
I was a bit confused when I got different results from your 2 queries,
but the problem was the Order By clause. Just make it "Order By 2" instead.

Your solution works very well as far as I can tell, CONGRATS!!!

By the way, the difference between #1 and #2 performancewise is not that big:
On my server 58 And 65 seconds respectively.

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-08 : 03:29:12

See if we get any solutions that eliminates all the "reverse" paths

.
Corey's solution evaluates all possibilities starting from any point,
going both back and forth.

EDIT: Corey, just to keep you thinking....
You only have to add 1 line of code...

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-09-08 : 04:47:29

[code]
select top 1
t0.p, t1.p, t2.p, t3.p, t4.p, t5.p, t6.p, t7.p, t8.p, t9.p,
sqrt((t0.x-t1.x)*(t0.x-t1.x) + (t0.y-t1.y)*(t0.y-t1.y)) +
sqrt((t1.x-t2.x)*(t1.x-t2.x) + (t1.y-t2.y)*(t1.y-t2.y)) +
sqrt((t2.x-t3.x)*(t2.x-t3.x) + (t2.y-t3.y)*(t2.y-t3.y)) +
sqrt((t3.x-t4.x)*(t3.x-t4.x) + (t3.y-t4.y)*(t3.y-t4.y)) +
sqrt((t4.x-t5.x)*(t4.x-t5.x) + (t4.y-t5.y)*(t4.y-t5.y)) +
sqrt((t5.x-t6.x)*(t5.x-t6.x) + (t5.y-t6.y)*(t5.y-t6.y)) +
sqrt((t6.x-t7.x)*(t6.x-t7.x) + (t6.y-t7.y)*(t6.y-t7.y)) +
sqrt((t7.x-t8.x)*(t7.x-t8.x) + (t7.y-t8.y)*(t7.y-t8.y)) +
sqrt((t8.x-t9.x)*(t8.x-t9.x) + (t8.y-t9.y)*(t8.y-t9.y)) +
sqrt((t9.x-t0.x)*(t9.x-t0.x) + (t9.y-t0.y)*(t9.y-t0.y)) as dist_sum
from
points t0, points t1, points t2, points t3, points t4,
points t5, points t6, points t7, points t8, points t9
where
t0.p='A' and
t1.p<>t0.p and
t2.p<>t1.p and t2.p<>t0.p and
t3.p<>t2.p and t3.p<>t1.p and t3.p<>t0.p and
t4.p<>t3.p and t4.p<>t2.p and t4.p<>t1.p and t4.p<>t0.p and
t5.p<>t4.p and t5.p<>t3.p and t5.p<>t2.p and t5.p<>t1.p and t5.p<>t0.p and
t6.p<>t5.p and t6.p<>t4.p and t6.p<>t3.p and t6.p<>t2.p and t6.p<>t1.p and
t6.p<>t0.p and
t7.p<>t6.p and t7.p<>t5.p and t7.p<>t4.p and t7.p<>t3.p and t7.p<>t2.p and
t7.p<>t1.p and t7.p<>t0.p and
t8.p<>t7.p and t8.p<>t6.p and t8.p<>t5.p and t8.p<>t4.p and t8.p<>t3.p and
t8.p<>t2.p and t8.p<>t1.p and t8.p<>t0.p and
t9.p<>t8.p and t9.p<>t7.p and t9.p<>t6.p and t9.p<>t5.p and t9.p<>t4.p and
t9.p<>t3.p and t9.p<>t2.p and t9.p<>t1.p and t9.p<>t0.p
order by 11 -- desc

p p p p p p p p p p dist_sum
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ------------------
A G J C B H E I F D 62.059781629737572

p p p p p p p p p p dist_sum
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ------------------
A C I B D H F J E G 141.38736285325578
[/code]

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-08 : 04:56:20

Very nice Stoad !!! looks somewhat familiar.
nice to see some of You are kept busy

Do you really have to evaluate all 362880 possibilities ?

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-09-08 : 05:54:26

I think "yes", all 3628800 (you missed one trailing zero) possibilities.

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-08 : 06:21:53

quote:
Originally posted by Stoad

I think "yes", all 3628800 (you missed one trailing zero) possibilities.

Well You fix one of the points when you start the calculation,
so that effectively leaves 362880 possibilities for that particular calculation.
"no"
Do You want a hint ?

rockmoose
/* Chaos is the nature of things...Order is a lesser state of chaos */

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-09-08 : 06:30:41

Yes! I want a hint :)

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2004-09-08 : 06:47:12

A possible path and it's reverse:
Path: ABCDEFGHIJA
Reverse: AJIHGFEDCBA
The bold ones are my "key" and this hint contains the keyword :)
There is a pattern...

Order in Chaos
/rockmoose

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-09-08 : 08:30:25

rockmoose,

it's about time to reveal your secret!

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2004-09-08 : 08:42:04

rockmoose: is your pattern maybe that u use only 4 bolds out of each, and then combine them?
meaning u calculate only half the path each time?

Go with the flow & have fun! Else fight the flow

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-09-08 : 08:52:09

yes, please. these solutions presented are good, but they require exactly 9 points. I would love to see a generic solution that works with as many points that are in the table.

- Jeff

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources