Алгоритм нахождения всех точек на расстоянии от другой точки
У меня была эта проблема для вступительного испытания на работу. Я не прошел тест. Я замаскирую вопрос в почтении к компании.
Представьте, что у вас есть N людей в парке A X B. Если у человека нет другого человека в пределах 50 футов, он наслаждается его конфиденциальностью. В противном случае его личное пространство нарушается. Учитывая набор (x, y), скольким людям будет нарушено их пространство?
Например, приведите этот список в Python:
человек = [(0,0), (1,1), (1000, 1000)]
Мы нашли бы 2 человек, у которых нарушено их пространство: 1, 2.
Нам не нужно находить все группы людей; просто общее количество уникальных людей.
Вы не можете использовать грубый метод для решения проблемы. Другими словами, вы не можете использовать простой массив внутри массива.
Я работал над этой проблемой время от времени в течение нескольких недель, и, хотя я получил решение быстрее, чем n^2, я не нашел проблему, которая масштабируется.
Я думаю, что единственный правильный способ решить эту проблему - использовать алгоритм Fortune?
Вот что я имею в Python (не используя алгоритм Fortune):
import math
import random
random.seed(1) # Setting random number generator seed for repeatability
TEST = True
NUM_PEOPLE = 10000
PARK_SIZE = 128000 # Meters.
CONFLICT_RADIUS = 500 # Meters.
def _get_distance(x1, y1, x2, y2):
"""
require: x1, y1, x2, y2: all integers
return: a distance as a float
"""
distance = math.sqrt(math.pow((x1 - x2), 2) + math.pow((y1 - y2),2))
return distance
def check_real_distance(people1, people2, conflict_radius):
"""
determine if two people are too close
"""
if people2[1] - people1[1] > conflict_radius:
return False
d = _get_distance(people1[0], people1[1], people2[0], people2[1])
if d >= conflict_radius:
return False
return True
def check_for_conflicts(peoples, conflict_radius):
# sort people
def sort_func1(the_tuple):
return the_tuple[0]
_peoples = []
index = 0
for people in peoples:
_peoples.append((people[0], people[1], index))
index += 1
peoples = _peoples
peoples = sorted(peoples, key = sort_func1)
conflicts_dict = {}
i = 0
# use a type of sweep strategy
while i < len(peoples) - 1:
x_len = peoples[i + 1][0] - peoples[i][0]
conflict = False
conflicts_list =[peoples[i]]
j = i + 1
while x_len <= conflict_radius and j < len(peoples):
x_len = peoples[j][0] - peoples[i][0]
conflict = check_real_distance(peoples[i], peoples[j], conflict_radius)
if conflict:
people1 = peoples[i][2]
people2 = peoples[j][2]
conflicts_dict[people1] = True
conflicts_dict[people2] = True
j += 1
i += 1
return len(conflicts_dict.keys())
def gen_coord():
return int(random.random() * PARK_SIZE)
if __name__ == '__main__':
people_positions = [[gen_coord(), gen_coord()] for i in range(NUM_PEOPLE)]
conflicts = check_for_conflicts(people_positions, CONFLICT_RADIUS)
print("people in conflict: {}".format(conflicts))
5 ответов
Как видно из комментариев, есть много подходов к этой проблеме. В ситуации интервью вы, вероятно, захотите перечислить как можно больше и сказать, в чем сильные и слабые стороны каждого из них.
Для указанной выше задачи, когда у вас есть фиксированный радиус, простейшим подходом, вероятно, является округление и хеширование. Деревья kd и тому подобное являются мощными структурами данных, но они также довольно сложны, и если вам не нужно многократно запрашивать их, добавлять или удалять объекты, они могут быть излишними для этого. Хеширование может достигать линейного времени по сравнению с пространственными деревьями, которые являются n log n, хотя это может зависеть от распределения точек.
Чтобы понять хеширование и округление, просто подумайте о том, как разделить свое пространство на сетку квадратов со сторонами длины, равными радиусу, который вы хотите проверить. Каждому квадрату присваивается свой собственный "почтовый индекс", который вы можете использовать в качестве хэш-ключа для хранения значений в этом квадрате. Вы можете вычислить почтовый индекс точки, разделив координаты x и y на радиус и округлив, как показано ниже:
def get_zip_code(x, y, radius):
return str(int(math.floor(x/radius))) + "_" + str(int(math.floor(y/radius)))
Я использую строки, потому что это просто, но вы можете использовать что угодно, если вы генерируете уникальный почтовый индекс для каждого квадрата.
Создайте словарь, где ключи - это почтовые индексы, а значения - списки всех людей в этом почтовом индексе. Чтобы проверить наличие конфликтов, добавляйте пользователей по одному, а перед добавлением каждого проверяйте наличие конфликтов со всеми людьми в одном и том же почтовом индексе и 8 соседями почтового индекса. Я повторно использовал ваш метод для отслеживания конфликтов:
def check_for_conflicts(peoples, conflict_radius):
index = 0
d = {}
conflicts_dict = {}
for person in peoples:
# check for conflicts with people in this person's zip code
# and neighbouring zip codes:
for offset_x in range(-1, 2):
for offset_y in range(-1, 2):
offset_zip_code = get_zip_code(person[0] + (offset_x * conflict_radius), person[1] + (offset_y * conflict_radius), conflict_radius)
if offset_zip_code in d:
# get a list of people in this zip:
other_people = d[offset_zip_code]
# check for conflicts with each of them:
for other_person in other_people:
conflict = check_real_distance(person, other_person, conflict_radius)
if conflict:
people1 = index
people2 = other_person[2]
conflicts_dict[people1] = True
conflicts_dict[people2] = True
# add the new person to their zip code
zip_code = get_zip_code(person[0], person[1], conflict_radius)
if not zip_code in d:
d[zip_code] = []
d[zip_code].append([person[0], person[1], index])
index += 1
return len(conflicts_dict.keys())
Временная сложность этого зависит от нескольких вещей. Если вы увеличите количество людей, но не увеличите размер пространства, в котором вы их распределяете, то это будет O (N2), потому что число конфликтов будет увеличиваться квадратично, и вам придется подсчитывать их все, Однако, если вы увеличите пространство вместе с количеством людей, чтобы плотность была одинаковой, она будет ближе к O(N).
Если вы просто подсчитываете уникальных людей, вы можете вести подсчет, если у скольких людей в каждом почтовом индексе есть хотя бы 1 конфликт. Если он равен всем в почтовом индексе, вы можете рано выйти из цикла, который проверяет наличие конфликтов в данном почтовом индексе после первого конфликта с новым человеком, так как больше не будет найдено ни одного уникального файла. Вы также можете выполнить цикл дважды, добавив всех людей в первом цикле и протестировав во втором, прерывая цикл, когда вы обнаружите первый конфликт для каждого человека.
Я придумываю ответ, который, кажется, занимает O(N) время. Стратегия состоит в том, чтобы отсортировать массив по значениям X. Для каждого значения X проведите влево до тех пор, пока не будет обнаружен конфликт или расстояние не превысит конфликтное расстояние (500 м). Если конфликт не обнаружен, разверните влево таким же образом. С помощью этой техники вы ограничиваете объем поиска.
Вот код:
import math
import random
random.seed(1) # Setting random number generator seed for repeatability
NUM_PEOPLE = 10000
PARK_SIZE = 128000 # Meters.
CONFLICT_RADIUS = 500 # Meters.
check_real_distance = lambda conflict_radius, people1, people2: people2[1] - people1[1] <= conflict_radius \
and math.pow(people1[0] - people2[0], 2) + math.pow(people1[1] - people2[1], 2) <= math.pow(conflict_radius, 2)
def check_for_conflicts(peoples, conflict_radius):
peoples.sort(key = lambda x: x[0])
conflicts_dict = {}
i = 0
num_checks = 0
# use a type of sweep strategy
while i < len(peoples) :
conflict = False
j = i + 1
#sweep right
while j < len(peoples) and peoples[j][0] - peoples[i][0] <= conflict_radius \
and not conflict and not conflicts_dict.get(i):
num_checks += 1
conflict = check_real_distance(conflict_radius, peoples[i], peoples[j])
if conflict:
conflicts_dict[i] = True
conflicts_dict[j] = True
j += 1
j = i - 1
#sweep left
while j >= 0 and peoples[i][0] - peoples[j][0] <= conflict_radius \
and not conflict and not conflicts_dict.get(i):
num_checks += 1
conflict = check_real_distance(conflict_radius, peoples[j], peoples[i])
if conflict:
conflicts_dict[i] = True
conflicts_dict[j] = True
j -= 1
i += 1
print("num checks is {0}".format(num_checks))
print("num checks per size is is {0}".format(num_checks/ NUM_PEOPLE))
return len(conflicts_dict.keys())
def gen_coord():
return int(random.random() * PARK_SIZE)
if __name__ == '__main__':
people_positions = [[gen_coord(), gen_coord()] for i in range(NUM_PEOPLE)]
conflicts = check_for_conflicts(people_positions, CONFLICT_RADIUS)
print("people in conflict: {}".format(conflicts))
Я нашел относительно решение проблемы. Сортировать список координат по значению X Затем посмотрите на каждое значение X, по одному за раз. Поверните направо, проверяя положение со следующей позицией, пока не будет достигнут конец области развертки (500 метров) или не будет обнаружен конфликт.
Если конфликт не обнаружен, разверните влево таким же образом. Этот метод позволяет избежать ненужных проверок. Например, если в парке 1000000 человек, то все они будут в конфликте. Алгоритм будет проверять каждого человека только один раз: после обнаружения конфликта поиск прекращается.
Мое время, кажется, O(N).
Вот код:
import math
import random
random.seed(1) # Setting random number generator seed for repeatability
NUM_PEOPLE = 10000
PARK_SIZE = 128000 # Meters.
CONFLICT_RADIUS = 500 # Meters.
check_real_distance = lambda conflict_radius, people1, people2: people2[1] - people1[1] <= conflict_radius \
and math.pow(people1[0] - people2[0], 2) + math.pow(people1[1] - people2[1], 2) <= math.pow(conflict_radius, 2)
def check_for_conflicts(peoples, conflict_radius):
peoples.sort(key = lambda x: x[0])
conflicts_dict = {}
i = 0
num_checks = 0
# use a type of sweep strategy
while i < len(peoples) :
conflict = False
j = i + 1
#sweep right
while j < len(peoples) and peoples[j][0] - peoples[i][0] <= conflict_radius \
and not conflict and not conflicts_dict.get(i):
num_checks += 1
conflict = check_real_distance(conflict_radius, peoples[i], peoples[j])
if conflict:
conflicts_dict[i] = True
conflicts_dict[j] = True
j += 1
j = i - 1
#sweep left
while j >= 0 and peoples[i][0] - peoples[j][0] <= conflict_radius \
and not conflict and not conflicts_dict.get(i):
num_checks += 1
conflict = check_real_distance(conflict_radius, peoples[j], peoples[i])
if conflict:
conflicts_dict[i] = True
conflicts_dict[j] = True
j -= 1
i += 1
print("num checks is {0}".format(num_checks))
print("num checks per size is is {0}".format(num_checks/ NUM_PEOPLE))
return len(conflicts_dict.keys())
def gen_coord():
return int(random.random() * PARK_SIZE)
if __name__ == '__main__':
people_positions = [[gen_coord(), gen_coord()] for i in range(NUM_PEOPLE)]
conflicts = check_for_conflicts(people_positions, CONFLICT_RADIUS)
print("people in conflict: {}".format(conflicts))
Вы можете увидеть эту ссылку topcoder и раздел "Ближайшая пара". Вы можете изменить алгоритм ближайшей пары так, чтобы расстояние h всегда составляло 50.
Итак, что вы в основном делаете,
- Сортировать людей по координате X
- Размах слева направо.
- Сохраняйте сбалансированное двоичное дерево и сохраняйте все точки в пределах 50 радиусов в двоичном дереве. Ключ двоичного дерева будет координатами Y точки
- Выберите точки с Y-50 и Y+50, это можно сделать с помощью двоичного дерева за время lg(n).
- Таким образом, общая сложность становится n lg(n)
- Обязательно отметьте найденные вами точки, чтобы пропустить эти точки в будущем.
Вы можете использовать set в C++ как двоичное дерево. Но я не смог найти, поддерживает ли python set запрос диапазона или upper_bound и lower_bound. Если кто-то знает, пожалуйста, укажите это в комментариях.
Вот мое решение этой интересной проблемы:
from math import sqrt
import math
import random
class Person():
def __init__(self, x, y, conflict_radius=500):
self.position = [x, y]
self.valid = True
self.radius = conflict_radius**2
def validate_people(self, people):
P0 = self.position
for p in reversed(people):
P1 = p.position
dx = P1[0] - P0[0]
dy = P1[1] - P0[1]
dx2 = (dx * dx)
if dx2 > self.radius:
break
dy2 = (dy * dy)
d = dx2 + dy2
if d <= self.radius:
self.valid = False
p.valid = False
def __str__(self):
p = self.position
return "{0}:{1} - {2}".format(p[0], p[1], self.valid)
class Park():
def __init__(self, num_people=10000, park_size=128000):
random.seed(1)
self.num_people = num_people
self.park_size = park_size
def gen_coord(self):
return int(random.random() * self.park_size)
def generate(self):
return [[self.gen_coord(), self.gen_coord()] for i in range(self.num_people)]
def naive_solution(data):
sorted_data = sorted(data, key=lambda x: x[0])
len_sorted_data = len(sorted_data)
result = []
for index, pos in enumerate(sorted_data):
print "{0}/{1} - {2}".format(index, len_sorted_data, len(result))
p = Person(pos[0], pos[1])
p.validate_people(result)
result.append(p)
return result
if __name__ == '__main__':
people_positions = Park().generate()
with_conflicts = len(filter(lambda x: x.valid, naive_solution(people_positions)))
without_conflicts = len(filter(lambda x: not x.valid, naive_solution(people_positions)))
print("people with conflicts: {}".format(with_conflicts))
print("people without conflicts: {}".format(without_conflicts))
Я уверен, что код еще можно оптимизировать