Skip to main content
added 28 characters in body
Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

Because of the [no-computers] tag, I waited to post this answer until somebody else already proved optimality.

A graph-based approach to this problem is to first compute all-pairs shortest-path distances in an undirected graph with a node for each grassy square and an edge between nodes that are horizontal or vertical neighbors. Then solve a traveling salesman problem on a complete graph where the shortest-path distances are the edge weights. As in my answer to a similar problem, introduce a dummy node adjacent to all other nodes to allow the starting and ending squares to be anywhere.

As expected, the resulting optimal objective value is $110$, which corresponds to $111$ squares mowed:

enter image description here

Because of the [no-computers] tag, I waited to post this answer until somebody else already proved optimality.

A graph-based approach to this problem is to first compute all-pairs shortest-path distances in an undirected graph with a node for each grassy square and an edge between nodes that are horizontal or vertical neighbors. Then solve a traveling salesman problem on a complete graph where the shortest-path distances are the edge weights. As in my answer to a similar problem, introduce a dummy node to allow the starting and ending squares to be anywhere.

As expected, the resulting optimal objective value is $110$, which corresponds to $111$ squares mowed:

enter image description here

Because of the [no-computers] tag, I waited to post this answer until somebody else already proved optimality.

A graph-based approach to this problem is to first compute all-pairs shortest-path distances in an undirected graph with a node for each grassy square and an edge between nodes that are horizontal or vertical neighbors. Then solve a traveling salesman problem on a complete graph where the shortest-path distances are the edge weights. As in my answer to a similar problem, introduce a dummy node adjacent to all other nodes to allow the starting and ending squares to be anywhere.

As expected, the resulting optimal objective value is $110$, which corresponds to $111$ squares mowed:

enter image description here

Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

Because of the [no-computers] tag, I waited to post this answer until somebody else already proved optimality.

A graph-based approach to this problem is to first compute all-pairs shortest-path distances in an undirected graph with a node for each grassy square and an edge between nodes that are horizontal or vertical neighbors. Then solve a traveling salesman problem on a complete graph where the shortest-path distances are the edge weights. As in my answer to a similar problem, introduce a dummy node to allow the starting and ending squares to be anywhere.

As expected, the resulting optimal objective value is $110$, which corresponds to $111$ squares mowed:

enter image description here