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

- Using FSI to execute F# code from a .NET app (8)
- Excel ScatterPlot with labels, colors and markers (29)
- S-shaped market adoption curve (37)
- Plot functions from F# to Excel (4)

Comment RSSDave Thomas wrote: If anyones interested I wrote a couple of article ... [More]

Ron wrote: Mathias, That was just what I was looking for. T... [More]

Mathias wrote: Hi Scott, I don't know of an existing implementati... [More]

Mathias wrote: Damn - that is a bit strange, I will look into it.... [More]