Минимальная сумма всех времен путешествия

Question

Я нашел головоломку онлайн на интервьюStreet и попытался решить ее следующим образом:

Существует бесконечная целочисленная сетка, в которой N людей имеют свои дома. Они решили объединяйтесь в общем месте встречи, которое является чьим-то домом. Из любой клетки все 8 соседние ячейки достижимы за 1 единицу времени. например: (x, y) может быть достигнуто из (x-1, y + 1) в одну единицу времени. Найдите общее место встречи, которое минимизирует сумму время в пути всех людей.

Сначала я подумал о том, чтобы написать решение со сложностью n² во времени, но есть ограничения

1 <= N <= 10 ^ 5 и абсолютное значение каждой координаты на входе будет не более 10 ^ 9 </p>

Итак, я изменил свой первый подход и вместо того, чтобы смотреть на проблему с расстояниями и временем в пути, я смотрел на разные дома как на разные тела с разным весом. И вместо вычисления всех расстояний я ищу центр тяжести группы тел.

Вот код моей функции «решить», vectorToTreat - это таблица lengthX2, в которой хранятся все данные о точках на сетке, а resul - это число, которое нужно напечатать на стандартный вывод:

long long solve(long long** vectorToTreat, int length){
    long long resul = 0;
    int i;
    long long x=0;
    long long y=0;
    int tmpCur=-1;
    long long tmp=-1;
    for(i=0;i<length;i++){
        x+=vectorToTreat[i][0];
        y+=vectorToTreat[i][1];
    }
    x=x/length;
    y=y/length;
    tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y));
    tmpCur = 0;
    for(i=1;i<length;i++){
        if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))<tmp){
            tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y));
            tmpCur = i;
        }
    }
    for(i=0;i<length;i++){
        if(i!=tmpCur)
            resul += max(absol(vectorToTreat[i][0]-vectorToTreat[tmpCur][0]),absol(vectorToTreat[i][1]-vectorToTreat[tmpCur][1]));
    }

    return resul;
}

Проблема сейчас в том, что я прошел 12 официальных тестов за 13, и я не вижу, что я делаю не так, какие-либо идеи? Заранее спасибо. AE

Answer 1

Ключом к этой проблеме является понятие центроид множества точек . Место встречи - самый близкий дом к центроиду для множества точек, представляющих все дома. При таком подходе вы можете решить задачу за линейное время, т. Е. O (N). Я сделал это на Python, представил свое решение и прошел все тесты.

Однако легко создать набор данных, для которого центроидный подход не работает. Вот пример:

[(0, 0), (0, 1), (0, 2), (0, 3), 
 (1, 0), (1, 1), (1, 2), (1, 3), 
 (2, 0), (2, 1), (2, 2), (2, 3), 
 (3, 0), (3, 1), (3, 2), (3, 3), 
 (101, 101)]

Лучшее решение - это встреча в доме по адресу (2, 2), а стоимость 121 (это можно найти с помощью исчерпывающего поиска - O (N ^ 2)). Однако центроидный подход дает другой результат:

• Центр тяжести (7, 7)
• Ближайший дом к центроиду (3, 3)
• стоимость встречи в (3, 3) составляет 132

Контрольные примеры на веб-сайте, очевидно, имеют такую ​​форму, что решение для центроида в порядке, или, возможно, они просто хотели выяснить, знаете ли вы о понятии центроида.

Answer 2

Я не читал ваш код, но рассмотрим следующий пример:

• 2 парня живут в (0, 0)
• 1 парень живет в (2, 0)
• 4 парня живут в (3, 0)

Центр тяжести находится в точке (2, 0), с минимальным общим временем в пути 8, но оптимальное решение находится в точке (3, 0) с минимальным общим временем в пути 7.

Answer 3

