3
$\begingroup$

I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this.

To put it simply, the problem is the following:

  • We want to go from point A to point B, nice and simple, we can easily find the shortest path.
  • Each cell on our grid has a certain value, let's say we win some money by going through cells. So we do not want the shortest path but the most profitable one.
  • But, we have a step limitation (known to be at least sufficient to make it from A to B). So we cannot just go on every cell, we have to find an optimized path.

Here is an example: enter image description here

1, 2 and 3 represent cell values, the step limit is arbitrary but you get the idea.

The problem is: How to find the most valuable path we can take, and still make it to point B ?

Any thoughts on this?

$\endgroup$
4
  • 1
    $\begingroup$ All the cells have positive weight $\geq 0$ right? Also are A and B always placed at the corners of your grid? Can i visit a cell twice and get the money twice (walking in a loop)? $\endgroup$
    – plshelp
    Oct 18 at 8:13
  • 1
    $\begingroup$ If you can move N, S, E, W but not diagonally, and visiting a cell multiple times only gives you the score once, then this is NP-complete by reduction from rectilinear TSP, so don't expect a poly-time algorithm. $\endgroup$ Oct 18 at 12:28
  • $\begingroup$ It could be FPT parameterized by the "above guarantee", i.e. finding the max-weight path with length $k+d$ from $s$ to $t$, where $d = \text{dist}_G(s,t)$, parameterized by $k$ (see e.g. $s$-$t$-detour problem). $\endgroup$
    – Pål GD
    Oct 18 at 13:04
  • $\begingroup$ If the step limit is dist(s,t), then you can find the optimal solution in linear time. $\endgroup$
    – Pål GD
    Oct 18 at 13:16
3
$\begingroup$

The problem is NP-hard even in case of grid graphs and profits in $\{0,1,2\}$ by a reduction from Hamiltonian path on graphs that can be embedded on grids (the Hamiltonian path problem remains hard in this case).

Here is a sketch of the reduction. Embed the instance of the input graph on a grid (this can be done in polynomial time). Make sure the grid is fine enough and that all the edges become paths of the same length $\ell \ge 2$.

Assign a profit of $1$ to each cell corresponding to an edge. Assign a profit of $2$ to the cells corresponding to the vertices. Assign a profit of $0$ to all other cells. There exists an Hamiltonian path from $s$ to $t$ in the input graph if and only if the maximum profit of a path of length at most $(n-1)\ell+n-1$ that goes from the location corresponding to $s$ to the location corresponding to $t$ in the grid is $2n + (n-1)\ell$.

Here is an example with $n=10$ and $\ell=2$:

enter image description here

The best path of length at most $(n-1)\ell + (n-1)=27$ encounters exactly $28$ cells: all $10$ cells corresponding to vertices, plus $28-10=18$ cells corresponding to $9$ edges. It's total profit is $10 \cdot 2 + 18 = 38$. Notice that this is the best possible profit since we collect all cells with profit $2$ and no cell with profit $0$.

Note: It seems that you allow diagonal moves. The above construction might allow some vertices to be "shortcutted" by moving diagonally but this can be fixed. An easy way to do so is to "rotate" everything by 45 degrees, so that edges correspond to diagonal lines.

$\endgroup$
9
  • $\begingroup$ I am not 100% sure, but I doubt this will work in a long "path-like" graph, where we "curl" the graph "backwards" at the middle point, and near the end node of this "path" expand it to have at least $2$ width. Now, a path on this graph will have to go through the entire string, going through the "middle node", and finishing at the end, while in the "grid" you can go through the $0$ tiles to create a shortcut to the end and possibly get more reward. Again, I'm not 100% sure this is a valid counter-example, and I think its at least worth to mention those kinds of "shortcuts", to avoid mistakes $\endgroup$
    – nir shahar
    Oct 18 at 12:51
  • 1
    $\begingroup$ If you collect even a single $0$ tile then you won't be able to reach the desired profit (which is the sum of all tiles of profit $2$ with as many tiles of profit 1 as we are allowed to encounter before the returned path becomes too long). (Notice that in my previous version of the answer I let the profit of vertex-tiles be a parameter $M$. I have now fixed $M=2$ for simplicity). $\endgroup$
    – Steven
    Oct 18 at 12:54
  • $\begingroup$ Are you sure, because if the graph is constructed in such a way that we cant go through its entirety with one path, then this "shortcut" does in fact prove problematic. I'm no expect in cubic graphs, so I have no idea if this is possible $\endgroup$
    – nir shahar
    Oct 18 at 13:11
  • $\begingroup$ I'm not 100% sure I'm visualizing the graph you describe correctly but it seems that you want to skip some vertices. The number of visited cells of a path is at most $L=(n-1)\ell + n$. A Hamiltonian path collects the maximum possible profit of $P = 2 \cdot n + (L-n)$ since it traverses all tiles with profit $2$ (i.e., all vertices) and never touches a tile with profit $0$. If you skip at least one vertex then the maximum profit must be at most $2 \cdot (n-1) + (L-n+1) = P-1$. Similarly, if you ever touch a tile with profit $0$ the overall profit will be at most $2\cdot n + (L-n-1) = P-1$. $\endgroup$
    – Steven
    Oct 18 at 16:31
  • $\begingroup$ Then my question is: is it guaranteed to have a Hamiltonian path in cubic graphs? $\endgroup$
    – nir shahar
    Oct 18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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