patternMinor
Finding the most profitable path
Viewed 0 times
paththeprofitablefindingmost
Problem
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:
Here is an example:
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?
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:
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?
Solution
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$:
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.
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$:
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.
Context
StackExchange Computer Science Q#144882, answer score: 3
Revisions (0)
No revisions yet.