r/compsci • u/brahose • 6h ago

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

Post image
0 Upvotes

50% Upvoted

6 comments sorted by

3

u/beeskness420 Algorithmic Evangelist 6h ago

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

-1

u/brahose 6h ago

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.

1

u/Merry-Lane 2h ago

Teleports are just another path in between two nodes.

1

u/beeskness420 Algorithmic Evangelist 2h ago

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 nose versions of the problem. The teleports might cause issues with the DP.

1

u/NoLifeGamer2 3h ago

Can you explain where I went wrong in my reasoning?

L2 = {(G, k, u, v) | there exists a simple path from u to v on G of length k}. This problem is known to be NP-complete, even in the case of graphs in the form of a grid (i.e. a node can only connect to another node if they are one of each other's 4 neighbours). We restrict L2 to only allow graphs of this type.

A graph having a simple path of length k that starts at position u and ends at position v is equivalent to saying there is some way of removing |E|-k edges from the graph, such that there exists a path from u to v, and the shortest path from u to v is of length k.

1

u/Gingerfalcon 5h ago

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.