Extension of an Older SQL Puzzle

[AlexCuse]

I was looking at posts in SQL Server programming forum with the most stars, and I stumbled upon this one.

thread183-1197121 (I know, it's old, but I'm new...)

I was able to solve it, and I am now trying to get my head around how to figure out the shortest route that would have one visit all 50 capitals.

I first tried to get the closest other capital to each capital, and was able to do that with a very ugly query, but this latest question I have has got me very puzzled.

If anyone would care to join me in this undertaking, I'm all ears. Of course I am open to any tips you MVP's out there would be willing to offer!

Hope this gets at least a little interest,

Alex

PS - here is the code I used to get the closest capitals, if anyone is interested. I had to eliminate the rounding because a few had matching rounded values.

[COLOR=white]
select x.FromCapital, c.ToCapital, x.MDIST 

From

(SELECT 
c.FromCapital, min(c.Distance) as MDIST
from

(SELECT 
a.Capital +', ' + a.State AS FromCapital,
b.Capital +', ' + b.State AS ToCapital,
convert(int,dbo.fnCalculateDistance(a.longitude, a.latitude, b.longitude, b.latitude)
*5) as DISTANCE
from StateCapitals a, StateCapitals b
where a.Capital <> b.Capital) c GROUP BY c.FromCapital)
x

INNER JOIN

(SELECT 
a.Capital +', ' + a.State AS FromCapital,
b.Capital +', ' + b.State AS ToCapital,
convert(int,dbo.fnCalculateDistance(a.longitude, a.latitude, b.longitude, b.latitude)
*5) as DISTANCE
from StateCapitals a, StateCapitals b
where a.Capital <> b.Capital) c

ON 
x.FromCapital = c.FromCapital and x.MDIST = c.Distance

group by x.FromCapital, c.ToCapital, x.MDist

order by ltrim(right(x.FromCapital, charindex(',',reverse(x.FromCapital))-1)), x.MDIST
[/color]

It's a magical time of year in Philadelphia. Eagles training camp marks the end of another brutal season of complaining about the Phillies.

 

[Skie]

I'm not an SQL coder, but I'd probably have to code a long way to determine the answer.

Basically, determine what capital 1 to capital 2 to capital 3... would be. I'd calculate that path first and then loop through all the other routes and replace the total distance if I found a better one. If a calculation went over the current "best" I'd exit the for loop and move to the next possibility.

 

[Olaf Doschke]

I'm a programmer of data centric applications and sql is of course one main aspect. I mostly use foxpro, some grandchild of dbase. And there you can loom at data the sql way as a dataset, or you can pick sinlge records by having a table as some kind of object, sorted by an index, seeking the first record matching some condition. That way it's quite ideal for this kind of problems.

the traveling salesman problem. Normally it's done as a roundtrip problem. I wonder if the shortest route would end near the start city or have rather remote start and end cities.

Before I'd do any coding, I'd do it manually and observe what kind of assumptions and natural optimizations I do as a human. Just having some random array of points spread on a sheet, I'd surely start connecting the nearest points together. But will the shortest route only connect the nearest cities to each other, or is there a shorter path, if you take second shortest connections of two cites, because that enables another connection with a third and fourth city, which saves miles? the more points, the more complicated it gets.

Wit two cities the problem is easy. With three one can skip the longest distance between those three, the longest side of the triangle. Still seems the whole route would only be built by the shortest distances. And the idea of partitioning the whole area into triangles comes to my mind. Then simply remove all the longest sides of each triangle...

hmm.

It's quite hard to solve such a problem using SQL only.

I'd think of subproblems, partitioning to subareas, putting together partial ideal routes.

Perhaps it would be a great idea to start with a roundtrip with all the outmost cities, the margin cities of the whole area, then add city after city, the most central city at last.

Perhaps one should start with a rout through the center all in all connecting the most remote cities, and then add from there.

hmm.

doing it with a single SQL you'd have to join the tables of cities 50 times, having a virtual very huge cartesian product of all record combinations. The art of computing the shortest most certainly is to not really compute each possible route, but sort out too long routes as fast as possible.

Bye, Olaf.

 

[AlexCuse]

Interesting points all. I thought more about this over the weekend, and I think it might be best approached with a language that is more conducive to looping.

Not sure yet how would be best to approach it, but I don't think a single SQL statmement will be an option. It is just too many joins, and I will be working on this on a Toshiba laptop that is a couple years old and has cooling issues.

Not worth killing my computer over, I just thought this would be an excellent learning exercise. I will start with five or so and take it from there.

Thanks for the input,

Alex


It's a magical time of year in Philadelphia. Eagles training camp marks the end of another brutal season of complaining about the Phillies.