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

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

Как всегда, два обычных отказа от ответственности:

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

Хватит болтать, приступим. Сегодняшняя проблема была задана не кем иным, как Google!

Вы находитесь в бесконечной 2D-сетке, где вы можете двигаться в любом из 8 направлений:

(x,y) to
(x+1, y),
(x - 1, y),
(x, y+1),
(x, y-1),
(x-1, y-1),
(x+1,y+1),
(x-1,y+1),
(x+1,y-1)

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

Пример:

Input: [(0, 0), (1, 1), (1, 2)]
Output: 2

Чтобы перейти от (0, 0) к (1, 1), требуется 1 шаг. Требуется еще один шаг, чтобы перейти от (1, 1) к (1, 2).

По сути, нас просят двигаться из ряда точек, вычисляя минимальные шаги, необходимые для путешествия до конечной точки. Может быть, это было собеседование на работу в такой сервис, как Google Maps? Подобные алгоритмы широко используются для картографических сервисов и подобного программного обеспечения.

Графически мы могли бы представить что-то вроде этого:

Обратите внимание, что мы не можем вычислить прямое расстояние между A и E, так как это даст нам неправильные результаты, как мы увидим позже. Нас просят пройти в каждую точку заданного набора: как и в реальном мире, мы не можем путешествовать прямо из одного места в другое, мы должны следовать по дороге! Вычисление прямого расстояния от одного места до другого было бы неправильным, так как дорога может быть вовсе не прямой.

Идя немного глубже, из одной точки нам разрешено двигаться в 8 направлениях. Для перемещения нам нужны две координаты, поэтому при каждом движении мы можем достигать четырех внешних углов вокруг этой точки и средних точек между углами. Опять же, графически:

Нам нужно свести к минимуму все расстояние перемещения и, помня, что нам нужно пройти из каждой заданной точки массива, нам нужно минимизировать перемещение между каждыми двумя точками массива.

По этой причине, поскольку я предполагаю, что статья будет довольно длинной, я решил разделить эту статью на две части:

  • В первой части мы рассмотрим два разных алгоритма минимизации перемещения из одной точки в другую. Первый — это более «грубое» решение, а второй — более быстрый способ решить проблему с небольшим количеством рассуждений.
  • Во второй части мы рассмотрим простую функцию-оболочку для перебора первой функции по всем точкам заданного массива и получения окончательного результата.

Вы готовы тогда? Давай начнем!

Часть первая: минимизация расстояния

Из школьной базовой геометрии мы знаем, что минимальное расстояние (d) между двумя точками — это просто прямая линия между ними, рассчитанная, как указано выше. Ах, старые добрые времена с Пифагором! Тогда нам нужно найти способ следовать этой прямой линии.

С помощью нашего алгоритма мы можем двигаться в каждом из восьми направлений, а это означает, что мы можем следовать по этой прямой, когда захотим. Мы можем двигаться в любом направлении, поэтому мы всегда можем построить прямую линию из точки A в точку B. И если, строя эту линию, мы не заканчиваем точно в точке B (в основном, когда наклон не равен 1), мы можем добавить дополнительные шаги, необходимые для перехода к B. Графически это будет что-то так:

Каждая желтая точка — это точка, которую нам нужно достичь, чтобы добраться до B с нашими разрешенными ходами, минимизируя расстояние. Это означает, что если мы посчитаем желтые точки, у нас будет минимальное количество шагов для путешествия из A в B.

Мы знаем, что каждая точка имеет две координаты: например, первая точка массива, назовем ее A, должна иметь две координаты, а именно x и y . Обычно для обозначения этих координат мы будем писать Ax и Ay.

С точки зрения нашего алгоритма эта прямая линия — это линия, которая на каждом шаге сокращает расстояние между x и y точки A и x и y точки B. Это означает, что на каждом шаге мы можем прибавлять или вычитать единицу к каждой из координат, чтобы стать ближе к B, чем на предыдущем шаге, и мы будем следовать прямой линии между A и B. Нам просто нужно добавить или вычесть единицу соответственно. к размерам координат:

  • Если x у A больше, чем x у B, это означает, что нам нужно вычесть из этой координаты, и наоборот.
  • Если у A больше, чем у B, это означает, что нам нужно вычесть из этой координаты, и наоборот.
  • Если x или y A равны x или y B, мы оставляем все как есть.

