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

Ответ 1

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

(300), (300), (300, 0), (3003, 0)

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

Ответ 2

Ключом к этой проблеме является понятие центроида набора точек. Место встречи - это самый близкий дом для центра тяжести для множества точек, представляющих все дома. При таком подходе вы можете решить проблему в линейном времени, т.е. 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)). Однако подход с центроидом дает другой результат:

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

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

Ответ 3

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

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

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

Ответ 4

РЕШЕНИЕ:

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

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

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

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

  Перед тем, как применить 2. algorhitm, вы должны сделать такт tranformation, чтобы

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

Ответ 5

"... кто-то дом" означает, что вы выбираете занятый дом, а не произвольное место.

Изменить: oops, max (abs (a-A), abs (b-B)) заменяет (abs (a-A) + abs (b-B)). См. L_p space для получения более подробной информации, когда p- > infinty.

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

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

Ответ 6

Если вы немного подумаете о функции расстояния, которую вы получаете как время прохождения между (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]

Ответ 7

Я написал быстрый и грязный тестер сетки в 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)

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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

Ответ 10

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

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

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

найти центроид данных точек.

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