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

- How dense is the product of Sparse Matrices? (5)
- Testing and mocking your C# code with F# (5)
- Field notes from the F# tour (2)
- Throttling F# Events using the Reactive Extensions (3)

Comment RSSHow To Reverse Aging wrote: Hello, I enjoy reading all of your article. I want... [More]

thetaoofbadassus.tumblr.com wrote: I have read so many articles about the blogger lov... [More]

reverseagingprocess.newsvine.com wrote: Normally I do not read post on blogs, however I wo... [More]

How To Cure Herpes wrote: Thanks for finally writing about > Throttling F... [More]