Ну, вот решение для, возможно, самого простого способа, которым я мог бы интерпретировать ваш вопрос:
Предположим, что для каждого элемента мы рассматриваем две возможности:
Мы помещаем его в его предполагаемом месте (то есть в центр интервала)
Мы не
Тогда мы можем переформулировать этоЗадача в виде следующей функции: Найти максимальный набор элементов, которые можно поместить в центр их интервала без наложения.
Это похоже на то, что должно иметь жадное решение, но я должен признаться, что лучшийЯ смог сделать довольно наивный алгоритм динамического программирования.Вот как я сформулировал повторение:
Предположим, что мы рассматриваем n-й элемент (начиная с левого), и что мы хотим назначить его таким образом, чтобы левый край этого элемента не проходил наиболее правоеперед всеми предыдущими пунктами.Тогда должно быть верно, что оптимальное присвоение удовлетворяет:
best_align(n, right) =
if center[n]-radius[n] > right[n]:
max(best_align(n+1, right+radii[n], 1+best_align(n+1,center[n]+radius[n])
else:
best_align(n+1, right+radius[n])
Это имеет очевидное решение DP, которое я кодировал (в python).Вот результат:
#Assumes that the items are sorted left-to-right by their centers
def best_align(radii, centers):
assignments = { (radii[0]+centers[0]):[0], (-100000):[] }
for i in range(1, len(radii)):
nc = centers[i] + radii[i]
nassignments = { nc : [i] }
for right, assigned in assignments.items():
#Handle case where object is not inserted
nr = right+radii[i]
if not nr in nassignments or len(assigned) > len(nassignments[nr]):
nassignments[nr] = assigned
#Handle inclusion case
if right <= centers[i]-radii[i] and len(assigned) >= len(nassignments[nc]):
nassignments[nc] = assigned + [i]
assignments = nassignments
return max([ (len(l), l) for l in assignments.values() ])[1]
Переменные радиусы - это радиусы различных предметов, а центры - это целевые позиции назначения.Алгоритм возвращает наибольшее подмножество элементов, которые могут быть размещены в желаемых позициях.Остальные предметы должны быть вычеркнуты как можно лучше.Например, вот несколько выходных данных:
In [11]: plc.best_align ([1, 5, 1], [0, 2, 3])
Out [11]: [2]
Другой пример:
В [18]: plc.best_align ([1, 10, 1, 1, 1, 1, 1], [0, 2, 4, 6, 8, 10, 12])
Out [18]: [2, 3, 4, 5, 6]
Theвременная сложность этой реализации является кубической из-за наивного способа обработки наборов назначений.Можно легко оптимизировать, чтобы получить квадратичное решение, заменив списки python ссылками на предыдущие списки, из которых они были построены (хотя это сделает презентацию более скверной).