I am stucked at this problem:
Suppose we have the following grid configuration (or matrix) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$
(I.e $G$ is a matrix that have $m$ rows and $n$ colums over the alphabet $\{0,x,y\}$) $$G= \begin{bmatrix} 0 & 0 & x & \cdots & x \\ 0 & 0 & x & \cdots & 0 \\ x & y & 0 & \cdots & x \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & x& 0& \cdots & 0 \end{bmatrix} $$
What is the minimal number of steps required for $y$ to visit each of the $x$'s on the grid (I.e.each of the $x$'s in the matrix) at least once where $y$ can move left, right, up and down one cell at a time?
(The $y$ and the $x$'s in the grid $G$ were arbitrarily placed, The $y$ and the $x$'s can be anywhere on the matrix, Also the number of the $x$'s on the matrix was arbitrary and there must be exactly one $y$ on the matrix).
I hope that there is some kind of mathematical formula (or summation) that can give the exact answer (in contrast to an algorithm).
And if there must be some use of an algorithm maybe we could find a sufficiently tight lower bound for the actual number?
Thanks for any hint or help.
This is of course the Traveling Salesman Problem in the special case where the distances are given by the Manhattan norm.
Even this special case is NP-hard, so don't hope for a formula, or even an algorithm that scales well.
I found this reference, but haven't read it myself: