2

I am stuck at this problem:

Suppose we have the following m by n grid configuration (or matrix) G over the alphabet {0,X,Y}

G=
0 0 X .. X
0 0 X .. 0
X Y 0 .. X
:  :  :      :
0 X 0 .. 0

Find a good lower bound on 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).

Surely there is no some kind of mathematical formula that can give the exact number of steps (Since it is a TSP problem).

But how can we find a sufficiently tight lower bound for the actual number of steps (that is relatively easy to calculate using an algorithm, for example)?

I've seen what was suggested on:

Using A* to solve Travelling Salesman

And it was suggested there that the total cost of the minimum spanning tree can be a good lower bound for TSP problems.

But in contrast to the problem there, Here, In this problem, We are not required to visit each of the points on the grid, But we are required to visit each of the "special" points on the grid at least once and to get to them we may need to visit some "non-special" points on the grid, So I do not know how the minimum spanning tree looks like for this problem (and maybe how to adjust Kruskal's algorithm to find it).

(Note: I've encountered this problem while trying to figure out a heuristic for A* grid search that calculates a path for Y that must visit each of the X's on the grid at least once)

Thanks for any hint or help.

Community
  • 1
  • 1
MathNerd
  • 170
  • 3
  • 11

1 Answers1

1

If I understood the question correctly, a tight lower bound on the objective of the described problem is demanded. Such a bound is in fact the minimum spanning tree of the instance; the distances would be the pairwise shortest paths between the X and Y node (which in this case are some discrete Euklidean distances). The tightness of the bound can be seen considering an instance which looks like

YXXXXX...X

where the weight of the spanning tree (namely the number of nodes to visit minus one) matches the weight of the shortest path from Y to the rightmost X node. In total, Kruskal's algorithm does not need to be modified to calculate the minimum spanning tree.

Codor
  • 17,447
  • 9
  • 29
  • 56
  • But what about the points on the grid that are not required to be visited? Do they need some kind of special treatment? Am I supposed to include them in the **minimum spanning tree**? – MathNerd Apr 01 '16 at 07:42
  • Conceptually, the intermediate nodes can be removed from the problem once the distances for each pairs of `X` and `Y` nodes have been precalculated. – Codor Apr 01 '16 at 07:50