r/compsci • u/brahose • Aug 20 '26

[Request] What is the complexity in solving a grid-based least optimal path puzzle?

Post image
5 Upvotes

73% Upvoted

8 comments sorted by

5

u/beeskness420 Algorithmic Evangelist Aug 20 '26

Shortest Paths Network Interdiction is NP-Hard in general, but for the square grid case there is a DP.

2

u/NoLifeGamer2 Aug 21 '26

But this assumes no holes in the square grid. There are holes in these grids.

0

u/brahose Aug 20 '26

Oh wow, I read the Abstract and will have to dig deeper into the paper when I get a chance. Thank you for sharing.

Does this take into consideration the added complexity of teleports? I imagine so because it is just another subset of the larger problem.

3

u/Merry-Lane Aug 20 '26

Teleports are just another path in between two nodes.

1

u/beeskness420 Algorithmic Evangelist Aug 20 '26 edited Aug 23 '26

Not sure if it's the best reference, but the first one I could find defining the problem. Didn't run down the details on the teleports or on the edge versus node versions of the problem. The teleports might cause issues with the DP.

1

u/Gingerfalcon Aug 20 '26

If you use say A* or IDA* with a Manhattan heuristic plus and node costs based on tile type it would very easy to solve even on much larger grids.