Изучение разностного алгоритма Майерса: часть 2

ОГЛАВЛЕНИЕ

Данная статья изучает детализацию линейного пространства, описанную Евгением У. Майерсом в его статье "Разностный алгоритм O(ND) и его вариации".

•    Скачать двоичные файлы учебного приложения - 23.89 Кб
•    Скачать исходники учебного приложения - 35.52 Кб

Введение

Это вторая часть статьи о разностном алгоритме Майерса, требующая понимания базового жадного алгоритма, описанного в части I.

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

Обратный алгоритм

Базовый алгоритм также может работать обратно, то есть работать от (N,M) обратно до (0, 0). Единственное отличие заключается в том, что сдвиги начинаются в удалении / вставке / совпадении, а не кончаются в них. Ниже показано решение примера, но работающее обратно.

Рисунок 1: Обратное решение

Как видно из диаграммы, решение отличается от первого, сгенерированного путем работы вперед, но имеет такие же длины LCS и SES. Это совершенно правильно, потому что вообще может быть много эквивалентных решений, и алгоритм просто выбирает первое найденное решение.

Дельта: Поскольку длины последовательностей A и B могут различаться, k линии прямого и обратного алгоритмов могут различаться. Полезно выделить эту разницу в переменную delta = N - M. В примере N = 7 и M = 6, что дает дельта = 1. Это смещение от прямых k линий до обратных k линий. Можно сказать, что прямые пути сконцентрированы вокруг k = 0, а обратные пути сконцентрированы вокруг k = delta.

Читайте также:
  • Манипулирование цветами в .NET – часть первая
    • Скачать демонстрационный проект (.NET 1.1) - 58.8 Кб• Скачать исходники C# (.NET 1.1) - 110.0 Кб• Скачать исходники C# (.NET 2.0) - 111.2 Кб• Скачать исходники VB (.NET 2.0) - 115.7 Кб Введение Почему статья о "цветах"? На самом деле, в .NET, можно использовать только два формата цвета: цвет...
  • Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0
    •    Скачать исходники - 265.8 Кб (с тестами NUnit)•    Скачать двоичные файлы - 40.5 Кб•    Домашняя страница проекта NGenerics (CodePlex)Статья не дает все подробности и полные описания внутреннего устройства этих коллекций и алгоритмов - наоборот, она дает ссылки на имеющиеся в интернете ресурс...
  • Определение цен барьерных опционов с помощью сеток. Часть первая – постоянные барьеры
    •    Скачать демонстрационный проект - 5.26 Кб•    Скачать исходники - 12.2 Кб Введение Стоит отметить, что представленный метод можно расширить до вмещения опционов с несколькими постоянными барьерами. После изучения простого примера перейдем к более сложным опционам с изменяющимися во времени ...
  • FuzzyAdvisor – простая экспертная система с нечеткой логикой на F#
    •    Скачать исходники - 108 Кб Введение Более 15 лет назад разрабатывали проект (Brulé и др., 1995), требовавший экспертную систему, выбирающую подходящий вариант исходя из некоторых основных параметров. Были опробованы несколько подходов, в том числе использование исчисления предикатов (...
  • Нейронные сети на C#
    •    Скачать исходники - 251 Кб•    Скачать демонстрационный проект - 181 Кб Введение История нейронных сетей начинается в 1950-х гг., когда была представлена архитектура простейших нейронных сетей. После начальной работы в области идея нейронных сетей стала весьма популярной. Но затем область...