Friday, June 25, 2010

Exact Solution for the Minimum Links Problem

It is possible to solve the Minimum Links Problem exactly without having to resort to using the curved lines. The center of the circle through two of the points, K, can be determined as follows with σ = 1 or -1 indicating whether the center is above or below the line joining the two points respectively as well as the radius of curvature, ρ.

One can eliminate the X·X term from the two equations for the circles to get a vector equation for a straight line. X can then be defined as a linear combination of ΔK and its normal ΔK' and the unknown parameters, λ and μ, can be found by substituting into the equations for the line and one of the circles.

Edit: This solution and the previous one are alternative solutions to Problem 1.14 in Schaum's Outline of Operations Research by Richard Bronson.

No comments: