алгоритм поиска самых длинных неперекрывающихся последовательностей
https://stackoverflow.com/questions/4593583
-
15-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь найти наилучший способ решить следующую проблему.Под наилучшим способом я подразумеваю менее сложный.
В качестве входных данных используется список кортежей (начало, длина), таких:
[(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)].
Решение
Итерация над списком кортежей с использованием заданного упорядочения (путем начального элемента), используя хэшмап, чтобы отслеживать длину самой длинной непрерывной последовательности. конец по определенному индексу.
Псевдокод, пропуская детали, такие как предметы, не найденные в хэшмапе (предположим, что 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]);
}
Это особый случай Самая длинная проблема пути для взвешенных направленных ациклических графиков.
Узлы на графике - это начальные точки и точки после последнего элемента в последовательности, где может начаться следующая последовательность.
Проблема особенная, потому что расстояние между двумя узлами должно быть одинаковым независимо от пути.
Размышляя об алгоритме в основных терминах, будет ли это работать?
(Приносим извинения за ужасный синтаксис, но я стараюсь оставаться здесь независимым от языка)
Сначала самая простая форма: найти самую длинную смежную пару.
Прокатитесь через каждого участника и сравните его с любого другого члена с более высоким стартовым. Если Startpos второго члена равен сумме Startpos и длине первого члена, они смежны. Если это так, сформируйте новый элемент в новом наборе с нижним стартовым и комбинированной длиной, чтобы представить это.
Затем возьмите каждую из этих пар и сравните их со всеми отдельными членами с более высокими стартовыми и повторяя, образуя новый набор смежных тройков (если существуют).
Продолжайте этот шаблон, пока у вас нет новых наборов.
Сложная часть того, что вам нужно сравнить длину каждого члена каждого из ваших наборов, чтобы найти настоящую самую длинную цепь.
Я почти уверен, что это не так эффективно, как другие методы, но я считаю, что это жизнеспособный подход к грубому принуждению этого решения.
Я бы признателен отзывы об этом и любых ошибках, которые я мог упустить из виду.
Отредактировано для замены псевдокода фактическим кодом Python
Отредактировано снова, чтобы изменить код; Оригинальный алгоритм был на решении, но я понял, каково было второе значение в парах! Fortunatelly Основной алгоритм такой же, и я смог его изменить.
Вот идея, которая решает проблему в O (n log n) и не использует хэш -карту (так что без скрытых времен). Для памяти мы собираемся использовать n * 2 "вещи".
Мы собираемся добавить еще два значения в каждый кортеж: (Backcount, Backlink). В успешной комбинированной обратной ссылке будет связываться справа налево от самого правого кортежа с самого левого кортежа. Backcount будет накопленным значением для данной обратной связи.
Вот какой -то код 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)]
Ключ для всего алгоритма - это то, где комментарий «это ключ» находится в коде. Мы знаем, что наш текущий стартап может быть связан с EndTuple. Если более длинная последовательность, которая заканчивается в конце.
Я удалил предыдущее решение, потому что оно не было протестировано.
Проблема заключается в нахождении самого длинного пути в "взвешенном направленном ациклическом графе", она может быть решена за линейное время:
http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs
Поместите набор {начальных позиций} объединения {(начальная позиция + конечная позиция)} в качестве вершин.Для вашего примера это было бы {0, 1, 5, 10, 11, 12}
для вершин v0, v1, если существует конечное значение w, которое составляет v0 + w = v1, то добавьте направленное ребро, соединяющее v0 с v1, и поместите w в качестве его веса.
Теперь следуйте псевдокоду на странице википедии.поскольку количество вершин равно максимальному значению 2xn (n - количество кортежей), задача все еще может быть решена за линейное время.
Это простая операция по сокращению. Учитывая пару последовательных кортежей, они либо могут быть или не могут быть объединены. Так что определите функцию парной комбинации:
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 Операция для многопоточной добра.
Это звучит как идеальная проблема «динамическое программирование» ...
Самая простая программа - это сделать грубую силу (например, рекурсивную), но это имеет экспоненциальную сложность.
При динамическом программировании вы можете настроить массив A длины n, где n-максимум из всех (начало+длины) значений вашей проблемы, где A [i] обозначает самую длинную непересекающуюся последовательность до [i]. Затем вы можете передать все кортежи, обновляя. Сложность этого алгоритма будет O (n*k), где k - это количество входных значений.
- Создайте упорядоченный массив всех начальных и конечных точек и инициализируйте их все в один
- Для каждого элемента в вашем кортеже сравните конечную точку (начало и конец) с упорядоченными элементами в вашем массиве, если какая -либо точка находится между ними (например, точка в массиве 5, и у вас есть начало 2 с длиной 4) Изменение значения на нуль.
- После окончания петли начните перемещаться по упорядоченному массиву и создайте полосу, когда вы видите 1 и, когда вы видите 1, добавьте к существующей полосе, с любым нолью, закройте полоску и т. Д.
- В конце проверьте длину полос
Я думаю, что сложность вокруг O (4-5*N)
(См. Обновление)
с n, будучи количеством предметов в кортеже.
ОБНОВИТЬ
Как вы поняли, сложность не является точной, но определенно очень мала, так как она является функцией количества линейных растяжков (предметы рубки).
Таким образом, если n - количество линейных растяжек, сортировка - O (2n * log2n). Сравнение o (2n). Поиск линий растягивает также O (2n). Так в целом O (2n (log2n + 2)).