Вот несколько расчетов вручную, чтобы продемонстрировать это.

Давайте тогда распишем алгоритмы, хорошо? Как и предполагалось ранее, будет два алгоритма. Сначала мы рассмотрим решение грубой силы, не очень эффективное, но легкое для понимания, а затем еще немного порассуждаем о проблеме и получим решение с более эффективным алгоритмом.

Как всегда, я написал это на Python для удобочитаемости: не стесняйтесь портировать это на любой язык, который вам нравится, и поделитесь со мной своим алгоритмом!

Решение грубой силы

Вот решение «грубой силы»:

def minimumStepsBruteForce (a,b):
  newA = a
  counter = 0
  while newA != b:
    if b[0] > newA[0]:
      newA[0] += 1
    elif b[0] < newA[0]:
      newA[0] -= 1
    if b[1] > newA[1]:
      newA[1] += 1
    elif b[1] < newA[1]:
      newA[1] -= 1
    counter += 1
  
  return counter

Однажды создал функцию minimumStepsBruteForce , которая принимает две точки aи b(два списка или кортежа в виде a[x,y] и b[x,y]) , мы сначала создаем:

  • newA , новая пара координат x,y для отслеживания точки, которую мы достигли во время нашего путешествия из a в b.
  • counter , который является просто счетчиком для отслеживания наших ходов.

После этого мы создаем цикл while, который выполняется до тех пор, пока наше newA не станет отличным от b: в этот момент, конечно, мы достигли конца. Теперь мы продолжаем двигаться к b, добавляя и вычитая единицы, чтобы сократить расстояние, как на предыдущем рисунке. Чтобы было ясно, здесь newA[0] — это наши newA[x], а newA[1] — это наши newA[y]. Та же концепция для b, где b[0] равно b[x], а b[1] равно b[y] .

Естественно, мы обновляем newA с нашими вычислениями на каждом шаге, чтобы проследить, где мы находимся, и мы также обновляем counter на каждом шаге.

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

Временная сложность

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

Второе решение: построение треугольников

Давайте еще раз подумаем об этом изображении, таком же, как и в предыдущем решении:

По сути, в этом примере на каждом шаге мы:

  • продвижение вверх на один
  • двигаться вправо на один

Тогда в конце алгоритма мы будем двигаться вверх на сумму движений вверх и будем двигаться вправо на сумму движений вправо. В этом же примере мы двигаемся вверх 4 раза, а это означает, что общее расстояние в направлении «вверх» будет равно 4. В то же время мы также двигаемся вправо 5 раз, в «право» пройденное расстояние в сумме составит 5 Графически мы можем переставить ходы так, чтобы они образовали треугольник с прямой линией в качестве гипотенузы, а наши ходы — в качестве двух других сторон треугольника. Что-то вроде этого:

Обратите внимание, что созданные двусторонние — это просто расстояние от точки A до точки b для каждой координаты. Конкретно:

Естественно, расстояние между B(x) и A(x) будет равно тому, сколько шагов нам нужно сделать по этой координате, а расстояние между B(y) и A(y) будет тем, сколько шагов нам нужно сделать по этой координате. та координата.

Теперь мы знаем, что для каждого движения «вверх» мы также делаем «правильное» движение, часть от последнего «правильного» движения до точки В.

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

Это может быть сложно понять, но этот пример должен помочь вам:

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

Давайте закодируем это!

def minimumStepsbyTwo (a,b):
    diffX = a[0]-b[0] if a[0] > b[0] else b[0] - a[0]
    diffY = a[1]-b[1] if a[1] > b[1] else b[1] - a[1]
    if diffX > diffY:
        return diffX
    else:
        return diffY

Это намного короче, чем грубая сила! Пойдем разбирать.

