|
To make the "minimize the equation" approach complete, other paths should be considered, such as instead of going up to the ceiling, going to the side and taking a side wall. Some limits can be placed on the number of possible paths by considering some general properties of an optimal solution: 1. Assuming the start point is A, and the path leaves the start side at point B, the optimal path will take a straight line from A to B. Proof: if it were not straight, it could be replaced by a straight line which would shorten the path, contradicting the assumption the path was optimum. 2. Once the optimal path leaves a side, it will not return to that side. Proof. Suppose the path leaves the side at point B, then later enters at C, and then leaves again at D. The route from B to C could be replaced with a straight line from C to D, which would shorten the path, again contradicting the assumption that the path was optimum. This cuts down the number of possible path templates greatly, since a given surface can only appear once in the optimal path, and only contain a single straight line segment. I expect that a little more reasoning can deduce some more limits on possible optimal paths, to get it down to just two or three possible equations to maximize. |