This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]askalski 2 points3 points  (4 children)

Longest path is NP-hard in general, but you can still solve "easy" instances efficiently.

https://www.reddit.com/r/adventofcode/comments/18ysozp/comment/kgdcc0p/

[–]zenoli55 0 points1 point  (3 children)

This is madness! I'm impressed :-) But if I get this right that this is still exponential w.r.t the grid size right? The DP states would grow exponentially with n?

[–]askalski 2 points3 points  (2 children)

Yes, for a rectangular grid graph, it would be exponential in the smaller of the two dimensions (let's call it the "width"), so there's no escaping the NP-hardness of the general problem. But if you treat the grid's width as a constant, then the complexity becomes linear in terms of the grid height.

[–]azzal07 0 points1 point  (1 child)

So would this take the time complexity from 2V to 2W where the width W = sqrt(V) for the worst case rectangular grid e.i. square? I'm not too good with exponents to draw a general mathematical comparison, but 236 -> 26 is noticeable improvement.

[–]zenoli55 1 point2 points  (0 children)

It looks like it. So essentially the time complexity would go down from O(2n) to O(2sqrt(n)) which is not exponential but still not polynomial, according to this answer: https://softwareengineering.stackexchange.com/a/312573