алгоритм поиска самых длинных непересекающихся последовательностей

Question

Я пытаюсь найти лучший способ решить следующую проблему.Лучше всего я имею в виду менее сложный.

В качестве входных данных используется список кортежей (начало, длина), таких как:

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

Каждый элемент представляет последовательность своим start * 1007.* и длина , например (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)].

Answer 1

Итерируйте по списку кортежей, используя заданный порядок (по элементу start), при этом используя хэш-карту для отслеживания длины самой длинной непрерывной последовательности , заканчивающейся по определенному индексу.1004 * псевдокод, пропуская детали, такие как элементы, не найденные в хэш-карте (предположим, 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))

Answer 2

Это частный случай проблемы самого длинного пути для взвешенных направленных ациклических графов .

Узлы на графике - это начальные точки и точки после последнего элемента в последовательности, где может начинаться следующая последовательность.

Проблема особенная, поскольку расстояние между двумя узлами должно быть одинаковым независимо от пути.

Answer 3

Пересмотренный алгоритм:

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]);
}

Answer 4

Если подумать об алгоритме в общих чертах, сработает ли это?

(извиняюсь за ужасный синтаксис, но я пытаюсь остаться независимым от языка)

Сначала самая простая форма:Найдите самую длинную непрерывную пару.

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

Затем возьмите каждую из этих пар и сравните их со всеми одиночными членами с более высокой стартовой точкой и повторите, образуя новый набор смежных троек (если таковые имеются).

Продолжите этошаблон, пока у вас нет новых наборов.

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

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

Буду признателен за отзыв об этом и за любые ошибки, которые я мог пропустить.

Answer 5

Это простая операция уменьшения.Учитывая пару последовательных кортежей, они могут или не могут быть объединены.Итак, определите функцию парной комбинации:

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])

[/ Edit]

Сложность O (N).Для бонусных отметок сделайте это в обратном порядке, чтобы начальный pop(0) стал pop(), и вам не нужно было переиндексировать массив или вместо этого переместить итератор.Для высших отметок запустите его как парную reduce операцию для многопоточного совершенства.

Answer 6

Отредактировано для замены псевдокода реальным кодом 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»!

Answer 7

Я удалил предыдущее решение, потому что оно не было проверено.

Проблема в том, чтобы найти самый длинный путь в «взвешенном ориентированном ациклическом графе», его можно решить за линейное время:

http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs

Поместить набор {начальных позиций} union {(начальная позиция + конечная позиция)} в качестве вершин.Для вашего примера это будет {0, 1, 5, 10, 11, 12}

для вершин v0, v1, если есть конечное значение w, которое составляет v0 + w = ​​v1, затем добавьте направленный крайподключив v0 к v1 и поставив w в качестве его веса.

Теперь следуйте псевдокоду на странице википедии.поскольку число вершин является максимальным значением 2xn (n - количество кортежей), проблему все еще можно решить за линейное время.

Answer 8

• Создайте упорядоченный массив всех начальных и конечных точек и инициализируйте их все в одну
• . Для каждого элемента в вашем кортеже сравните конечную точку (начало и конец) с упорядоченными элементами вваш массив, если между ними есть какая-либо точка (например, точка в массиве равна 5, и у вас есть начало 2 с длиной 4), измените значение на ноль.
• После завершения цикла начните перемещаться по упорядоченному массиву и создайтеполосу, когда вы видите 1 и пока вы видите 1, добавьте к существующей полосе любой ноль, закройте полосу и т. д.
• В конце проверьте длину полос

Я думаю, что сложность составляет вокруг O (4-5 * N)

(СМ. ОБНОВЛЕНИЕ)

, где N - количество элементов в кортеже.

---

ОБНОВЛЕНИЕ

Как вы выяснили, сложность не точна, но определенно очень мала, поскольку она является функцией числа растяжений линий (элементов кортежа).

Таким образом, если N - это число отрезков строки, сортировка будет O (2N * log2N).Сравнение O (2N).Нахождение отрезков также O (2N).Таким образом, всего O (2N (log2N + 2)) .

Answer 9

Это звучит как идеальная проблема "динамического программирования" ...

Самой простой программой было бы сделать это грубой силой (например, рекурсивной), но это имеет экспоненциальную сложность.

При динамическом программировании вы можете установить массив a длины n, где n - максимум всех (начало + длина) значений вашей задачи, где a [i] обозначает самую длинную непересекающуюся последовательность вверхк [я].Затем вы можете перейти на все кортежи, обновив.Сложность этого алгоритма будет O (n * k), где k - количество входных значений.