Thread Subject: How to quickly generate list of traversal schemes

I have ran into a speed barrier on a piece of code I'm working, and I hope some of you guys can offer any advice on my problem.

I have to determine the best way to connect source points to destination points for use in a blob tracking algorithm. Because of the non descriptive nature of the blobs, I effectively have a list of points for the set of destinations and sources. I also have the distances between each source and destination pair.

Now, for the problem. I need to find mutually exclusive sets (no destination can have a source that another node has, and a source can have no destination that another source has). After generating the sets, I can determine the weights and pick the best.

I am currently doing this with a brute force method (with a few optimizations), but still have serious speed issues on the size of the arrays that I am using.

The bottleneck is generating the sets. Any ideas on how to do this faster?

Jeremy Freeman wrote:
> I have ran into a speed barrier on a piece of code I'm working, and I
> hope some of you guys can offer any advice on my problem.
>
> I have to determine the best way to connect source points to destination
> points for use in a blob tracking algorithm. Because of the non
> descriptive nature of the blobs, I effectively have a list of points for
> the set of destinations and sources. I also have the distances between
> each source and destination pair.
>
> Now, for the problem. I need to find mutually exclusive sets (no
> destination can have a source that another node has, and a source can
> have no destination that another source has). After generating the
> sets, I can determine the weights and pick the best.
>
> I am currently doing this with a brute force method (with a few
> optimizations), but still have serious speed issues on the size of the
> arrays that I am using.
>
> The bottleneck is generating the sets. Any ideas on how to do this faster?

This sounds to me to be possibly equivalent to "The Marriage Problem",
http://www.cut-the-knot.org/arithmetic/marriage.shtml