给定 n 个点，每个点都有自己的范围，调整所有点以最大化相邻点的最小距离
Given n points where each point has its own range, adjust all points to maximize the minimum distance of adjacent points
一维取n个点：
每个点都可以在上面箭头指示的一定范围内移动。这些范围是已知的。范围可以重叠。如何调整这些点，使相邻点的最小距离最大化？
我也可以接受近似值。
编辑：
我不是真的在寻找代码，而是在寻找一般策略。
我真的不知道如何解决这个问题。
最初，我认为贪心算法可能会起作用。
设p0为起点，pn为终点。设dist(p0,p1)表示p0到p1.Well的距离，显然p0尽量往左，pn尽量往右
接下来，求dist(p0,pn)/n-1。这表示每个点之间应尽可能分散的最佳距离。将 p1 移动到接近此距离。
求 dist(p1, pn)/n-2。将 p2 移动到尽可能靠近此距离。
重复其余点数。
这不起作用，因为稍后调整另一个指针可能会破坏之前的点。
这是一些 Ruby 代码，后面是示例结果。这个想法是从将点随机分配到其范围内的值开始。然后我们重复执行以下操作：
1. Find the minimum gap
2. Find all points that border a minimum gap
3. Re-randomize the values of those points
一直以来，我们都记得迄今为止最好的解决方案。这不会给你最好的结果，但应该给你一个相当好的结果。
对于示例 运行，我通过在大约 1100 的范围内均匀分配 100 个点来给出一组 'good' 点，然后给每个点一个围绕该值的范围。该算法只是以随机顺序给出了范围。可以获得一组输入点，其中最佳可能最小间隙很小或为零，这是任何算法都无法解决的。
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
示例结果
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]]
----更新----
我添加了代码以尝试找到给定顺序的最佳间隙。这明显更好。
allocate_points() 改变了，我添加了一个名为 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
新样本结果：
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]]
您可以对间隙大小进行二进制搜索：执行现有的步骤 1 和 2 以获得最佳可实现间隙大小的上限 gap。设置 delta = gap / 2。现在继续将其他点精确 gap 分开布置，直到成功完成或导致不可能的情况：如果完成，则设置 gap += delta，否则设置 gap -= delta。无论哪种方式，设置 delta /= 2 并重新运行。重复直到 delta 低于您想要的精度阈值。
一维取n个点：
每个点都可以在上面箭头指示的一定范围内移动。这些范围是已知的。范围可以重叠。如何调整这些点，使相邻点的最小距离最大化？
我也可以接受近似值。
编辑： 我不是真的在寻找代码，而是在寻找一般策略。 我真的不知道如何解决这个问题。
最初，我认为贪心算法可能会起作用。
设p0为起点，pn为终点。设dist(p0,p1)表示p0到p1.Well的距离，显然p0尽量往左，pn尽量往右
接下来，求dist(p0,pn)/n-1。这表示每个点之间应尽可能分散的最佳距离。将 p1 移动到接近此距离。
求 dist(p1, pn)/n-2。将 p2 移动到尽可能靠近此距离。
重复其余点数。
这不起作用，因为稍后调整另一个指针可能会破坏之前的点。
这是一些 Ruby 代码，后面是示例结果。这个想法是从将点随机分配到其范围内的值开始。然后我们重复执行以下操作：
1. Find the minimum gap
2. Find all points that border a minimum gap
3. Re-randomize the values of those points
一直以来，我们都记得迄今为止最好的解决方案。这不会给你最好的结果，但应该给你一个相当好的结果。
对于示例 运行，我通过在大约 1100 的范围内均匀分配 100 个点来给出一组 'good' 点，然后给每个点一个围绕该值的范围。该算法只是以随机顺序给出了范围。可以获得一组输入点，其中最佳可能最小间隙很小或为零，这是任何算法都无法解决的。
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
示例结果
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]]
----更新----
我添加了代码以尝试找到给定顺序的最佳间隙。这明显更好。
allocate_points() 改变了，我添加了一个名为 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
新样本结果：
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]]
您可以对间隙大小进行二进制搜索：执行现有的步骤 1 和 2 以获得最佳可实现间隙大小的上限 gap。设置 delta = gap / 2。现在继续将其他点精确 gap 分开布置，直到成功完成或导致不可能的情况：如果完成，则设置 gap += delta，否则设置 gap -= delta。无论哪种方式，设置 delta /= 2 并重新运行。重复直到 delta 低于您想要的精度阈值。