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

- Read the contents of a worksheet with C# (27)
- Create an Excel 2007 VSTO add-in: adding a WPF control (14)
- Management, the Gordon Ramsay way (4)
- How dense is the product of Sparse Matrices? (5)

Comment RSSDewayne wrote: Wonderful beat ! I would like to apprentice while ... [More]

Healthy Weight Loss Tips After Pregnancy wrote: This could possibly be enough to help you fit comf... [More]

maximum shred reviews wrote: You really make it seem so easy with your presenta... [More]

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