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

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

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

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

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

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

HCS = argmin(MW(s, S1), MW(s, S2))

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

I_S1 = [2, 4] --> MW("BD", "ABBCD") = 7

I_S2 = [1, 2] --> MW("BD", "TBDC") = 6

Поэтому HCS = "BD", and weight = min(MW(s, S1), MW(s, S2)) = 6.


algorithm dynamic-programming lcs
person Amin Edraki    schedule 13.05.2019    source источник
comment
Что вы сделали для решения задачи?   -  person Michel_T.    schedule 14.05.2019
comment
Если веса неотрицательны, вы можете использовать тот же подход, что и в обычном LCS; однако в рекурсивной формуле вы должны использовать сумму весов для минимизации вместо количества символов. Однако я не уверен в случае с отрицательными весами.   -  person A. Mashreghi    schedule 14.05.2019
comment
Да, веса неотрицательны. Вы случайно не знаете, какой алгоритм LCS я могу использовать для модификации и решения моей собственной проблемы?   -  person Amin Edraki    schedule 14.05.2019

Ответы (1)


arrow_upward
1
arrow_downward

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

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, который уже был опубликован ранее в последовательности.

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

person btilly    schedule 14.05.2019