Jump to content
Please Use CODE Tags

Is there anything faster than Held Karp for this

LukaP
By LukaP
in Programming
 Share
Posted

I have a graph of 91 points (cities) that i need to find the shortest path through all of them. I cant use any heuristic methods unless they can guarantee an exact result.

 

So far the Held-Karp Algorithm seems to be the most efficient with O(n2 * 2n) but that is still terribly slow. So is there anything faster? Mind you I have to do this in python, so its slow by default :P

 

Thanks :)

"Unofficially Official" Leading Scientific Research and Development Officer of the Official Star Citizen LTT Conglomerate | Reaper Squad, Idris Captain | 1x Aurora LN


Game developer, AI researcher, Developing the UOLTT mobile apps


G SIX [My Mac Pro G5 CaseMod Thread]

Link to comment
Share on other sites
Link to post
Share on other sites
Posted

what if you drew a line from point a to b and your reasoning be: i built a flying car

 eGPU Setup: Macbook Pro 13" 16GB DDR3 RAM, 512GB SSD, i5 3210M, GTX 980 eGPU

New PC: i7-4790k, Corsair H100iGTX, ASrock Fatal1ty Z97 Killer, 24GB Ram, 850 EVO 256GB SSD, 1TB HDD, GTX 1080 Fractal Design R4, EVGA Supernova G2 650W

 

 

Link to comment
Share on other sites
Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share
Go to topic listing Programming

×