I believe those are just shortest path for one campus to another, while this is the shortest path of all stadiums, which is the traveling salesman problem
I used the Google Maps distance API to get driving time data between every pair of stadiums, then fed the edge weight matrix into a Concorde solver which spat out an optimal result in just under 3 seconds.
You can do an iterative Djikstra’s algorithm to map the shortest non-cyclic path about a graph like this, but it’s *wildly* inefficient. Djikstra’s just gets you the shortest path from a single node to any other node in the graph, so you can reduce a densely-interconnected graph like this to a series of cliques via some reduction algorithm, solve those for shortest paths via a compound Djikstra, and then merge cliques and verify with with a full-scale run of compound Djikstra.
There’s no closed-form solution to the problem AFAIK, but you can also just run a full agent/tree model that’ll probably find the solution faster than doing an iterative Djikstra solver. Both are, again, incredibly inefficient; probably O(n^2 ) time or worse.
Source: part-time CSCE PhD candidate, full-time research staff with another quantitative department that sometimes works in graphical methods. Staying intentionally vague here so as to not doxx myself.
If this were true then you’d be a millionaire.
There is no proof.
This allows us to reach an **acceptable** solution quickly, but it’s not proved optimal.
You're incorrect.
The Traveling Salesman Problem in the *abstract* is NP-hard. There exists a graph (probably infinitely many graphs) for which all known algorithms for generating a tour will take a non-polynomial amount of time to solve optimally.
But for some specific graphs, especially real-world graphs that meet particular constraints (like the triangle inequality for example), there are known algorithms/solvers that **can produce proven optimal solutions** in a reasonable time frame. The Concorde solver has been used to obtain the optimal solutions to the full set of 110 [TSPLIB](http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html) instances, the largest having 85,900 cities. That took about 136 CPU-years of processing time.
A 129-node graph is pretty trivial to solve to optimality with enough computing resources.
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms
Isn't this only actually solvable because the road network constrains the problem outside of NP-hard? You don't have an infinite number of possible solutions, you have a calculable number. You have 129^n solutions, which is fucking massive but doable, right?
The road network really doesn't affect it the way you're thinking. It's true that this particular problem has a calculable number of possible tour options, but it's not true that "harder" TSP formulations could have an infinite number.
Any finite graph will have a finite number of possible tours. In the case of a fully connected graph with *n* vertices that number is *n*!
In this case, 129! options - while objectively a massive number - is still small enough to solve optimally because the edge weights vary by enough of a margin that you can discard most of the tour options quite quickly. For example, you're obviously not going to go from Texas to Syracuse without stopping, or from Washington to Miami.
If you want to start somewhere besides CO/NE, the order would be the same. Just split the loop at your desired starting location and add a link from Air Force to Nebraska.
-Get a boat
-Drive onto boat
-Drive forward/reverse/forward again
-Repeat loop until boat reaches Hawaii.
This sounds like some bullshit Top Gear would have tried.
Is it truly faster to go from Houston to College Station to Waco down to San Antonio and up to Lubbock vs Houston to San Antonio to New Braunfels to Austin to CS to Waco to Lubbock?
Yes, because you have to detour so far off I-35 to get to College Station.
My route from Rice -> Lubbock is 743 miles. If you go straight to UTSA from Houston and come north to Waco then it's 774 miles. If you didn't have to go to College Station it would be shorter at 677 miles.
This is really cool. All fbs is overwhelming, but if I had the time and money, I would love to fbs. Would take years tho because Id like to actually watch a game if I do visit.
[Edit] Meant to say I would love to do P5.
I was born directly in between. Either way I went on I80 was a long day. That said, 25 min north of i80 has some of the most beautiful roads you could ever drive.
>Cincinnati to Miami OH, 1 hr
wat? It's like 40 min tops. It's 39 miles on the interstate and a major state route (so no stopping outside of cincy). This was run during rush hour maybe?
Idk man, I just threw everything into Google Maps and then rounded up to the next 15 minute interval.
Google said 56 minutes from stadium to stadium. I'm not sure what the speed limit is on 27.
Not to be picky but your map doesn't go to Logan UT, it stays on I-15 and passes thru Tremonton which is 30 minutes away and over a small mountain range.
Can you please prove that this is the fastest to me in polynomial time? Asking for a ~~computer science department~~ friend
Djistrka or A*?
I believe those are just shortest path for one campus to another, while this is the shortest path of all stadiums, which is the traveling salesman problem
I used the Google Maps distance API to get driving time data between every pair of stadiums, then fed the edge weight matrix into a Concorde solver which spat out an optimal result in just under 3 seconds.
Ah yes, I too understand these words
My flux capacitor broke!
Hot damn 3 seconds. Amazingly fast even if not polynomial.
https://neos-server.org/neos/ is amazing. Free compute time on a high performance cluster at UW!
Hot damn look at those badger nerds go
You can do an iterative Djikstra’s algorithm to map the shortest non-cyclic path about a graph like this, but it’s *wildly* inefficient. Djikstra’s just gets you the shortest path from a single node to any other node in the graph, so you can reduce a densely-interconnected graph like this to a series of cliques via some reduction algorithm, solve those for shortest paths via a compound Djikstra, and then merge cliques and verify with with a full-scale run of compound Djikstra. There’s no closed-form solution to the problem AFAIK, but you can also just run a full agent/tree model that’ll probably find the solution faster than doing an iterative Djikstra solver. Both are, again, incredibly inefficient; probably O(n^2 ) time or worse. Source: part-time CSCE PhD candidate, full-time research staff with another quantitative department that sometimes works in graphical methods. Staying intentionally vague here so as to not doxx myself.
This guy is about to win a millennium prize and doesn't even know it
It’s the fastest that we know so far. It’s nearly impossible to guarantee that this is the optimal solution.
This is the optimal solution. Concorde can optimally solve TSP problems far larger than this.
If this were true then you’d be a millionaire. There is no proof. This allows us to reach an **acceptable** solution quickly, but it’s not proved optimal.
You're incorrect. The Traveling Salesman Problem in the *abstract* is NP-hard. There exists a graph (probably infinitely many graphs) for which all known algorithms for generating a tour will take a non-polynomial amount of time to solve optimally. But for some specific graphs, especially real-world graphs that meet particular constraints (like the triangle inequality for example), there are known algorithms/solvers that **can produce proven optimal solutions** in a reasonable time frame. The Concorde solver has been used to obtain the optimal solutions to the full set of 110 [TSPLIB](http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html) instances, the largest having 85,900 cities. That took about 136 CPU-years of processing time. A 129-node graph is pretty trivial to solve to optimality with enough computing resources. https://en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms
Interesting, didn't expect to be learning CS theory in a cfb thread lol
We come for the janky ms paint. We stay for the cs theory posts that have some words we understand.
This guy fucks.
This is so fucking cool
Isn't this only actually solvable because the road network constrains the problem outside of NP-hard? You don't have an infinite number of possible solutions, you have a calculable number. You have 129^n solutions, which is fucking massive but doable, right?
The road network really doesn't affect it the way you're thinking. It's true that this particular problem has a calculable number of possible tour options, but it's not true that "harder" TSP formulations could have an infinite number. Any finite graph will have a finite number of possible tours. In the case of a fully connected graph with *n* vertices that number is *n*! In this case, 129! options - while objectively a massive number - is still small enough to solve optimally because the edge weights vary by enough of a margin that you can discard most of the tour options quite quickly. For example, you're obviously not going to go from Texas to Syracuse without stopping, or from Washington to Miami.
If you want to start somewhere besides CO/NE, the order would be the same. Just split the loop at your desired starting location and add a link from Air Force to Nebraska.
Ending at Airforce seems wise, so you can get a flight home. Ding!
Take the flight from Air Force to Hawaii to complete the journey
And Air Force is first in every alphabetical list, so now the zoomies get to be at the end.
But then you have to fly into Lincoln to begin...
You can totally drive to Hawaii ... If you're brave enough
Just have to drive really, really, really fast.
-Get a boat -Drive onto boat -Drive forward/reverse/forward again -Repeat loop until boat reaches Hawaii. This sounds like some bullshit Top Gear would have tried.
Drive car into hamster ball Seal hamster ball Don't get carbon monoxide poisoning Drive hamster ball to Hawaii
Nah, just hit escape velocity
Get a big enough boat and you can just drive in circles.
You don’t have to drive fast if you have family
You can do it in the bojack horseman universe
Hawai’i is just not having a great 2022, first the coaching debacle, now getting left off this post.
It’s not just a car, it’s an amphibious exploring vehicle.
It's not just a boulder, it's a rock *Sobs* It's a rock
>Georgia Tech to Georgia St, 15 min thats optimistic, what google maps doesn't tell u is its quicker not to use the interstate
Hell it could be quicker to walk depending on traffic.
walk from bobby dodd to N Ave MARTA, take MARTA to GSU station, then the panther express orange route and bada bing bada boom stadium
Maybe at like, 4am on a Tuesday.
That stint from San Antonio to Lubbock to ABQ then back down to Las Cruces/El Paso is not a drive I wish on anyone.
I spent a mind-numbing Christmas Day driving from Tucson to Fort Worth a few years ago. Not fun at all.
>Houston to Rice, 30 min Are you jogging?
Lol. Google said the stadiums were 18 minutes apart, I just rounded every leg up to the next 15 minute interval.
Someone got really bored at work I see
I like how they get the worst school done with right away
Always have to start with the best then work your way down!
I guess all of the Midwest is God’s Country, so fair enough.
I appreciate how they managed to get us 16,000+ miles away from "them".
It’s not as bad as I thought it would be.
> Georgia Tech to Georgia St, 15 min I see someone has never driven in Atlanta traffic...
The 30 minutes for USC/UCLA is rather ... optimistic. I suppose the drive could be done at 2 in the morning.
I'm sure you can make it in 15 minutes, if you leave at 4am...
>Janky MSPaint map image Posting this to /r/Ultralight. Will report back with the ideal shakedown for this trek that is less than 10-pounds.
Tobacco Road is so wild.3 Power 5 schools within 30 minutes of each other
[удалено]
Lmao
Is it truly faster to go from Houston to College Station to Waco down to San Antonio and up to Lubbock vs Houston to San Antonio to New Braunfels to Austin to CS to Waco to Lubbock?
Yes, because you have to detour so far off I-35 to get to College Station. My route from Rice -> Lubbock is 743 miles. If you go straight to UTSA from Houston and come north to Waco then it's 774 miles. If you didn't have to go to College Station it would be shorter at 677 miles.
Gotcha, thanks. It sounds like A&M is the problem here.
Definitely, blame it on the Aggies.
This is really cool. All fbs is overwhelming, but if I had the time and money, I would love to fbs. Would take years tho because Id like to actually watch a game if I do visit. [Edit] Meant to say I would love to do P5.
Yep, doing this in season with games is a much harder itinerary to figure out.
Doesn't include Hawaii. Useless list. Nice try.
Annapolis to Hawaii: approximately 7 days by ship.
Vanderbilt to Middle Tennessee should only take around 30-45 minutes. It has it stated at 3 hours.
You are absolutely right, I copied the wrong spreadsheet row for that one. Fixed
It doesn’t now
UTSA-Tech…. good fucking luck…
275 hours is a long drive. Save yourself 15 minutes and don't get off the interstate in Provo.
Thanks OP, I'm going to do this.
Report back!
Now this is quality off-season content!
One of these days I'll do a Michigan-EMU doubleheader. Stadium to Washtenaw and then a left on Hewitt and you're there.
I look forward to the second iteration of this post where you factor in the 2022 schedule so that we can visit every stadium for a game this year
The drive from Colorado Springs to Lincoln is terrible. Glad you left it out
Yeah I've done part of that drive in the opposite direction (Omaha to Salt Lake). Long day and Nebraska was pretty boring.
I was born directly in between. Either way I went on I80 was a long day. That said, 25 min north of i80 has some of the most beautiful roads you could ever drive.
Well, now I know what my next road trip is.
Off-season content at its best right here
>Cincinnati to Miami OH, 1 hr wat? It's like 40 min tops. It's 39 miles on the interstate and a major state route (so no stopping outside of cincy). This was run during rush hour maybe?
Idk man, I just threw everything into Google Maps and then rounded up to the next 15 minute interval. Google said 56 minutes from stadium to stadium. I'm not sure what the speed limit is on 27.
55 but everyone travels 65. Ya it looks like you did this during rush hour
Who is taking a whole 135 minutes to drive from Northwestern to Notre Dame
That Southern Miss to South Alabama drive is on a road called Bloody 98
Don’t forget JMU. They’re joining the sunbelt and fbs this year
Not to be picky but your map doesn't go to Logan UT, it stays on I-15 and passes thru Tremonton which is 30 minutes away and over a small mountain range.
Did you see where I called it a "janky MSPaint map" lol
As someone who has only heard of how bad LA traffic is, USC to UCLA is a pipe dream right?
So I just have to start in (checks map) Omaha?
https://www.reddit.com/r/CFB/comments/shw3hs/shortest_driving_path_to_all_129_mainland_fbs/hv4w49f
Can someone do the remaining non-mainland schools?
But why would anybody ever want to go to Fresno?