Shortest Path Algorithm Problem - Computerphile

A seemingly simple problem that's "in general" incredibly difficult! CEO of Redwood Research Buck Shlegeris explains his favourite algorithmic fact!

This video was filmed and edited by Sean Riley.

[Siderite]

Math guy: this apparently simple problem is actually very hard
Engineer: these two paths are the same length

[TheHDreality]

The pathfinding angle to this is such a huge red herring to what the topic is actually about that I can see why he laughed so hard at the end

[TheGreatAtario]

The truly hard problem is to find out how this guy ended up with an American accent except for "poth" and "groff"

[martinbean]

It’s amazing how Buck can make the words “farthest”, “path”, and “graph” all sound the same 😂

[TmOnlineMapper]

A classic case of something that's practically trivial but theoretically impossible. Or at least, that's what I thought, given our understanding of sums of square roots.

Edit: Turns out doing it mathematically is not impossible! While square roots are irrational, they are algebraic numbers — meaning each satisfies a finite minimal polynomial over the rationals. While the minimal polynomials themselves don’t directly tell you the ordering, they do allow for finite algebraic representations of sums. This means that you can, in principle, always determine which of two such sums is smaller in finite time.

Now, the computational effort grows very quickly (often exponentially with naive methods), but it can be done — so my earlier statement was incorrect. Mathematically it's not impossible, just computationally hard.

I think going into the mathematics behind that would've been very interesting. Oh well... maybe for a numberphile video.

[waarschijn]

For everyone saying "just take the numbers out of the roots and compare them": that doesn't work. Because even if a+b < c+d that doesn't mean √a+√b < √c+√d. For a counterexample, pick a and b far apart but c and d close to each other. E.g. a, b, c, d=49, 50, 1, 99.

[itachiuchiha]

if both path looks same, its faster to pick one than to calculate one

[PaulFromLongBeach]

So the lesson here is to only do practical things. If you are deciding the shortest path to walk, for example, the number of decimal places needed to decide is small. If you work in computational geometry for any length of time, you spend a lot of that time trying to avoid knife-edge decisions.

[backyardgarage]

This man is great to listen to. He sounds british with his "o" and some "a" vowels but american with all his "r"s.

[Rubrickety]

I was distracted by the much more difficult problem of placing Buck's accent. 90% American (maybe California?), non-rhotic Rs at word endings, extremely rhotic long-Os. Fascinating.

[DreadKyller]

The worst case scenario is that the two paths are exactly equal, because you'll never reach high enough precision. At a purely theory standpoint this is an interesting argument, but from a practical standpoint it is of no value, at some level of precision you just cut off, if the two paths are equal to that precision than just pick one at random. If this was a delivery problem no one is going to care if one route is a thousandth of a millimeter shorter in practice, and at some point you'd run into Planck's length as well. This problem is only hard within the realm of pure mathematics.

[jonathanchapple]

Kind of feel, as an engineer, if they are the same up to a point of precision, just default the the "1st path" however we are storing that... Even if its wrong in later precision, we don't care, they were the same with the defined precision, and thus should get similar results, regardless what you choose. Feel like real world solution is simply don't over think it. If it works, it works.

[superjugy]

if you chose a precision to begin with, it is because that precision is enough for you to not care what comes after. if both paths give the same result up until that precision, for all intents and purposes, the paths are the same and either will work.

[melwinalm]

Wow. My brain is not braining after watching this. Shortest path is supposed to be a simple problem, but when you think of it in terms of Cartesian system, this gets really complicated.

[chadbeck]

Do we just want to know which path is shortest? Since you’re doing a square root on all lengths, couldn’t you just…ignore the radical and base the decision off the relative sum of squares? Or do we actually care what shortest path length value is?

[zzfkbcu]

A video with Buck and Rob about AI alignment vs AI control would probably be pretty interesting.

[williamlouie]

This is how you turn a simple problem into a complex one!

[johanlindeberg]

You have to ask yourself which road is the one less traveled by. That will make all the difference.

[HeavyMetalMouse]

Random thought. For paths on the cartesian plane between two points, could we do something with comparing the areas enclosed by the a given path and the 'as the crow flies' path' for each path, with some clever accounting for concavities and self-intersections, to determine how 'close' the path lengths are? Since you can determine polygonal areas, given coordinates on the plane, with only multiplication and addition (Shoelace Formula), if those areas, plus the additional time it would take to determine where and how inclusions and self-intersections could affect the way the path length and area relate, we should at the very least be able to determine an upper bound for how long it would take to calculate that area comparison (since it doesn't involve floating point precision), and then from there determine some kind of upper bound on the amount of precision we need for the actual path length problem.

I don't expect such a system would be 'easy' - but the complexity of determining whether and how and where a path is concave/self-intersecting should be describable. If we can then say 'these modified areas are within this error amount of each other, therefore the path lengths should be a minimum this different from one another', that would give us an upper bound for precision to actually calculate those path lengths.

As a bonus, if both paths happen to be convex with the direct line, then the one with the least area will also be the path with the shortest length, so the algorithm can terminate early in that case. there are likely several other early termination conditions that could be incidentally found during the (admittedly likely difficult) process of accounting for concavities and self-intersections.

[redshift]

Define the paths as a series of polar vectors instead of cartesian vectors. You no longer have to calculate the vector magnitudes because they are defined (in a similar way, the original problem doesn't require the measurement of the cartesian coordinates because they are defined). Add up all the vector magnitudes and compare.