1

I've encountered a problem which I think is rather suited to be solved using a Constraint Satisfaction Problem algorithm. I am however, not entirely certain that this is the best approach, as the specifics seem to deviate a bit from the classical CSP problems.

The problem:

I've got a list of entities that I need to match together based on a heuristic, which has been calculated using a distance function.

The list might look like this:

Entity A
    - H(euristic): 0.1 -> Entity B
    - H: 0.25 -> Entity D

Entity B
    - H: 0.1 -> Entity A
    - H: 0.4 -> Entity C

Entity C
    - H: 0.4 -> Entity B

Entity D
    - H: 0.25 -> Entity A

Now what I wish to accomplish is to match these entities together 1 to 1, where the only constraint of the problem, is that any entity can only be matched with 1 entity. Which in the case above, obviously mean that the solution would be 2 sets of entities linked together.

Now this might be an easy task, but this is where my problem deviates from the CSP problems I've encountered in the past.

I wish to find a solution based on the following criterias:

 - 1. Most amount of matches (Some entities might not know of more than 1 other entity, if the heuristic is too high, it will not be included in the list of possible relationships).
 - 2. Lowest overall cost of matching entities.

Another main feature of this problem, is that it doesn't have to be solved to perfection. Not every Entity needs to have a match. If leaving out a single entity for matching will result in 2 more matches down the road, then that would be prefered.

And by the way, a solution to the example above based on the mentioned criterias could be the following:

- Entity A <--> Entity D
- Entity B <--> Entity C

If the entity list was bigger, and there were to be two solutions with the same amount of matches, I'd obviously want to compare these on the heuristic cost, and pick the lowest of these.

Now the question is what kind of algorithm would be the best fit for this kind of problem? If CSP is the choice, then how would I go about allowing it to return an (unsolved) dataset, but pick the best partial solution with the least amount of iterations?

Edit:

Example of dataset that's been run through the algorithm dan1111 provided.

I forgot to mention that the higher the heuristic, the better in this case. Should've done a 1-h, before I took the screenshot. enter image description here

1

A simple algorithm that should provide pretty good results is:

  • Select the groups with the fewest potential matches.
  • Within those groups, select the closest match.
  • Repeat the process, with all "used" entities removed, until no more matches are found.

I have used this algorithm with a similar problem (but 1:N matching instead of 1:1 matching) with good results. It also can be implemented quite efficiently in a set-based manner in SQL (which was a requirement for me).

  • I already tried a similar approach, but one of it's flaws is that it doesn't evaluate any alternative options, and therefor it's likely to pick a non-optimized match, just for the sake of matching. In my previous iterations with this algorithm, if I had an uneven number of entities, the one that was left out, would in most cases be a better match than most. Mainly because it's one of the last entities to be searched in, as it has the most potential matches. – Mathias Nov 8 '16 at 10:34
  • @Mathias hmmm, that's interesting. Would it be possible to update your question with a more illustrative example? In the one that is given, there will be exactly two matches, no matter which ones are selected, so it is hard to think about the optimization. – user82096 Nov 8 '16 at 10:44
  • I've updated the question with a picture. As you can see the 8th entity (node) is a much better match for the 2nd entity than the 4th is. But the 4th node has priority in the final list over the 8th, because it's been visited first as the list was orded by the amount potential matches. – Mathias Nov 8 '16 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.