Здравствуйте и спасибо вам за ваши ответы и комментарии, они были очень полезны. Я, наконец, отказался от своего алгоритма, использующего центр тяжести, когда я провел по нему несколько образцов, я заметил, что, когда дома собираются в разных деревнях с разным расстоянием между ними, алгоритм не работает. Если мы рассмотрим пример, который @Rostor указал выше:

(0,0), (1,0), (2000,0), (3000,0), (3001,0), (3002, 0), (3003, 0)

Алгоритм, использующий центр тяжести, отвечает, что 3-й дом - это решение, но правильный ответ - 4-й дом. Правильным понятием для использования в таких задачах является медиана, и адаптировать его к нужным измерениям. Вот отличная статья, в которой говорится о Геометрическая медиана , надеюсь, это поможет.

Answer 4

РЕШЕНИЕ:

1. если все точки на одной линии и люди могут двигаться только в 2 направлениях (слева и справа)

   сортирует точки и вычисляет два массива: один, если они движутся только влево, и другой, если они движутся только вправо. добавьте оба вектора и найдите минимум, чтобы найти решение

2. если люди могут перемещаться только в 4 направлениях (влево, вниз, вверх, вправо), вы можете применять одно и то же правило, все, что вам нужно для поддержки, - это когда вы сортируете по одной оси, вы должны иметь возможность вернуться назад, поэтому, когда сортировка вы также должны сохранить сортировки перестановок

3. если люди могут двигаться в 8 направлениях (как в вопросе), вы можете использовать тот же алгоритм, что и в 4 направлениях (2. алгоритм), поскольку, если вы правильно наблюдаете движения, вы можете видеть, что можно сделать одинаковое количество ходов, если все движутся только по диагонали, и им не нужно двигаться влево, вправо вверх и вниз, но только влево-вверх, вверх-вправо, влево-вниз и вниз-вправо, если для каждой точки (x, y ) считает, что (x + y)% 2 == 0 - представьте, что сетка - шахматная доска, а дома только на черных квадратах

   Перед применением 2. algorhitm вы должны сделать трансформацию точек так

   (x, y) становится (x + y, x-y) - это повороты точек на 45 градусов. Затем вы применяете 2. алгоритм и делите результат на 2.

Answer 5

Я даже пытался, но получил только 4 из 13 тестовых случаев. ошибка сегментации, что они говорят.

, но я сделал два массива по 100001 каждый и несколько переменных m, используя.

Мой алгоритм.

найти центр тяжести заданных точек.

найти точку, ближайшую к центроиду. получить сумму всех расстояний, используя максимум (abs (a-A), abs (b-B)).

Answer 6

Это то, что я сделал

def abs(a)
  (a < 0) ? -a : a
end

# Calculate distance between cell(i) to cell(j)
#
# a and b are point structures each having x, y co-ordinate
def dist(a, b)

  if ((a[0] == b[0]) && (a[1] == b[1]))
    return 0
  end

  del_row = abs(a[0] - b[0])
  del_col = abs(a[1] - b[1])

  if (del_row == del_col)
    return del_row
  else
    return del_row > del_col ? del_row : del_col
  end

end

# Find the median cell from an array of cells
def find_median(array)

  # If array is of even length, the median element is not in the array. We've to consider
  # two adjacent elements of the median. For odd case we've just one median

  n = array.length

  # Median finding can be done at O(n)...
  #
  # Sort cell array - O(nlogn)
  array = array.sort do |cell1, cell2|

          # Try first by comparing x
          if (cell1[0] != cell2[0])
            cell1[0] < cell2[0] ? -1 : 1
          else
            # Resolve tie by comparing y
            cell1[1] <=> cell2[1]
          end

  end

  # Find median
  k = n / 2
  median_element = []
  if ((n % 2) == 0)
    median_element << array[k]
    median_element << array[k+1]
  else
    median_element << array[k]
  end

  median_element
end

# Calculate travel time given an array of cells and a cell indicating the meeting point
def calculate_travel_time(array, meeting_cell)

  travel_time = 0
  array.each do |cell|

    # Skip the meeting cell itself
    if (!((cell[0] == meeting_cell[0]) && (cell[1] == meeting_cell[1])))
      travel_time = travel_time + dist(cell, meeting_cell)
    end

  end

  travel_time

