Форум: "Прочее";
Текущий архив: 2007.04.08;
Скачать: [xml.tar.bz2];
Вниз
помогите с алгоритмом Найти похожие ветки
← →
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 динамическим программированием?
Да. Отличие - максимум ищется среди трех возможных вариантов и нуля. Ну, и от максимумов до нуля надо пройтись. Получаются подпоследовательности, которые нельзя удлиннять без ухудшения.
← →
TUser © (2007-03-14 18:05) [8]> 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 © (2007-03-14 18:38) [9]Еще это похоже на задачу нахождения минимальной цены редактирования, только в отличие от обычных условий цена удаления-вставки непрерывной последовательности(*) равна цене для одного символа.
← →
TUser © (2007-03-14 19:18) [10]> MBo © (14.03.07 18:38) [9]
Есть хитрый способ сделать аффинные гепы (т.е. штраф зависит от длины). Матрица в этих задачах - это по сути граф, в котором какие-то маршруты ищутся. Надо каждой ячейке ставить в соотвествие две вершины графа, одну нормальную, а другую - она учитывает то состояние, когда мы вставляем символы в качестве звездочки. Ну, и сообразить, как ребра организовать.
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2007.04.08;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.306 c