algorithm - 给定n个点，每个点都有自己的范围，调整所有点以最大化相邻点的最小距离

Question

在一维中取n个点:

每个点都可以在其上方箭头指示的特定范围内移动。这些范围是已知的。范围可以重叠。如何调整这些点以使相邻点的最小距离最大化？
我也可以接受近似值。
编辑:
我并不是在寻找代码，而是在寻找一般策略。
我真的不知道如何解决这个问题。
最初，我认为贪心算法可能会奏效。

设 p0 为起点，pn 为终点。让 dist(p0,p1) 代表 p0 和 p1 之间的距离。显然，p0 尽可能向左调整，pn 尽可能向右调整。

接下来，找到 dist(p0,pn)/n-1。这代表了每个点之间应该尽可能分散的最佳距离。将 p1 移动到该距离附近。

找到 dist(p1, pn)/n-2。将 p2 尽可能靠近这个距离。

重复其余的点。

这不起作用，因为稍后调整另一个指针可能会破坏之前的点。

Answer 1

这是一些 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 个点来给出一组“好”点，然后给每个点一个围绕该值的范围。该算法只是以随机顺序给出范围。有可能获得一组输入点，其中最佳可能的最小间隙很小或为零，没有任何算法可以提供帮助。

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]]

- - 更新 - -
我添加了代码来尝试找到给定顺序的最佳间隙。这明显更好。
locate_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]]