end

def figure_out_the_meeting_point(array)

  if (array.nil?)
    return 0
  end

  n = array.length
  if (n == 0)
    return 0
  end

  if (n == 1)
    # Lonely person
    return 0
  end

  if (n == 2)
    # Just two neighbors
    return dist(array[0], array[1])
  end

  # Find median
  median = find_median(array)
  median_length = median.length
  min_travel_time = 0
  meeting_point = nil
  if (median_length == 1)

    min_travel_time = calculate_travel_time(array, median[0])
    meeting_point = median[0]

  else

    # We've two candidates. Need to check minimum of them
    t_first_median = calculate_travel_time(array, median[0])
    t_second_median = calculate_travel_time(array, median[1])
    if (t_first_median < t_second_median)
      min_travel_time = t_first_median
      meeting_point = median[0]
    else
      min_travel_time = t_second_median
      meeting_point = median[1]
    end

  end

  return min_travel_time, meeting_point

end

# Handle STDIN and STDOUT for I/O
def handle_io()

  STDOUT.flush
  n = gets.to_i
  array = []
  (n).times do
    STDOUT.flush
    s = gets
    array << s.split(' ').map(&:to_i)
  end

  array
end

tt, mp = figure_out_the_meeting_point(handle_io)
puts tt
puts mp

Сетка бесконечна. Следовательно, решение должно быть целочисленным, безопасным при переполнении. Я проверил с огромными целочисленными значениями, и Ruby правильно конвертирует их в BigNum, как и ожидалось.

Любая идея, почему я НЕ прохожу все тестовые случаи.

Answer 7

Я пытался решить это, используя метод геометрической медианы. Но только 11 из 13 тестов прошли. Это была моя стратегия.

1. finding centroid of a set of points.
2. then found the point closest to that centroid.

Answer 8

Я написал быстрый и грязный тестер расстояния по сетке в scala, который сравнивает среднее значение с минимумом исчерпывающего поиска:

class Coord (val x:Int, val y: Int) {
  def delta (other: Coord) = {
    val dx = math.abs (x - other.x)
    val dy = math.abs (y - other.y)
    List (dx, dy).max
  }
  override def toString = " (" + x + ":" + y + ") "
}

def run (M: Int) {
  val r = util.Random 
  // reproducable set:
  // r.setSeed (17)

  val ucells = (1 to 2 * M).map (dummy => new Coord (r.nextInt (M), r.nextInt (M))).toSet take (M) toSeq
  val cells = ucells.sortWith ((a,b) => (a.x < b.x || a.x == b.x && a.y <= b.y))

  def distanceSum (lc: Seq[Coord], cell: Coord) = lc.map (c=> cell.delta (c)).sum

  val exhaustiveSearch = for (x <- 0 to M-1;
    y <- 0 to M-1)
      yield (distanceSum (cells, new Coord (x, y)))

  def sum (lc: Seq[Coord]) = ((0,0) /: lc) ((a, b) => (a._1 + b.x, a._2 + b.y))
  def avg (lc: Seq[Coord]) = {
    val s = sum (lc) 
    val l = lc.size 
    new Coord ((s._1 + l/2) / l, (s._2 + l/2) / l)
  }
  val av = avg (ucells)
  val avgMethod = distanceSum (cells, av)

  def show (cells : Seq[Coord]) {
     val sc = cells.sortWith ((a,b) => (a.x < b.x || a.x == b.x && a.y <= b.y))
     var idx = 0
     print ("\t")
     (0 to M).foreach (i => print (" " + (i % 10))) 
     println ()
     for (x <- 0 to M-1) {
       print (x + "\t")
       for (y <- 0 to M -1) {
         if (idx < M && sc (idx).x == x && sc (idx).y == y) {
           print (" x") 
           idx += 1 }
           else if (x == av.x && y == av.y) print (" A")
           else print (" -")
       }
       println ()
     }
  }

  show (cells)
  println ("exhaustive Search: " + exhaustiveSearch.min)
  println ("avgMethod: " + avgMethod)
  exhaustiveSearch.sliding (M, M).toList.map (println)
}

