New ask Hacker News story: Ask HN: As an outsider, how could I publish a white paper?
Ask HN: As an outsider, how could I publish a white paper?
3 by eezurr | 0 comments on Hacker News.
Hello HN TL;DR: I probably created the fastest "find all K simple paths" algorithm for a weighted or unweighted, directed or undirected graph. How would I, as an outsider, publish the results? If I'm right, I'd like to benefit from this discovery to open doors to more interesting work/careers. (I fear, in my 30s, I am at a huge disadvantage for not having any big co. or university to list on my resume) Background: I am outside of the tech "scene" and have no tech/academia connections (self taught, no time spent in university). That being said, I've been programming and managing operations (working as the sole dev at small co.) for 10+ years. I recently quit my job to reevaluate my career path and for fun, started working on a city builder video game. The first big problem I had to solve was "how can I efficiently simulate people/cars utilizing ALL the fastest paths available to them?" (in case you aren't aware, Dijkstra's algorithm only returns one shortest path from start to destination). Solution: I created an algorithm that has a time complexity of around O((V+E)log V) and a space complexity of O(n) (for a single node to all other nodes, for all possible shortest paths from each possible destination node to the source node). Now: I tested the algorithm in my game world and watched my digital citizens utilize all the shortest paths available to them for various destinations around the map. For a heavy load test, I created a 100 x 100 grid (where each square is a node), and my code takes 1.75 times longer than Dijkstra's. Since I can store the search tree I created, I can move tens of thousands of units around the map without any lag (using SFML vertex arrays for efficiently handling the screen draws). I started researching other existing solutions and to my surprise, my solution is faster. Eppstein (1997) is the fastest solution I came across @ O(E + V log V + kV), where k can grow at some binomial coefficient (thus would be terribly inefficient with hundreds of nodes, let alone thousands, if many fastest paths existed, which is the reality of most cities if you walk). Other notes (excuse my lack of traditional education here): This does not prove P = NP (phew! I'm safe.). While the number of shortest paths can grow at some binomial coefficient, the classification of all possible paths does not. To explain by example: Going from node (A) to node (G) could possibly use nodes (B, C, D, E, F) along the way. So A-->G is a classification. When we add a new node (H) to (G), that (A) can only get to via (G), the A-->G classification is not changed. On the other hand, if every node connected to every other node, the amount of classifications would increase at an exponential rate (and devolve into all NP-Complete problems), and the possible amount of k paths (not necessarily shortest) would grow super-binomial coefficient-ly.
3 by eezurr | 0 comments on Hacker News.
Hello HN TL;DR: I probably created the fastest "find all K simple paths" algorithm for a weighted or unweighted, directed or undirected graph. How would I, as an outsider, publish the results? If I'm right, I'd like to benefit from this discovery to open doors to more interesting work/careers. (I fear, in my 30s, I am at a huge disadvantage for not having any big co. or university to list on my resume) Background: I am outside of the tech "scene" and have no tech/academia connections (self taught, no time spent in university). That being said, I've been programming and managing operations (working as the sole dev at small co.) for 10+ years. I recently quit my job to reevaluate my career path and for fun, started working on a city builder video game. The first big problem I had to solve was "how can I efficiently simulate people/cars utilizing ALL the fastest paths available to them?" (in case you aren't aware, Dijkstra's algorithm only returns one shortest path from start to destination). Solution: I created an algorithm that has a time complexity of around O((V+E)log V) and a space complexity of O(n) (for a single node to all other nodes, for all possible shortest paths from each possible destination node to the source node). Now: I tested the algorithm in my game world and watched my digital citizens utilize all the shortest paths available to them for various destinations around the map. For a heavy load test, I created a 100 x 100 grid (where each square is a node), and my code takes 1.75 times longer than Dijkstra's. Since I can store the search tree I created, I can move tens of thousands of units around the map without any lag (using SFML vertex arrays for efficiently handling the screen draws). I started researching other existing solutions and to my surprise, my solution is faster. Eppstein (1997) is the fastest solution I came across @ O(E + V log V + kV), where k can grow at some binomial coefficient (thus would be terribly inefficient with hundreds of nodes, let alone thousands, if many fastest paths existed, which is the reality of most cities if you walk). Other notes (excuse my lack of traditional education here): This does not prove P = NP (phew! I'm safe.). While the number of shortest paths can grow at some binomial coefficient, the classification of all possible paths does not. To explain by example: Going from node (A) to node (G) could possibly use nodes (B, C, D, E, F) along the way. So A-->G is a classification. When we add a new node (H) to (G), that (A) can only get to via (G), the A-->G classification is not changed. On the other hand, if every node connected to every other node, the amount of classifications would increase at an exponential rate (and devolve into all NP-Complete problems), and the possible amount of k paths (not necessarily shortest) would grow super-binomial coefficient-ly.
Comments
Post a Comment