5 ms·
Dijkstra's in Disguise
- ColinWright 8y agoCovering: 1 : Bellman-Ford 2 : Currency Arbitrage 3 : Directional Shortest-Path 4 : Q-Learning 5 : Handling Randomness in Shortest-Path Algorithms 6 : Modern Q-Learning 7 : Physically-Based Rendering 8 : Summary and Questions 9 : Acknowledgements
- pinewurst 8y agoThat’s a really neat article!
- tptacek 8y agoThis is one of the tightest, best things I've read on HN in a long time.
- ericjang 8y agoGlad you like it! Happy to answer any questions. I’ve been trying to make my writing accessible to both the HN and academic research community; let me know if you have feedback on how I can improve here
- vsto 8y agoThank you very much, great article indeed! The PDF download link to the article at the top of the page requires access approval though, is that the way it is supposed to be?
- ericjang 8y agoMy bad, I updated it to fix some typos and forgot to open up sharing settings. Should be fixed.
- pvg 8y agoHmm, even in PDF form it's not possible to read this without humming the Transformers theme and putting in 'Dijkstra's in Disguise' at the relevant places. This is very distracting.
- adito 8y agohttps://i.imgur.com/mlpUy4g.png https://i.imgur.com/mlpUy4g.png The usage of text color on this image caption is brilliant. It never occurred to me that you can do this technique to explain a diagram. Definitely love it. Will steal this technique for my own purpose.
- gugagore 8y agoYou might enjoy articles from BetterExplained. For example: https://betterexplained.com/articles/q-why-is-e-special-2-718-not-other-number/ https://betterexplained.com/articles/q-why-is-e-special-2-71... There might be an article about this specific technique.
- kalid 8y agoThanks for the pointer -- I have an article here. https://betterexplained.com/articles/colorized-math-equations/ https://betterexplained.com/articles/colorized-math-equation... If you hover any diagram, there are options for a colorblind-friendly version.
- jclulow 8y agoIf it's for broad consumption, it's best to consider people with poor colour vision.
- JBiserkov 8y agoProgressive enhancement?
- deleted 8y ago[deleted]
- sadamznintern 8y agoWonderful article! I absolutely adore graphs just for this reason - you can solve a massive number of problems with a few tools. And of-fucking-course OP is at Google Brain.
- j9461701 8y agoGraph theory and abstract algebra were the two elective math classes I took that almost tempted me to switch from physics to math. But then I took real analysis and was like "Yup, nope, this is not for me"
- Buge 8y agoThere seems to be a mistake about whether the currency arbitrage cost is -log(B/A) or log(B/A)
- ericjang 8y agoThanks! There was an error in the embedded graphic, which I've updated. Edge costs E(A,B) should be log (A/B)
- jtms 8y agoThe information density in this post is insane! This is easily the best things I have read on hacker news this year.
- yosyp 8y agoCouldn't agree more, it had me going back to the Algorithms book to refresh on most of part VI (Graph Algorithms). For those interested, Bellman-Ford is 24.1, and Dijkstra's algo is 24.3 in CLRS. Reviewing those helped step through the VisuAlgo link in the article: https://visualgo.net/en/sssp https://visualgo.net/en/sssp
- modarts 8y agoThis was such a pleasure to read, holy cow. I absolutely love the interconnection between different fields bound together by graph theory.
- signa11 8y agoon similar lines, we also have multiplicative-weight-update [https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf], which has been characterized as : "a basic tool [that should be] taught to all algorithms students together with divide-and-conquer, dynamic programming, and random sampling.” - sanjeev-arora “so hard to believe that it has been discovered five times and forgotten.” - christos-papadimitrou [https://www.youtube.com/watch?v=KP0WFbdHhJM https://www.youtube.com/watch?v=KP0WFbdHhJM] it has formed basis of algorithms in fields as diverse as machine-learning, optimization from e.g. tcp ^^), game-theory, economics, biology etc. etc.
- abkumar 8y agoReading this spiked my interest in graphs especially considering I never learned anything more than the basics taught in algorithms and data structures courses in college. Any resources (i.e. textbooks) recommended for learning more about graph theory as well as currency arbitrage?
- vowelless 8y agoWhat a beautiful write-up. Some colleagues and I used to joke that everything was Dijkstra. It's pretty awesome to see that elucidated so well.
- pcwalton 8y ago> Path tracing integrals are fairly expensive because states and actions are continuous and each bounce requires ray-intersecting a geometric data structure. What if we do light transport simulations on a point cloud with a precomputed visibility matrix between all points, and use that as an approximation for irradiance caching / final-gather? A crude variation on this is often used in games, known as "light probes". You precompute the light transport simulation on a subset of points in the scene (manually placed by artists), and lighting for dynamic objects simply lerps between the nearest light probes.
- LolWolf 8y agoThis is a fantastic post! Thank you so much for sharing it. Perhaps another post (which maybe you should write! Or I may (though I'm certainly nowhere as good), or why not both!) might the unifying principle of finding solutions to fixed-point equations. In general, having a Bellman-style update equation, you can usually construct either (a) DP solutions to this problem or (b) contraction mappings whose fixed point solves this problem. Perhaps the most general form I know of the above principles is the Hamilton-Jacobi-Bellman equation [0], which is used absolutely everywhere in control theory and has deep connections to several fields (including the theory of PDEs, such as heat equations on manifolds along with several other cases). Many, many problems (including all of the ones mentioned above) reduce immediately to an appropriate instance of the HJB equation (either in the finite or the infinite case), which admits a simple DP solution that can be very quickly computed. Anyways, again, awesome post. I'll be following your blog quite closely :) --- [0] https://en.wikipedia.org/wiki/Hamilton–Jacobi–Bellman_equation https://en.wikipedia.org/wiki/Hamilton–Jacobi–Bellman_equati...