3
$\begingroup$

On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus for each grid point which is NOT on the path but meanwhile has at least one neighbor on the path (bonus counting stops when reaching destination, see Fig. a). One restriction for path is: each grid point on path can have and only have 2 neighboring grid points on path (source and destination point can only have 1 neighbor on path accordingly, see Fig. b). I'm attempting to maximize the total bonus for a simple path connecting the source to destination.

My question is:

Can this problem be converted into some category of classic problem in graph theory (such as shortest path or maximum flow) or are there any other smarter DFS approach / Dynamic Programming to solve it?

(I'm not sure if polynomial time would be possible, but a better exponential time than current brute DFS would also be appropriate for this problem, because the N will be at most 400~500. )

Illustrations of: a) Bonus counting method; b) Invalid paths; c) Case of 5x3 grid.

What I have tried:

1. Brute DFS

Pseudo-codes are listed below which could inefficiently but thoroughly solve cases with N around 100 within several seconds on a common PC, the solution to a 5x3 grid are given in Fig. c. I curve-fitted the time complexity with 4x4 to 9x9 grids as about $O(1.24^N)$.

bool DFS (Vertex V) {
  if (V is destinationVertex) {
    Compare the current total bonus with the maximum total bonus;
    if (this path is better) {
      Record current paths and update total bonus;
    }
    return false; // Returning false means an end of this DFS branch. 
  }
  Verify which neighbors W of V could make a valid visit and put them into Queue.
  for (W in Queue) { DFS (W); } 
  if (all of above DFS (W) return false OR Queue is empty) {
    Clear this level's influences on decision tree. //Subtract current bonuses and paths
    return false;
  } else {
    return true;
  }
}
  1. I tried hard and found it might not be easy to be converted to a DAG or even a simple graph. If the grid points are selected as vertexs, the weight of edges are essentially undetermined, which is related to previous paths having been covered. And this is different from Shortest paths when edge weight depends on previous edge, where the edge weight is only related to LAST previous edge rather than possible ALL previous edge in my problem. So using <u, v> pair as vertexes might also not work. But maybe I'm wrong, so I really desire to find a better model for solving it.

I've spent several days trying to solve it and search similar problems and no progress are made. Any help would be appreciated! Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

I think I have found a working idea, however this is only a draft.

Take your n×m grid and split it into 3×3 squares starting from the upper-left corner until there are borders of size either 4 or 2 on two sides. If the border is of size 4 add 2 boxes 2×3, if it is of size 2 add only 1 2×3 box.

Some examples would be:

For 6×6 it is straight forward:

3×3 | 3x3

3x3 | 3x3

For 5×5 it would be:

3×3 | 3×2

2×3 | 2x2

For 10×9 it would be:

3x3 | 3x3 | 3x3

3x3 | 3×3 | 3x3

2×3 | 2x3 | 2x3

2x3 | 2x3 | 2x3

Connect 3x3 boxes through the middle of the edge. This way you only cover a bonus point twice at 90 degree turns. Only count points if they come from the same box as the path itself.

Now consider the new grid of boxes as a graph where the weights of the edges (between adjacent boxes) are the amount of bonus points added to both boxes by the best path connection. Do dijkstra or bellman ford to find the longest path from source to destination. This is the solution.

Might be a lot of case work, but if it works it would work.

$\endgroup$
7
  • $\begingroup$ First many thanks for your efforts and help. 1. I think 3x3 boxes as graph grid is kind of smart idea to model neighboring properties, yet we need consider: ① What if the source and destination are in the same box? Or more often, the optimal path in some cases (optimality verified by brute force DFS, but optimal path may not be unique) will travel into one box more than once. (See 8x8 case below, where S means Source, D for Des, 1 is grids on path, 0 is supplying bonus, X is not on path nor supplying bonus. Since comments do not allow newline, they are separated by colons and two spaces.) $\endgroup$
    – Rabbiiiiit
    Jul 27, 2023 at 14:55
  • $\begingroup$ X 0 S 0 0 0 0 X; X 0 1 0 1 1 1 0; D 0 1 0 1 0 1 0; 1 0 1 1 1 0 1 0; 1 0 0 0 0 0 1 0; 1 0 0 0 0 0 1 0; 1 1 1 1 1 1 1 0; 0 0 0 0 0 0 0 X; ② How to handle the situation inside the box? Surely there are some properties as you mentioned, in local region 90 degree turning will lose one bonus, but it's usually not the case when paths go through the box's middle column or the middle row directly (like "three-strike combo"). And how to correctly count bonuses at the boundaries of the boxes to set the weights of edges? $\endgroup$
    – Rabbiiiiit
    Jul 27, 2023 at 14:56
  • $\begingroup$ ③ Another extended demand which I didn't mension in the original question is that we're actually doing on a subgraph of the 2D grid graph. Some of the grid points may not give you bonus and at the same time cannot be a point on path. Anyway, maybe this demand could be studied later. $\endgroup$
    – Rabbiiiiit
    Jul 27, 2023 at 14:57
  • $\begingroup$ 2. what I'm still trying to understand in your answer is that: "Do dijkstra or bellman ford to find the longest path from source to destination. This is the solution." In my understanding, maximizing the total weights of path would be the longest path problem in an undirected cyclic graph with only positive edge-weights, and if negated to be the shortest path problem, there will be negative value cycles, where none of Dijkstra, Floyd, or Bellman-Ford would work out the solution. $\endgroup$
    – Rabbiiiiit
    Jul 27, 2023 at 14:57
  • $\begingroup$ (1) There should be a small number of configuration paths on a 3×3 box when src and dest are in it. Case work? $\endgroup$
    – LIR
    Jul 27, 2023 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.