Minimization of the total Euclidean distance from balls to holes is quite difficult optimization problem (I'm not sure, may be it is a NP-problem). As a start point I propose a simple greedy algorithm:
- Find the nearest hole for every ball.
- Put balls to holes starting from the closest ball-hole pair while the corresponding holes are empty
- Repeat
It is not the best algorithm and may be I will update my post in the future.
n = {5, 5};
holes = N@Tuples@Range@n;
balls = RandomReal[{0, # + 1}, Times @@ n] & /@ n // Transpose;
Graphics[{PointSize[Large], Point[holes], Red, PointSize[Medium], Point[balls]}]
res = Flatten[#, 2] &@ Last@Reap@
Module[{h = holes, b = balls, nh, nb, nf, num, put, fill,
nondup},
nb = nh = Range@Length@h;
While[h != {},
nf = Nearest[h -> Automatic];
num = nf /@ b // Flatten;
put = Ordering@Total[(h[[num]] - b)^2, {2}];
fill = num[[put]];
nondup = Floor@BinarySearch[Range@Length@fill, 1/2,
1 - Boole@DuplicateFreeQ@fill[[;; #]] &];
put = put[[;; nondup]];
fill = fill[[;; nondup]];
Sow@Transpose@{nb[[put]], nh[[fill]]};
b = Delete[b, Transpose@{put}];
nb = Delete[nb, Transpose@{put}];
h = Delete[h, Transpose@{fill}];
nh = Delete[nh, Transpose@{fill}];
]
]
(* {{8, 24}, {13, 5}, {19, 16}, {23, 10}, {1, 23}, {3, 17}, {5,
14}, {16, 21}, {17, 3}, {9, 8}, {7, 4}, {18, 11}, {4, 22}, {21,
15}, {11, 20}, {2, 6}, {14, 2}, {10, 7}, {15, 9}, {25, 1}, {12,
25}, {6, 18}, {22, 19}, {20, 13}, {24, 12}} *)
Graphics[{PointSize[Large], Point[holes], Red, PointSize[Medium],
Point[balls], Arrow[{balls[[#]], holes[[#2]]} & @@@ res]}]
