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)


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.


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.