2

Below are 25 rooms. The centre of the rooms are 1 unit apart from each other - horizontally and vertically. You want to visit all the rooms. You can only visit a room one time. You start in the "red squared" room.

Question:

If you can "jump" however you like from one room to another, what is the maximum distance you possibly can make? Can you prove this is the max?

My approach:

Is to always choose the room which is furthest away from the current room. E.g the first move would be to the room R1C5, second move to either of the rooms R4c1 or R5C2, and the third fourth..24th move following the same logic.

Intuitively this approach seems to lead to the optimal answer. But how to mathematically prove it? Or do you have other approaches?

enter image description here

Prim3numbah
  • 376
  • Can you jump diagonally? Also, what would be the distance from jumping from R1C5 to R3C2? – FilteredFrames Apr 11 '21 at 14:41
  • Yes diagonally is allowed. That would be sqrt(13). Just normal pythagoras – Prim3numbah Apr 11 '21 at 14:44
  • Is the distance measured from the room centre? – Parcly Taxel Apr 11 '21 at 14:50
  • yes, always from centre – Prim3numbah Apr 11 '21 at 14:51
  • I tried a lot for this but haven't really gotten anywhere and I am interested in seeing what people find. One route I was thinking is $\begin{align}\text{Maximize} \quad &y_1 + y_2 + y_3\ \text{Subject To} \quad &x_{k} = [i \text{ } j] \forall i,j,k\ &\sum_{k=1}^{25}\sqrt{|x_{k,1}-x_{k+1,1}|^2 + |x_{k+1,1}-x_{k+1,2}|^2}=y_1\quad(x_{k,1} \neq x_{k+1,1}) \text{ and } (x_{k,2} \neq x_{k+1,2}) \forall k\&\sum_{k=1}^{25}x_{k+1,1}-x_{k,1}=y_2\quad (x_{k+1, 2} = x_{k,2}) \forall k \ &\sum_{k=1}^{25}x_{k+1,2} - x_{k,2} =y_3\quad (x_{k+1, 1} = x_{k,1}) \forall k\ &x_1=[5 \text{ }1] \end{align} – FilteredFrames Apr 11 '21 at 15:55

2 Answers2

2

Optimal is $90.46$, obtained by solving a maximum traveling salesman problem (TSP): enter image description here

Explicitly, there are 26 nodes (one per room, plus a dummy node), and the 626 directed arcs are between all pairs of rooms and from the dummy to the red squared room. This structure forces that room to be visited first. Because you want to maximize and TSP minimizes total arc cost, take each arc cost to be the negative distance between the rooms (except costs in and out of the dummy node are 0).

RobPratt
  • 45,619
0

My iterative random shuffle arrives at 87.07

enter image description here

enter image description here

Axel Kemper
  • 4,943