Last week’s StackOverflow newsletter contained a fun problem I had never seen before: Bipartite Matching. Here is the problem:

*There are N starting points (purple) and N target points (green) in 2D. I want an algorithm that connects starting points to target points by a line segment (brown) without any of these segments intersecting (red) and while minimizing the cumulative length of all segments.*

*Image from the original post on StackOverflow*

I figured it would be fun to try out Bumblebee, my artificial bee colony library, on the problem. As the accepted answer points out, the constraint that no segment should intersect is redundant, and we only need to worry about minimizing the cumulative length, because reducing the length implies removing intersections.

As usual with Bumblebee, I’ll go first with the dumbest thing that could work. The solution involves matching points from two lists, so we’ll define a record type for Point and represent a Solution as two (ordered) lists of points, packed in a Tuple:

type Point = { X: float; Y: float }

let points = 100
let firstList = [ for i in 0 .. points -> { X = (float)i ; Y = float(i) } ]
let secondList = [ for i in 0 .. points -> { X = (float)i ; Y = float(i) } ]
let root = firstList, secondList

We’ll start with a silly problem, where the 2 lists are identical: the trivial solution here is to match each point with itself, resulting in a zero-length, which will be convenient to see how well the algorithm is doing and how far it is from the optimum.

How can we Evaluate the quality of a solution? We need to pair up the points of each of the lists, compute the distance of each pair, and sum them up – fairly straightforward:

let distance pair =
((fst pair).X - (snd pair).X) ** 2.0 + ((fst pair).Y - (snd pair).Y) ** 2.0
let evaluate = fun (solution: Point list * Point list) ->
List.zip (fst solution) (snd solution)
|> List.sumBy (fun p -> – distance p)

More...

## Comments

- It takes one to know one (3)
- Create optimization programs dynamically with C# and the Microsoft Solver Foundation (9)
- Free trade (1)
- AdaBoost in F# (2)

Comment RSSRon wrote: Statistics are used much like a drunk uses a lampp... [More]

green coffee bean pure extract 800 mg wrote: Hello there I am so grateful I found your web site... [More]

buyinvestmentpropertyonline.com wrote: Howdy I am so thrilled I found your site, I really... [More]

Suggested Internet page wrote: I am now not certain where you are getting your in... [More]