Есть ли алгоритм для решения самой длинной общей последующей проблемы с разными весами для каждого символа? - PullRequest
Новая
       34

Есть ли алгоритм для решения самой длинной общей последующей проблемы с разными весами для каждого символа?

2 голосов
/ 14 мая 2019

Я ищу алгоритм, который решает проблему LCS для двух строк со следующими условиями:

Каждая строка состоит из английских символов, и каждый символ имеет вес. Например:

последовательность 1 (S1): «ABBCD» с весами [1, 2, 4, 1, 3]

последовательность 2 (S2): «TBDC» с весами [7, 5, 1, 2]

Предположим, что MW(s, S) определен как максимальный вес подпоследовательности s в строке S относительно соответствующих весов. Самая тяжелая общая подпоследовательность (HCS) определяется как:

HCS = аргмин (МВт (с, S1), МВт (с, S2))

Выходными данными алгоритма должны быть индексы HCS как в строках, так и в весе. В этом случае индексы будут:

I_S1 = [2, 4] -> МВт («BD», «ABBCD») = 7

I_S2 = [1, 2] -> МВт («BD», «TBDC») = 6

Следовательно HCS = "BD", and weight = min(MW(s, S1), MW(s, S2)) = 6.

1 Ответ

1 голос
/ 14 мая 2019

Таблица, которую вам нужно построить, будет иметь это. 

for each position in sequence 1
    for each position in sequence 2
        for each extreme pair of (weight1, weight2)
            (last_position1, last_position2)

Где крайняя пара - это та, где невозможно найти подпоследовательность к той точке, чьи веса в последовательности 1 и веса в последовательности2 равны> = и, по крайней мере, один>>.

Может быть несколько экстремальных пар, где одна последовательность выше, чем другая.

Правило таково, что в (i, -1) или(-1, j) позиций, единственной экстремальной парой является пустой набор с весом 0. Во всех остальных случаях мы объединяем экстремальные пары для (i-1, j) и (i, j-1).И затем, если seq1[i] = seq2[j], добавьте параметры, в которых вы указали (i-1, j-1), а затем включили i и j в соответствующие подпоследовательности.(Поэтому добавьте weight1[i] и weight2[j] к весам, затем выполните слияние.)

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

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

...