помогите с алгоритмом

← →
lak-b/proxy/ (2007-03-14 16:51) [0]

Возможно, это какая-то известная задача.
Сам пока не додумался, как гуглить - не пойму. Вобщем - вот:

Есть две целочисленные последовательности (два вектора): В1 и В2. Найти такие подпоследовательности (N подряд идущих элементов) В1, которые присутствуют также в В2.
//если это еще куда ни шло, то дальше - больше :)
Последовательность можно искать, используя знаки: "?" и "*" (любое число и произвольный ряд чисел, соответственно)

Главнаяч задача - минимизируя количество значков "?" и "*", найти наиболее длинную подпоследовательность В1, которая присутствует и в В2.

Есть ли какие-нибудь соображения на этот счет?

← →
default © (2007-03-14 17:07) [1]

вроде у Арсак "Программирование игр и головоломок" я видел что-то похожее

← →
oldman © (2007-03-14 17:12) [2]

Может я математику забыл...

А как может часть вектора быть частью другого???

← →
TUser © (2007-03-14 17:15) [3]

> Главнаяч задача - минимизируя количество значков "?" и "*",
> найти наиболее длинную подпоследовательность В1, которая
> присутствует и в В2.

2 взаимоисключающих требования. Например, подпоследовательность "*" имеет наибольшую длину (пусть, 100), но если есть общая подпоследовательность длины, скажем, 10, то какая из них тебе нужна - которая длинее, или которая без звездочки? Опиши понятнее, что требуется.

← →
TUser © (2007-03-14 17:16) [4]

А так, если алгоритм Смита-Ватерманы, мы обычно с его помощью подобные задачи решаем.

← →
lak-b/proxy/ (2007-03-14 17:21) [5]

TUser
1,2,3,*,4 - будем считать, что длинна подобной последовательности = 4

← →
MBo © (2007-03-14 17:22) [6]

>TUser
Это алгоритм, похожий на получение LCS динамическим программированием?

← →
TUser © (2007-03-14 18:02) [7]

> Это алгоритм, похожий на получение LCS динамическим программированием?

Да. Отличие - максимум ищется среди трех возможных вариантов и нуля. Ну, и от максимумов до нуля надо пройтись. Получаются подпоследовательности, которые нельзя удлиннять без ухудшения.

> lak-b/proxy/ (14.03.07 17:21) [5]

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

http://www.bionet.nsc.ru/chair/cib/lectures/2003_1_CompGenom/CG07/img13.html
http://www.rtcb.iitp.ru/training/ab_004f_aa/ab_004f_aa.ppt

Еще это похоже на задачу нахождения минимальной цены редактирования, только в отличие от обычных условий цена удаления-вставки непрерывной последовательности(*) равна цене для одного символа.

> MBo © (14.03.07 18:38) [9]

Есть хитрый способ сделать аффинные гепы (т.е. штраф зависит от длины). Матрица в этих задачах - это по сути граф, в котором какие-то маршруты ищутся. Надо каждой ячейке ставить в соотвествие две вершины графа, одну нормальную, а другую - она учитывает то состояние, когда мы вставляем символы в качестве звездочки. Ну, и сообразить, как ребра организовать.

помогите с алгоритмом Найти похожие ветки