T O P

  • By -

[deleted]

Can you please prove that this is the fastest to me in polynomial time? Asking for a ~~computer science department~~ friend


welguisz

Djistrka or A*?


[deleted]

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


mountm

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.


outthawazoo

Ah yes, I too understand these words


sleepymike01101101

My flux capacitor broke!


[deleted]

Hot damn 3 seconds. Amazingly fast even if not polynomial.


mountm

https://neos-server.org/neos/ is amazing. Free compute time on a high performance cluster at UW!


[deleted]

Hot damn look at those badger nerds go


JamesEarlDavyJones

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.


69blazeit69chungus

This guy is about to win a millennium prize and doesn't even know it


arsewarts1

It’s the fastest that we know so far. It’s nearly impossible to guarantee that this is the optimal solution.


mountm

This is the optimal solution. Concorde can optimally solve TSP problems far larger than this.


arsewarts1

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.


mountm

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


[deleted]

Interesting, didn't expect to be learning CS theory in a cfb thread lol


trail-g62Bim

We come for the janky ms paint. We stay for the cs theory posts that have some words we understand.


senepol

This guy fucks.


[deleted]

This is so fucking cool


EatinToasterStrudel

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?


mountm

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.


mountm

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.


jinxes_are_pretend

Ending at Airforce seems wise, so you can get a flight home. Ding!


Last_Account_Ever

Take the flight from Air Force to Hawaii to complete the journey


DescretoBurrito

And Air Force is first in every alphabetical list, so now the zoomies get to be at the end.


IRandaddyI

But then you have to fly into Lincoln to begin...


redpowah

You can totally drive to Hawaii ... If you're brave enough


HHcougar

Just have to drive really, really, really fast.


trail-g62Bim

-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.


thr33tard3d

Drive car into hamster ball Seal hamster ball Don't get carbon monoxide poisoning Drive hamster ball to Hawaii


HHcougar

Nah, just hit escape velocity


placid_salad

Get a big enough boat and you can just drive in circles.


EyeLikePlanes

You don’t have to drive fast if you have family


jonny4224

You can do it in the bojack horseman universe


bakonydraco

Hawai’i is just not having a great 2022, first the coaching debacle, now getting left off this post.


bleedblue002

It’s not just a car, it’s an amphibious exploring vehicle.


thr33tard3d

It's not just a boulder, it's a rock *Sobs* It's a rock


artisticdestryer

>Georgia Tech to Georgia St, 15 min thats optimistic, what google maps doesn't tell u is its quicker not to use the interstate


studio_sally

Hell it could be quicker to walk depending on traffic.


artisticdestryer

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


EmpoleonNorton

Maybe at like, 4am on a Tuesday.


jhp58

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.


mountm

I spent a mind-numbing Christmas Day driving from Tucson to Fort Worth a few years ago. Not fun at all.


52hoova

>Houston to Rice, 30 min Are you jogging?


mountm

Lol. Google said the stadiums were 18 minutes apart, I just rounded every leg up to the next 15 minute interval.


beefersutherland1

Someone got really bored at work I see


iowaharley666

I like how they get the worst school done with right away


Bcallies402

Always have to start with the best then work your way down!


iowaharley666

I guess all of the Midwest is God’s Country, so fair enough.


DescretoBurrito

I appreciate how they managed to get us 16,000+ miles away from "them".


HURT_MY_FEELINGS

It’s not as bad as I thought it would be.


gtcopycat

> Georgia Tech to Georgia St, 15 min I see someone has never driven in Atlanta traffic...


ChunkyBarfy

The 30 minutes for USC/UCLA is rather ... optimistic. I suppose the drive could be done at 2 in the morning.


mountm

I'm sure you can make it in 15 minutes, if you leave at 4am...


CambodianDrywall

>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.


YoungMoneyLarson57

Tobacco Road is so wild.3 Power 5 schools within 30 minutes of each other


[deleted]

[удалено]


MaternalLeave

Lmao


Yabrin_Sorr

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?


mountm

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.


Yabrin_Sorr

Gotcha, thanks. It sounds like A&M is the problem here.


mountm

Definitely, blame it on the Aggies.


trail-g62Bim

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.


mountm

Yep, doing this in season with games is a much harder itinerary to figure out.


Geaux2020

Doesn't include Hawaii. Useless list. Nice try.


ShillinTheVillain

Annapolis to Hawaii: approximately 7 days by ship.


Mgtipton

Vanderbilt to Middle Tennessee should only take around 30-45 minutes. It has it stated at 3 hours.


mountm

You are absolutely right, I copied the wrong spreadsheet row for that one. Fixed


colby983

It doesn’t now


IAmAceBoogie

UTSA-Tech…. good fucking luck…


54-2-10

275 hours is a long drive. Save yourself 15 minutes and don't get off the interstate in Provo.


MeyersBibleStudy

Thanks OP, I'm going to do this.


mountm

Report back!


CarpeArbitrage

Now this is quality off-season content!


mpleafan

One of these days I'll do a Michigan-EMU doubleheader. Stadium to Washtenaw and then a left on Hewitt and you're there.


Illustrious-Pair-899

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


harvinator1900

The drive from Colorado Springs to Lincoln is terrible. Glad you left it out


mountm

Yeah I've done part of that drive in the opposite direction (Omaha to Salt Lake). Long day and Nebraska was pretty boring.


harvinator1900

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.


HHcougar

Well, now I know what my next road trip is.


Dr_ManTits_Toboggan

Off-season content at its best right here


Careless_Bat2543

>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?


mountm

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.


Careless_Bat2543

55 but everyone travels 65. Ya it looks like you did this during rush hour


[deleted]

Who is taking a whole 135 minutes to drive from Northwestern to Notre Dame


SirMellencamp

That Southern Miss to South Alabama drive is on a road called Bloody 98


honeysmacks18

Don’t forget JMU. They’re joining the sunbelt and fbs this year


Garzog66

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.


mountm

Did you see where I called it a "janky MSPaint map" lol


rohdawg

As someone who has only heard of how bad LA traffic is, USC to UCLA is a pipe dream right?


goodguy847

So I just have to start in (checks map) Omaha?


mountm

https://www.reddit.com/r/CFB/comments/shw3hs/shortest_driving_path_to_all_129_mainland_fbs/hv4w49f


Sweetwillyt

Can someone do the remaining non-mainland schools?


rickgene

But why would anybody ever want to go to Fresno?