Алгоритм поиска самых длинных непересекающихся последовательностей
Я пытаюсь найти лучший способ решить следующую проблему. Лучше всего я имею в виду менее сложный.
В качестве входных данных список кортежей (начало, длина) такой:
[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]
Каждый элемент представляет последовательность по ее началу и длине, например (5,7) эквивалентно последовательности (5,6,7,8,9,10,11) - список из 7 элементов, начиная с 5. Можно предположить, что кортежи отсортированы по start элемент.
Выходные данные должны возвращать неперекрывающуюся комбинацию кортежей, которые представляют самые длинные непрерывные последовательности. Это означает, что решение представляет собой подмножество диапазонов без наложений и пропусков и является самым длинным из возможных - хотя их может быть несколько.
Например, для данного ввода решение:
[(0,5),(5,7)] эквивалентно (0,1,2,3,4,5,6,7,8,9,10,11)
Откат назад лучший подход для решения этой проблемы?
Мне интересны любые подходы, которые люди могут предложить.
Также, если кто-то знает официальную ссылку на эту проблему или другую похожую, я хотел бы получить ссылки.
Кстати - это не домашняя работа.
редактировать
Просто чтобы избежать ошибок, это еще один пример ожидаемого поведения
для входа, как [(0,1),(1,7),(3,20),(8,5)] правильный ответ [(3,20)] эквивалентно (3,4,5,..,22) длиной 20. Некоторые из полученных ответов дадут [(0,1),(1,7),(8,5)] эквивалентно (0,1,2,...,11,12) в качестве правильного ответа. Но этот последний ответ не является правильным, потому что короче [(3,20)],
9 ответов
Выполните итерацию по списку кортежей, используя заданный порядок (по элементу start), при этом используя хэш-карту для отслеживания длины самой длинной непрерывной последовательности, заканчивающейся на определенном индексе.
псевдокод, пропуская детали, такие как элементы, не найденные в хэш-карте (предположим, 0 возвращается, если не найден):
int bestEnd = 0;
hashmap<int,int> seq // seq[key] = length of the longest sequence ending on key-1, or 0 if not found
foreach (tuple in orderedTuples) {
int seqLength = seq[tuple.start] + tuple.length
int tupleEnd = tuple.start+tuple.length;
seq[tupleEnd] = max(seq[tupleEnd], seqLength)
if (seqLength > seq[bestEnd]) bestEnd = tupleEnd
}
return new tuple(bestEnd-seq[bestEnd], seq[bestEnd])
Это алгоритм O(N).
Если вам нужны фактические кортежи, составляющие эту последовательность, вам нужно будет также сохранить связанный список кортежей, хэшированный по конечному индексу, обновляя его всякий раз, когда максимальная длина обновляется для этой конечной точки.
ОБНОВЛЕНИЕ: Мои знания Python довольно ограничены, но на основе вставленного вами кода Python я создал этот код, который возвращает фактическую последовательность, а не только длину:
def get_longest(arr):
bestEnd = 0;
seqLengths = dict() #seqLengths[key] = length of the longest sequence ending on key-1, or 0 if not found
seqTuples = dict() #seqTuples[key] = the last tuple used in this longest sequence
for t in arr:
seqLength = seqLengths.get(t[0],0) + t[1]
tupleEnd = t[0] + t[1]
if (seqLength > seqLengths.get(tupleEnd,0)):
seqLengths[tupleEnd] = seqLength
seqTuples[tupleEnd] = t
if seqLength > seqLengths.get(bestEnd,0):
bestEnd = tupleEnd
longestSeq = []
while (bestEnd in seqTuples):
longestSeq.append(seqTuples[bestEnd])
bestEnd -= seqTuples[bestEnd][1]
longestSeq.reverse()
return longestSeq
if __name__ == "__main__":
a = [(0,3),(1,4),(1,1),(1,8),(5,2),(5,5),(5,6),(10,2)]
print(get_longest(a))
Пересмотренный алгоритм:
create a hashtable of start->list of tuples that start there
put all tuples in a queue of tupleSets
set the longestTupleSet to the first tuple
while the queue is not empty
take tupleSet from the queue
if any tuples start where the tupleSet ends
foreach tuple that starts where the tupleSet ends
enqueue new tupleSet of tupleSet + tuple
continue
if tupleSet is longer than longestTupleSet
replace longestTupleSet with tupleSet
return longestTupleSet
реализация C#
public static IList<Pair<int, int>> FindLongestNonOverlappingRangeSet(IList<Pair<int, int>> input)
{
var rangeStarts = input.ToLookup(x => x.First, x => x);
var adjacentTuples = new Queue<List<Pair<int, int>>>(
input.Select(x => new List<Pair<int, int>>
{
x
}));
var longest = new List<Pair<int, int>>
{
input[0]
};
int longestLength = input[0].Second - input[0].First;
while (adjacentTuples.Count > 0)
{
var tupleSet = adjacentTuples.Dequeue();
var last = tupleSet.Last();
int end = last.First + last.Second;
var sameStart = rangeStarts[end];
if (sameStart.Any())
{
foreach (var nextTuple in sameStart)
{
adjacentTuples.Enqueue(tupleSet.Concat(new[] { nextTuple }).ToList());
}
continue;
}
int length = end - tupleSet.First().First;
if (length > longestLength)
{
longestLength = length;
longest = tupleSet;
}
}
return longest;
}
Тесты:
[Test]
public void Given_the_first_problem_sample()
{
var input = new[]
{
new Pair<int, int>(0, 5),
new Pair<int, int>(0, 1),
new Pair<int, int>(1, 9),
new Pair<int, int>(5, 5),
new Pair<int, int>(5, 7),
new Pair<int, int>(10, 1)
};
var result = FindLongestNonOverlappingRangeSet(input);
result.Count.ShouldBeEqualTo(2);
result.First().ShouldBeSameInstanceAs(input[0]);
result.Last().ShouldBeSameInstanceAs(input[4]);
}
[Test]
public void Given_the_second_problem_sample()
{
var input = new[]
{
new Pair<int, int>(0, 1),
new Pair<int, int>(1, 7),
new Pair<int, int>(3, 20),
new Pair<int, int>(8, 5)
};
var result = FindLongestNonOverlappingRangeSet(input);
result.Count.ShouldBeEqualTo(1);
result.First().ShouldBeSameInstanceAs(input[2]);
}
Это частный случай задачи с самым длинным путем для взвешенных направленных ациклических графов.
Узлы на графике являются начальными точками и точками после последнего элемента в последовательности, где может начинаться следующая последовательность.
Проблема особенная, потому что расстояние между двумя узлами должно быть одинаковым независимо от пути.
Это простая операция сокращения. Учитывая пару последовательных кортежей, они могут или не могут быть объединены. Итак, определите функцию парной комбинации:
def combo(first,second):
if first[0]+first[1] == second[0]:
return [(first[0],first[1]+second[1])]
else:
return [first,second]
Это просто возвращает список либо одного элемента, объединяющего два аргумента, либо исходных двух элементов.
Затем определите функцию для перебора первого списка и объединения пар:
def collapse(tupleList):
first = tupleList.pop(0)
newList = []
for item in tupleList:
collapsed = combo(first,item)
if len(collapsed)==2:
newList.append(collapsed[0])
first = collapsed.pop()
newList.append(first)
return newList
Это сохраняет первый элемент для сравнения с текущим элементом в списке (начиная со второго элемента), и когда он не может объединить их, он сбрасывает первый в новый список и заменяет first со вторым из двух.
Тогда просто позвоните collapse со списком кортежей:
>>> collapse( [(5, 7), (12, 3), (0, 5), (0, 7), (7, 2), (9, 3)] )
[(5, 10), (0, 5), (0, 12)]
[Править] Наконец, переберите результат, чтобы получить самую длинную последовательность.
def longest(seqs):
collapsed = collapse(seqs)
return max(collapsed, key=lambda x: x[1])
[/Редактировать]
Сложность O(N). Для получения бонусных отметок сделайте это в обратном порядке, чтобы pop(0) становится pop() и вам не нужно переиндексировать массив или перемещать итератор. Для верхних отметок сделайте его попарным reduce операция для многопоточного совершенства.
Если подумать об алгоритме в общих чертах, это сработает?
(извиняюсь за ужасный синтаксис, но я пытаюсь остаться независимым от языка здесь)
Сначала самая простая форма: найдите самую длинную непрерывную пару.
Переберите каждого участника и сравните его с каждым другим участником с более высоким начальным значением. Если начальная точка второго элемента равна сумме начальной точки и длины первого элемента, они являются смежными. Если это так, сформируйте новый член в новом наборе с более низкой начальной точкой и объединенной длиной, чтобы представить это.
Затем возьмите каждую из этих пар и сравните их со всеми отдельными членами с более высоким начальным значением и повторите, образуя новый набор смежных троек (если таковые существуют).
Продолжайте эту схему, пока у вас не будет новых наборов.
Сложность в том, что вам нужно сравнить длину каждого члена каждого из ваших наборов, чтобы найти самую длинную цепочку.
Я уверен, что это не так эффективно, как другие методы, но я считаю, что это жизнеспособный подход к грубому принуждению этого решения.
Буду признателен за отзыв об этом и за любые ошибки, которые я мог пропустить.
Отредактировано для замены псевдокода реальным кодом Python
Отредактировал ОПЯТЬ для изменения кода; Оригинальный алгоритм был на решении, но я не понял, какое второе значение в парах! К счастью, основной алгоритм такой же, и я смог его изменить.
Вот идея, которая решает проблему в O(N log N) и не использует хэш-карту (поэтому нет скрытых времен). Для памяти мы будем использовать N * 2 "вещей".
Мы собираемся добавить еще два значения для каждого кортежа: (BackCount, BackLink). В успешной комбинации BackLink будет связывать справа налево от крайнего правого кортежа до крайнего левого кортежа. BackCount будет значением накопленного значения для заданной BackLink.
Вот немного кода на Python:
def FindTuplesStartingWith(tuples, frm):
# The Log(N) algorithm is left as an excersise for the user
ret=[]
for i in range(len(tuples)):
if (tuples[i][0]==frm): ret.append(i)
return ret
def FindLongestSequence(tuples):
# Prepare (BackCount, BackLink) array
bb=[] # (BackCount, BackLink)
for OneTuple in tuples: bb.append((-1,-1))
# Prepare
LongestSequenceLen=-1
LongestSequenceTail=-1
# Algorithm
for i in range(len(tuples)):
if (bb[i][0] == -1): bb[i] = (0, bb[i][1])
# Is this single pair the longest possible pair all by itself?
if (tuples[i][1] + bb[i][0]) > LongestSequenceLen:
LongestSequenceLen = tuples[i][1] + bb[i][0]
LongestSequenceTail = i
# Find next segment
for j in FindTuplesStartingWith(tuples, tuples[i][0] + tuples[i][1]):
if ((bb[j][0] == -1) or (bb[j][0] < (bb[i][0] + tuples[i][1]))):
# can be linked
bb[j] = (bb[i][0] + tuples[i][1], i)
if ((bb[j][0] + tuples[j][1]) > LongestSequenceLen):
LongestSequenceLen = bb[j][0] + tuples[j][1]
LongestSequenceTail=j
# Done! I'll now build up the solution
ret=[]
while (LongestSequenceTail > -1):
ret.insert(0, tuples[LongestSequenceTail])
LongestSequenceTail = bb[LongestSequenceTail][1]
return ret
# Call the algoritm
print FindLongestSequence([(0,5), (0,1), (1,9), (5,5), (5,7), (10,1)])
>>>>>> [(0, 5), (5, 7)]
print FindLongestSequence([(0,1), (1,7), (3,20), (8,5)])
>>>>>> [(3, 20)]
Ключ ко всему алгоритму - это то, где комментарий "ЭТО КЛЮЧ" находится в коде. Мы знаем, что наш текущий StartTuple может быть связан с EndTuple. Если более длинная последовательность, которая заканчивается в EndTuple.To, существует, она была найдена к тому времени, когда мы добрались до этой точки, потому что она должна была начинаться с меньшего StartTuple.From, а массив отсортирован по "From"!
Я удалил предыдущее решение, потому что оно не было проверено.
Проблема в том, чтобы найти самый длинный путь в "взвешенном ориентированном ациклическом графе", она может быть решена за линейное время:
http://en.wikipedia.org/wiki/Longest_path_problem
Поместите набор {начальных позиций} union {(начальная позиция + конечная позиция)} в качестве вершин. Для вашего примера это будет {0, 1, 5, 10, 11, 12}
для вершин v0, v1, если есть конечное значение w, которое составляет v0 + w = v1, то добавьте направленный ребро, соединяющее v0 с v1, и укажите w в качестве его веса.
Теперь следуйте псевдокоду на странице википедии. Так как количество вершин является максимальным значением 2xn (n - количество кортежей), проблема все еще может быть решена за линейное время.
Это звучит как идеальная проблема "динамического программирования"...
Простейшей программой было бы сделать это грубой силой (например, рекурсивной), но это имеет экспоненциальную сложность.
При динамическом программировании вы можете установить массив a длины n, где n- максимум всех (начало + длина) значений вашей задачи, где a [i] обозначает самую длинную непересекающуюся последовательность вплоть до [i]. Затем вы можете перейти на все кортежи, обновив. Сложность этого алгоритма будет O(n*k), где k - количество входных значений.
- Создайте упорядоченный массив всех начальных и конечных точек и инициализируйте их все в одну
- Для каждого элемента в вашем кортеже сравните конечную точку (начало и конец) с упорядоченными элементами в вашем массиве, если между ними есть какая-либо точка (например, точка в массиве равна 5, и у вас есть начало 2 с длиной 4), измените значение на нуль.
- Закончив цикл, начните перемещаться по упорядоченному массиву и создайте полосу, когда увидите 1, а пока вы видите 1, добавьте к существующей полосе любой ноль, закройте полосу и т. Д.
- В конце проверьте длину полос
Я думаю, что сложность составляет около 0 (4-5 * N)
(СМОТРЕТЬ ОБНОВЛЕНИЕ)
где N - количество элементов в кортеже.
ОБНОВИТЬ
Как вы выяснили, сложность не точна, но определенно очень мала, поскольку она является функцией количества растяжений линий (элементов кортежей).
Так что, если N - это число отрезков строки, сортировка - O(2N * log2N). Сравнение O(2N). Нахождение отрезков также O(2N). Таким образом, всего O (2N (log2N + 2)).