Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a 2x2 grid and I have 5 tokens. I want to place 4 of the 5 tokens on the grid.

Each token has a different value depending on where they are placed on the grid. Essentially if they should not be placed in a certain position they are awarded a value of 20, otherwise they have a score lower than 20.

I am writing a program that needs to figure out which 4 tokens should be placed, in order to use the ones with the lowest value possible.

I need this part of the program to be as fast as possible. I'm wondering if there is an optimal algorithm I should use. I have been researching and came across the Hungarian algorithm but I'm wondering if there is another option I should be considering.

Here is an example of the problem:

My grid has its' positions labelled, a,b,c,d ...

+--------+--------+ | c | d | | | | +--------+--------+ | a | b | | | | +--------+--------+

And I have the following tokens with corresponding values for each location on the grid... a b c d token_p = [20, 20, 15, 20] token_r = [ 1, 1, 20, 20] token_s = [15, 20, 20, 20] token_t = [20, 10, 20, 10] token_u = [20, 20, 5, 20]

The answer should be:

token_s = a (value 15)

token_r = b (value 1)

token_u = c (value 5)

token_t = d (value 10)

share|improve this question
add comment

1 Answer 1

I would create a weighted $K_{t, n}$ graph, with tokens in one partition and grid slots on the other, and use a greedy bipartite matching algorithm.

Here is a tutorial on general bipartite matching: http://www.dreamincode.net/forums/topic/304719-data-structures-graph-theory-bipartite-matching/

You will have to adapt it for a greedy approach.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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