Вот пример вывода:

run (10)
     0 1 2 3 4 5 6 7 8 9 0
0    - x - - - - - - - -
1    - - - - - - - - - -
2    - - - - - - - - - -
3    x - - - - - - - - -
4    - x - - - - - - - -
5    - - - - - - x - - -
6    - - - - A - - x - -
7    - x x - - - - - - -
8    - - - - - - - - - x
9    x - - - - - - - - x
exhaustive Search: 36
avgMethod: 37
Vector(62, 58, 59, 60, 62, 64, 67, 70, 73, 77)
Vector(57, 53, 50, 52, 54, 57, 60, 63, 67, 73)
Vector(53, 49, 46, 44, 47, 50, 53, 57, 63, 69)
Vector(49, 46, 43, 41, 40, 43, 47, 53, 59, 66)
Vector(48, 43, 41, 39, 37, 37, 43, 49, 56, 63)
Vector(47, 43, 39, 37, 36, 37, 39, 46, 53, 61)
Vector(48, 43, 39, 36, 37, 38, 40, 43, 51, 59)
Vector(50, 44, 40, 39, 38, 40, 42, 45, 49, 57)
Vector(52, 47, 44, 42, 42, 42, 45, 48, 51, 55)
Vector(55, 52, 49, 47, 46, 47, 48, 51, 54, 58)

Среднее значение не всегда является идеальной позицией (как показано в этом примере), но вы можете следить за соседями с более или менее значимым значением, чтобы найти лучшую позицию.Это хорошая отправная точка, и я не нашел образец локального оптимума, где вы застряли.Это может быть важно для огромных наборов данных.

Но у меня нет доказательств, всегда ли это так, и как найти идеальную позицию напрямую.

Answer 9

Если вы немного подумаете о функции расстояния, вы получите время перемещения между (x1, y1) и (x2, y2)

def dist( (x1,y1), (x2,y2)):
    dx = abs(x2-x1)
    dy = abs(y2-y1)
    return max(dx, dy)

Это можно увидеть, если сделать эскиз на бумаге с сеткой.

Таким образом, вам нужно только перебрать каждый дом, подвести итог времени в пути других и взять дом с минимальной суммой.

Полное решение:

houses = [ (7,4), (1,1), (3,2), (-3, 2), (2,7), (8, 3), (10, 9) ]

def dist( (x1, y1), (x2, y2)):
    dx = abs(x1-x2)
    dy = abs(y1-y2)
    return max(dx, dy)

def summed_time_to(p0, houses):
    return sum(dist(p0, p1) for p1 in houses)

distances = [ (summed_time_to(p, houses), i) for i, p in enumerate(houses) ]
distances.sort()

min_dist = distances[0][0]

print "best houses are:"
for d, i in distances:
    if d==min_dist:
        print i, "at", houses[i]

Answer 10

«... это чей-то дом» означает, что вы выбираете занятый дом, а не произвольное местоположение.

Редактировать : упс, макс (abs (aA), abs (bB))) заменяет (abs (aA) + abs (bB)).См. L_p space для более подробной информации, когда p-> бесконечность.

Расстояние от (a, b) до (A, B) равно max (abs (aA), abs (bB)).Метод грубой силы состоит в том, чтобы вычислить общее время в пути для встречи в каждом занятом доме, отслеживая лучшее место для встреч.

Это может занять некоторое время.Сортировка по центру масс может позволить вам расставить приоритеты в порядке поиска.Я вижу, что вы используете хороший расчет центра масс для этой метрики: для получения простого среднего значения первой координаты и простого среднего значения второго компонента.