Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Общие подпоследовательности. Дистанция /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


8  Введение
8  Рекурсивное решение
8  Запоминание
8  Динамическое программирование снизу вверх
8  Итерационное LCS ( Longest Common Subsequence )
8  Сама подпоследовательность
8  Уменьшаем требоватия к памяти
Задача о наибольшей общей подпоследовательности. - Программирование от RIN.RU
Задача о наибольшей общей подпоследовательности.

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


Итак, задача состоит в том, чтобы для данных строк x и y (|x|, |y| > 0) найти |lcs(x,y)|, где lcs(x,y) - самая длинная общая подпоследовательность (longest common subsequence) x и y. Как правило, требуется найти не только длину lcs(x,y), но и саму эту последовательность.






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


  • В этом разделе :

    8  Введение
    Для начала определим, в чем заключается задача.

    8  Рекурсивное решение
    Попробуем решить нашу задачу, используя рекурсию, а далее улучшить его через динамическое программирование.

    8  Запоминание
    Недостаток рекурсивного решения в том, что одинаковые подзадачи вызываются много раз в разное время.

    8  Динамическое программирование снизу вверх
    То, что было описано выше - всего лишь более умный путь создания рекурсивного алгоритма. Но можно считать эту программу способом заполнения массива L. Последовательность заполнения контролирует рекурсия, однако те же результаты можно получить и при другом порядке.

    8  Итерационное LCS ( Longest Common Subsequence )


    8  Сама подпоследовательность


    8  Уменьшаем требоватия к памяти
    Один из недостатков описанного метода динамического программирования, по сравнению с исходной рекурсией - в том, что он требует O(mn) памяти на массив L ( рекурсия - O(n+m) ).

    8  Введение
    8  Рекурсивное решение
    8  Запоминание
    8  Динамическое программирование снизу вверх
    8  Итерационное LCS ( Longest Common Subsequence )
    8  Сама подпоследовательность
    8  Уменьшаем требоватия к памяти

     
      
      
        Copyright ©  RIN 2003 - 2004      * Обратная связь
    отель Золотое Кольцо . Календарь матчей порту стал известен календарь матчей.