algorithmmathoptimizationmathematical-optimization
Given n points where each point has its own range, adjust all points to maximize the minimum distance of adjacent points
Take n points in one dimension:
Each point can be moved within a certain range indicated by the arrow above it. These ranges are known. Ranges can overlap. How can these points be adjusted so that minimum distance of adjacent points is maximized?
I would be okay with an approximation as well.
Edit: I am not really looking for code but a general strategy. I have really no idea how to solve this.
Originally, I thought a greedy algorithm might work.
Let p0 be the starting point and pn the ending point. Let dist(p0,p1) represent the distance between p0 and p1.Well obviously adjust p0 as far left as possible and pn as far right as possible.
Next, find dist(p0,pn)/n-1. This represents the optimal distance each point should be from each other to be as spread out as possible. Move p1 as close to this distance.
Find dist(p1, pn)/n-2. Move p2 as close to this distance as possible.
Repeat for rest of points.
This doesn't work because adjusting another pointer later on might ruin the previous points.
Solution
Here's some Ruby code, followed by sample results. The idea is to start with a random allocation of points to values within their ranges. Then we repeatedly do the following:
1. Find the minimum gap
2. Find all points that border a minimum gap
3. Re-randomize the values of those points
All the while, we remember the best solution so far. This won't give you the best possible result, but should give you a reasonably good result.
For the sample run, I gave a 'good' set of points by allocating 100 points evenly in a range of about 1100, then gave each point a range around that val. The algorithm was just given the ranges in random order. It's possible to get an input set of points where the best possible min gap is small or zero, which no algorithm can help with.
def test(n, range, max_attempts)
points = get_points_with_optimal_min_gap(n, range)
puts "input: #{points}"
allocation = allocate_points(points, max_attempts)
puts "solution: #{allocation.keys.sort}"
puts "best gap: #{get_min_gap(allocation, points)}"
puts "\n\nallocation:"
allocation.keys.sort.each do |k|
puts " #{k} => #{allocation[k]}"
end
end
def get_points_with_optimal_min_gap(n, range)
points = []
1.upto(n) do |num|
points.append([[0, num * range/n - rand(5*range/n)].max, num * range/n + rand(5*range/n)])
end
return points.shuffle
end
def allocate_points(input_points, max_attempts)
val_to_points = Hash.new {|h, k| h[k] = []}
input_points.each do |point|
val = get_rand_val_for_point(point)
val_to_points[val].append(point)
end
best_min_gap = -1
best_allocation = nil
attempts = 0
while attempts < max_attempts do
attempts += 1
min_gap = get_min_gap(val_to_points, input_points)
if min_gap > best_min_gap
best_min_gap = min_gap
best_allocation = deep_copy(val_to_points)
puts "found new gap after #{attempts} tries: #{best_min_gap}"
attempts = 0
end
vals_to_adjust = get_vals_bordering_min_gap(val_to_points, min_gap)
points_to_reallocate = []
vals_to_adjust.each do |val|
points_to_reallocate += val_to_points.delete(val)
end
points_to_reallocate.each do |point|
new_val = get_rand_val_for_point(point)
val_to_points[new_val].append(point)
end
end
return best_allocation
end
def get_vals_bordering_min_gap(val_to_points, min_gap)
vals_bordering_min_gap = Set.new()
if min_gap == 0
val_to_points.each do |val, points|
vals_bordering_min_gap.add(val) if points.size > 1
end
else
sorted_vals = val_to_points.keys.sort
prior_val = sorted_vals[0]
1.upto(sorted_vals.size - 1) do |i|
cur_val = sorted_vals[i]
cur_gap = cur_val - prior_val
if cur_gap == min_gap
vals_bordering_min_gap.add(cur_val)
vals_bordering_min_gap.add(prior_val)
end
prior_val = cur_val
end
end
return vals_bordering_min_gap.to_a
end
def get_min_gap(val_to_points, input_points)
return 0 if val_to_points.size < input_points.size
sorted_vals = val_to_points.keys.sort
prior_val = sorted_vals[0]
min_gap = nil
1.upto(sorted_vals.size - 1) do |i|
cur_val = sorted_vals[i]
min_gap = cur_val - prior_val if min_gap.nil? || cur_val - prior_val < min_gap
prior_val = cur_val
return min_gap if min_gap == 1
end
return min_gap
end
def get_rand_val_for_point(point)
return point[0] + rand(point[1] - point[0] + 1)
end
def deep_copy(int_to_arr_of_int_pairs)
new_hash = Hash.new {|h, k| h[k] = []}
int_to_arr_of_int_pairs.each do |int, arr|
arr.each do |int_pair|
new_hash[int].append([int_pair[0], int_pair[1]])
end
end
return new_hash
end
Sample Results
input: [[207, 258], [754, 826], [957, 993], [127, 158], [332, 352], [539, 615], [213, 236], [572, 590], [668, 712], [802, 823], [385, 427], [595, 641], [924, 1018], [20, 50], [698, 749], [318, 335], [64, 120], [462, 521], [708, 760], [513, 569], [806, 877], [364, 380], [732, 799], [896, 923], [947, 997], [250, 281], [798, 857], [717, 795], [542, 583], [910, 964], [277, 315], [168, 221], [263, 337], [858, 920], [316, 348], [646, 705], [557, 573], [293, 315], [48, 131], [488, 522], [252, 271], [269, 326], [43, 106], [673, 728], [399, 432], [140, 184], [564, 630], [906, 973], [508, 566], [0, 17], [493, 547], [782, 817], [184, 246], [230, 305], [5, 90], [446, 507], [429, 449], [822, 917], [35, 127], [630, 699], [888, 944], [899, 917], [179, 201], [715, 785], [40, 65], [338, 415], [908, 958], [2, 31], [469, 517], [649, 718], [96, 150], [380, 428], [347, 401], [197, 289], [849, 912], [603, 642], [805, 830], [564, 629], [19, 88], [80, 151], [593, 660], [932, 994], [479, 541], [291, 331], [175, 192], [842, 877], [987, 1028], [382, 432], [796, 884], [102, 160], [535, 587], [621, 696], [461, 476], [131, 170], [437, 469], [343, 410], [660, 713], [122, 171], [699, 752], [776, 782]]
found new gap after 1 tries: 0
found new gap after 2 tries: 1
found new gap after 8 tries: 2
found new gap after 9 tries: 3
found new gap after 35 tries: 4
found new gap after 87 tries: 5
found new gap after 384 tries: 6
found new gap after 8043 tries: 7
solution: [4, 12, 20, 31, 43, 51, 59, 68, 82, 102, 110, 119, 127, 134, 141, 148, 161, 172, 179, 188, 202, 209, 223, 233, 244, 251, 258, 273, 284, 299, 308, 326, 335, 344, 351, 361, 369, 376, 383, 395, 408, 415, 423, 430, 438, 454, 468, 482, 491, 499, 508, 515, 524, 532, 539, 549, 557, 574, 582, 589, 596, 615, 623, 634, 642, 649, 656, 663, 676, 693, 720, 728, 741, 748, 758, 769, 776, 786, 801, 808, 815, 827, 834, 842, 851, 858, 865, 872, 882, 899, 911, 935, 943, 952, 962, 974, 987, 996, 1011, 1028]
best gap: 7
allocation:
4 => [[0, 17]]
12 => [[5, 90]]
20 => [[2, 31]]
31 => [[20, 50]]
43 => [[19, 88]]
51 => [[40, 65]]
59 => [[35, 127]]
68 => [[43, 106]]
82 => [[64, 120]]
102 => [[96, 150]]
110 => [[80, 151]]
119 => [[48, 131]]
127 => [[122, 171]]
134 => [[102, 160]]
141 => [[140, 184]]
148 => [[127, 158]]
161 => [[131, 170]]
172 => [[168, 221]]
179 => [[179, 201]]
188 => [[175, 192]]
202 => [[184, 246]]
209 => [[207, 258]]
223 => [[197, 289]]
233 => [[213, 236]]
244 => [[230, 305]]
251 => [[250, 281]]
258 => [[252, 271]]
273 => [[263, 337]]
284 => [[269, 326]]
299 => [[277, 315]]
308 => [[293, 315]]
326 => [[291, 331]]
335 => [[318, 335]]
344 => [[316, 348]]
351 => [[332, 352]]
361 => [[347, 401]]
369 => [[343, 410]]
376 => [[364, 380]]
383 => [[338, 415]]
395 => [[382, 432]]
408 => [[399, 432]]
415 => [[380, 428]]
423 => [[385, 427]]
430 => [[429, 449]]
438 => [[437, 469]]
454 => [[446, 507]]
468 => [[461, 476]]
482 => [[479, 541]]
491 => [[469, 517]]
499 => [[462, 521]]
508 => [[488, 522]]
515 => [[493, 547]]
524 => [[513, 569]]
532 => [[508, 566]]
539 => [[535, 587]]
549 => [[539, 615]]
557 => [[557, 573]]
574 => [[542, 583]]
582 => [[572, 590]]
589 => [[564, 629]]
596 => [[564, 630]]
615 => [[595, 641]]
623 => [[603, 642]]
634 => [[630, 699]]
642 => [[593, 660]]
649 => [[621, 696]]
656 => [[649, 718]]
663 => [[646, 705]]
676 => [[660, 713]]
693 => [[668, 712]]
720 => [[673, 728]]
728 => [[699, 752]]
741 => [[698, 749]]
748 => [[717, 795]]
758 => [[708, 760]]
769 => [[715, 785]]
776 => [[776, 782]]
786 => [[732, 799]]
801 => [[754, 826]]
808 => [[802, 823]]
815 => [[782, 817]]
827 => [[805, 830]]
834 => [[806, 877]]
842 => [[796, 884]]
851 => [[798, 857]]
858 => [[822, 917]]
865 => [[842, 877]]
872 => [[858, 920]]
882 => [[849, 912]]
899 => [[899, 917]]
911 => [[896, 923]]
935 => [[906, 973]]
943 => [[888, 944]]
952 => [[908, 958]]
962 => [[910, 964]]
974 => [[957, 993]]
987 => [[932, 994]]
996 => [[947, 997]]
1011 => [[924, 1018]]
1028 => [[987, 1028]]
---- UPDATE ----
I added code to try to find the optimal gap for a given ordering. This is significantly better.
allocate_points() changed, and I added a new method called attempt_to_achieve_min_gap().
def attempt_to_achieve_min_gap(val_to_points, target_min_gap)
new_val_to_points = Hash.new {|h, k| h[k] = []}
leftmost_val = val_to_points.keys.min
leftmost_point = val_to_points[leftmost_val][0]
new_val_to_points[leftmost_point[0]].append(leftmost_point)
sorted_vals = val_to_points.keys.sort
prior_val = leftmost_val
1.upto(sorted_vals.length - 1) do |i|
cur_val = sorted_vals[i]
cur_point = val_to_points[cur_val][0]
target_val = prior_val + target_min_gap
if target_val <= cur_point[0]
new_val_to_points[cur_point[0]].append(cur_point)
prior_val = cur_point[0]
elsif target_val <= cur_point[1]
new_val_to_points[target_val].append(cur_point)
prior_val = target_val
else
return false
end
end
return new_val_to_points
end
def allocate_points(input_points, max_attempts)
val_to_points = Hash.new {|h, k| h[k] = []}
input_points.each do |point|
val = get_rand_val_for_point(point)
val_to_points[val].append(point)
end
best_min_gap = -1
best_allocation = nil
attempts = 0
while attempts < max_attempts do
attempts += 1
min_gap = get_min_gap(val_to_points, input_points)
if min_gap > 0
found_improvement = true
while found_improvement
found_improvement = false
trial_min_gap = [min_gap, best_min_gap].max + 1
improved_results = attempt_to_achieve_min_gap(val_to_points, trial_min_gap)
if improved_results
found_improvement = true
min_gap = trial_min_gap
puts "found improvement!: #{min_gap}"
val_to_points = improved_results
end
end
end
if min_gap > best_min_gap
best_min_gap = min_gap
best_allocation = deep_copy(val_to_points)
puts "found new gap after #{attempts} tries: #{best_min_gap}"
attempts = 0
end
vals_to_adjust = get_vals_bordering_min_gap(val_to_points, min_gap)
points_to_reallocate = []
vals_to_adjust.each do |val|
points_to_reallocate += val_to_points.delete(val)
end
points_to_reallocate.each do |point|
new_val = get_rand_val_for_point(point)
val_to_points[new_val].append(point)
end
end
return best_allocation
end
New sample results:
input: [[0, 21], [787, 819], [614, 642], [503, 553], [771, 854], [701, 740], [768, 807], [475, 480], [223, 251], [431, 473], [19, 67], [711, 764], [650, 673], [381, 401], [832, 907], [303, 357], [414, 480], [201, 215], [130, 182], [233, 269], [335, 417], [637, 704], [193, 242], [566, 632], [854, 927], [545, 577], [548, 574], [552, 607], [812, 868], [949, 962], [290, 334], [299, 372], [0, 31], [234, 304], [488, 540], [132, 215], [975, 994], [389, 406], [378, 437], [685, 721], [410, 453], [750, 800], [856, 919], [237, 270], [322, 355], [964, 1018], [67, 90], [925, 1015], [736, 792], [755, 823], [29, 78], [709, 761], [828, 897], [873, 927], [464, 533], [332, 380], [788, 831], [354, 413], [500, 545], [144, 196], [96, 138], [925, 982], [0, 67], [183, 207], [83, 116], [665, 679], [843, 904], [654, 694], [892, 955], [179, 203], [56, 87], [575, 636], [484, 542], [380, 439], [592, 689], [419, 431], [654, 700], [907, 978], [136, 151], [242, 313], [96, 126], [975, 1023], [449, 491], [866, 924], [117, 177], [291, 351], [460, 485], [959, 1004], [797, 846], [210, 277], [207, 240], [138, 184], [536, 606], [710, 774], [695, 714], [71, 83], [617, 629], [284, 302], [576, 633], [88, 137]]
found new gap after 1 tries: 0
found improvement!: 2
found improvement!: 3
found improvement!: 4
found improvement!: 5
found improvement!: 6
found new gap after 1 tries: 6
found improvement!: 7
found new gap after 5 tries: 7
found improvement!: 8
found improvement!: 9
found new gap after 2 tries: 9
found improvement!: 10
found new gap after 5686 tries: 10
solution: [0, 12, 22, 32, 42, 56, 67, 77, 87, 97, 107, 117, 127, 137, 147, 157, 167, 177, 187, 197, 207, 217, 227, 237, 247, 257, 267, 277, 287, 297, 307, 317, 327, 337, 347, 357, 367, 377, 389, 399, 409, 419, 429, 439, 449, 459, 469, 479, 489, 499, 509, 519, 529, 539, 549, 559, 569, 579, 589, 599, 614, 624, 634, 644, 654, 664, 674, 684, 694, 704, 714, 724, 734, 744, 754, 764, 774, 784, 794, 804, 814, 824, 834, 844, 854, 864, 874, 884, 894, 904, 914, 925, 935, 949, 959, 975, 985, 995, 1005, 1015]
best gap: 10
allocation:
0 => [[0, 31]]
12 => [[0, 21]]
22 => [[0, 67]]
32 => [[19, 67]]
42 => [[29, 78]]
56 => [[56, 87]]
67 => [[67, 90]]
77 => [[71, 83]]
87 => [[83, 116]]
97 => [[88, 137]]
107 => [[96, 126]]
117 => [[117, 177]]
127 => [[96, 138]]
137 => [[132, 215]]
147 => [[136, 151]]
157 => [[144, 196]]
167 => [[130, 182]]
177 => [[138, 184]]
187 => [[179, 203]]
197 => [[183, 207]]
207 => [[201, 215]]
217 => [[207, 240]]
227 => [[223, 251]]
237 => [[193, 242]]
247 => [[237, 270]]
257 => [[210, 277]]
267 => [[233, 269]]
277 => [[234, 304]]
287 => [[242, 313]]
297 => [[284, 302]]
307 => [[291, 351]]
317 => [[290, 334]]
327 => [[303, 357]]
337 => [[322, 355]]
347 => [[299, 372]]
357 => [[354, 413]]
367 => [[335, 417]]
377 => [[332, 380]]
389 => [[389, 406]]
399 => [[381, 401]]
409 => [[378, 437]]
419 => [[419, 431]]
429 => [[380, 439]]
439 => [[410, 453]]
449 => [[431, 473]]
459 => [[414, 480]]
469 => [[460, 485]]
479 => [[475, 480]]
489 => [[449, 491]]
499 => [[464, 533]]
509 => [[488, 540]]
519 => [[484, 542]]
529 => [[500, 545]]
539 => [[503, 553]]
549 => [[545, 577]]
559 => [[548, 574]]
569 => [[566, 632]]
579 => [[552, 607]]
589 => [[536, 606]]
599 => [[576, 633]]
614 => [[614, 642]]
624 => [[617, 629]]
634 => [[575, 636]]
644 => [[592, 689]]
654 => [[650, 673]]
664 => [[637, 704]]
674 => [[665, 679]]
684 => [[654, 694]]
694 => [[654, 700]]
704 => [[695, 714]]
714 => [[685, 721]]
724 => [[709, 761]]
734 => [[701, 740]]
744 => [[711, 764]]
754 => [[750, 800]]
764 => [[710, 774]]
774 => [[768, 807]]
784 => [[736, 792]]
794 => [[787, 819]]
804 => [[755, 823]]
814 => [[788, 831]]
824 => [[771, 854]]
834 => [[797, 846]]
844 => [[812, 868]]
854 => [[828, 897]]
864 => [[832, 907]]
874 => [[843, 904]]
884 => [[866, 924]]
894 => [[873, 927]]
904 => [[856, 919]]
914 => [[854, 927]]
925 => [[925, 982]]
935 => [[892, 955]]
949 => [[949, 962]]
959 => [[907, 978]]
975 => [[975, 994]]
985 => [[964, 1018]]
995 => [[959, 1004]]
1005 => [[925, 1015]]
1015 => [[975, 1023]]