Функция minimumStepsbyTwo принимает те же два параметра, что и раньше, a и b, которые являются нашей начальной и конечной точками. После этого создаем две переменные:

  • diffX , который будет содержать расстояние от A(x) и B(x). Естественно, поскольку расстояние должно быть целым числом, мы сначала оцениваем, какое из значений больше между A(x) и B(x), а затем вычитаем другое. Чтобы связать это с уравнением выше, это часть max(Ax,Bx) — min(Ax,Bx).
  • diffY , который будет содержать расстояние от A(y) и B(y). Опять же, мы должны получить положительное целое число, поэтому мы сначала должны оценить, какое из них больше, а затем вычесть из него другое. Чтобы связать это с уравнением выше, это часть max(Ay,By)-min(Ay,By).

После этого мы просто возвращаем наибольшую из двух разностей, возвращая diffX, если обнаруживаем, что max(Ax,Bx) — min(Ax,Bx)больше, чем max(Ay,By )-min(Ay,By),и diffY в противном случае.

Это применение полного уравнения выше:

max [max(Ax,Bx) — min(Ax,Bx) , max(Ay,By) — min(Ay,By)]

Если мы выполним два алгоритма вместе, мы увидим, что решение одно и то же:

print("This is the b.f. solution",minimumStepsBruteForce([3,4], [8,8]))
print("This is the other solution",minimumStepsbyTwo([3,4], [8,8]))
>>> This is the b.f. solution 5
>>> This is the other solution 5

Временная сложность

Давайте задумаемся на секунду о предыдущем примере (3.3). Если мы сравним два метода, то сразу заметим кое-что: в то время как первый метод, «грубая сила», выполняется за время O(n), второй для обоих примеров выполняет 3 шага. Это связано с тем, что в то время как первый должен пройти каждый шаг процесса, со вторым нам просто нужно рассчитать 3 вещи:

  • А(х),В(х) расстояние
  • A(y),B(y) расстояние
  • Максимальное значение между первыми двумя.

Это означает, что второй алгоритм работает за постоянное время, независимо от входных точек и расстояния до них. Этот алгоритм гораздо более эффективен, чем предыдущий, работает за время O(1).

Часть вторая: Оборачиваем все вместе

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

def minimumDistance(arrayOfPoints):
    
    initialPoint = arrayOfPoints[0]
    partialResult = 0
    for nextPoint in arrayOfPoints[1:]:
        partialResult += minimumStepsbyTwo(initialPoint,nextPoint)
        initialPoint = nextPoint
    
    return partialResult

Мы определяем функциюminimumDistance, которая принимает arrayOfPoints в качестве аргумента. После этого мы определяем две переменные:

  • initialPoint , который изначально будет отправной точкой нашего путешествия и будет обновляться в каждой точке нашего путешествия.
  • partialResult , который будет содержать количество шагов до этой точки.

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

После этого мы просто возвращаем partialResult , что в конце будет равно шагам, необходимым для всего пути.

Теперь мы можем проверить наше решение с точками, указанными в задаче, в качестве примера, и посмотреть, получим ли мы тот же результат:

>>> print("Total steps needed for the travel:",minimumDistance([[0,0],[1,1],[1,2]]))
Total steps needed for the travel: 2

Временная сложность

Помимо создания переменных и применения нашей функции, которая выполняется за O(1), единственное, на что здесь стоит обратить внимание, — это цикл for, который выполняется за время O(n) в зависимости от размера массива, который мы предоставляем функции. Это означает, что этот алгоритм выполняется за комплексное время O(n) линейно в зависимости от количества предоставленных точек.

Это конец! Это было долгое… путешествие, не так ли? 😄

Я очень надеюсь, что вам понравилась статья: если да, пожалуйста, поставьте лайк или поделитесь статьей с тем, кому это может быть полезно. Кроме того, если вы интересуетесь алгоритмами и программированием, следите за блогом: я публикую такие материалы, когда могу!

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

И, как всегда, спасибо за чтение.

Никола